Eine Woche Programmierwettbewerb: Rechtecke

Ponto

TomasRiker schrieb:

Ja, das hab ich auch schon gemerkt (und bei mir korrigiert).
Da ich unter Windows arbeite, musste ich den Timer durch timeGetTime() ersetzen.
Bei der Erstellung des distribution[]-Arrays ist auch noch ein Fehler drin (jedenfalls in der Version, die ich jetzt grade habe). Es kann passieren (und tut es auch), dass ein Rechteck dort eingetragen wird, obwohl es durch einen der nachfolgenden Tests rausfliegt.

Wie lange braucht ihr für:
> contest p 12345 4096x4096 4096 100000000 (100 Millionen)?

Ich bin mittlerweile bis auf 25 Sekunden runter

Die distribution map ist nur ein einfacher Check, dass die Größen auch logarithmisch abnehmen.

Mach deine Rechtecke nicht so groß. Je größer desto einfacher. für 4096x4096 würde ich eher 512 als maxsize nehmen.

TomasRiker

Ponto schrieb:

Mach deine Rechtecke nicht so groß. Je größer desto einfacher. für 4096x4096 würde ich eher 512 als maxsize nehmen.

Sehr gut. Dafür brauche ich dann nur knappe 15 Sekunden.

Ponto

TomasRiker schrieb:

Ponto schrieb:

Mach deine Rechtecke nicht so groß. Je größer desto einfacher. für 4096x4096 würde ich eher 512 als maxsize nehmen.

Sehr gut. Dafür brauche ich dann nur knappe 15 Sekunden.

Hui. Naja. Ich muss eh verschiedene Größen testen.

TomasRiker

In der Aufgabenstellung heißt es, dass die Rechtecke auch teilweise außerhalb des plane-Rechtecks liegen können. Allerdings liefern die Generatoren nie solche Rechtecke.
Darf man den Test nun weglassen?

Ponto

TomasRiker schrieb:

In der Aufgabenstellung heißt es, dass die Rechtecke auch teilweise außerhalb des plane-Rechtecks liegen können. Allerdings liefern die Generatoren nie solche Rechtecke.
Darf man den Test nun weglassen?

Nein. Vor allem, weil ich schon Abgaben mit dem Test habe.

Die Korrektheit wird mit handverlesenen Instanzen getestet, bei denen auch mal ein Rechteck außerhalb liegt.

Geht denn dafür soviel Laufzeit verloren?

Im echten Leben gibt es immer mal Rechtecke außerhalb, vor allem, wenn man in Bilder reinzoomt.

TomasRiker

Ponto schrieb:

Geht denn dafür soviel Laufzeit verloren?

Im echten Leben gibt es immer mal Rechtecke außerhalb, vor allem, wenn man in Bilder reinzoomt.

Ohne den Test wäre mein Algorithmus teilweise ca. 10% schneller, aber egal.
Hat diese Aufgabe etwa eine praktische Anwendung?

Ponto

TomasRiker schrieb:

Ponto schrieb:

Geht denn dafür soviel Laufzeit verloren?

Im echten Leben gibt es immer mal Rechtecke außerhalb, vor allem, wenn man in Bilder reinzoomt.

Ohne den Test wäre mein Algorithmus teilweise ca. 10% schneller, aber egal.
Hat diese Aufgabe etwa eine praktische Anwendung?

Ich musste das Problem selbst lösen, als ich einen Viewer für VLSI Daten geschrieben habe. Da hat man ungefähr 10-20 Mio Rechtecke, die man anzeigen möchte. Da man nur ungefähr 1 Mio Pixel im Fenster hat,
gibt es zwangsläufig Überlappungen. Das löst man, indem das letzte Rechteck gewinnt. Zoomt man rein, lösen sich die Überlappungen auf, und man muss sich nur um einen Ausschnitt kümmern.

Der Wiringgenerator erzeugt Bilder, die auch ungefähr der Realität entsprechen. In der Realität sind die Drähte aber nur auf bis zu 10 Lagen verteilt. Das macht der Generator nicht.

Der Placementgenerator erzeugt Bilder, die einem nicht legalen Placement entsprechen. (Legal bedeutet, dass sich keine zwei Rechtecke überlappen) Die Verteilung der Rechteckgrößen ist auf echten Chips ähnlich. Es gibt wenige große und sehr viele kleine.

TomasRiker

Sehr interessant, und wirst du die beste Lösung dann in dein Programm einbauen (falls sie besser ist als deine)?

Hier übrigens mal ein Ruby-Script, das ganz viele zufällige Tests ausführt.

def exec(str)
  puts
  puts '****************************************'
  puts 'EXECUTING:'
  puts '----------------------------------------'
  puts str
  puts '****************************************'
  puts
  system str
end

while true do
  seed = 1 + rand(1000)
  plane_w = 1 + rand(256)
  plane_h = 1 + rand(256)
  mode = rand(4)
  if mode == 0 then
    max_size = 1 + rand(1024)
    num_rects = 1 + rand(100000)
    exec "contest p #{seed} #{plane_w}x#{plane_h} #{max_size} #{num_rects}"
  elsif mode == 1 then
    num_layers = 1 + rand(10)
    exec "contest d #{seed} #{plane_w}x#{plane_h} #{num_layers}"
  elsif mode == 2 then
    num_wires = 1 + rand(100000)
    exec "contest w #{seed} #{plane_w}x#{plane_h} #{num_wires}"
  elsif mode == 3 then
    max_size = 1 + rand(1024)
    num_rects = 1 + rand(100000)
    exec "contest r #{seed} #{plane_w}x#{plane_h} #{max_size} #{num_rects}"
  end
end

Ponto

TomasRiker schrieb:

Sehr interessant, und wirst du die beste Lösung dann in dein Programm einbauen (falls sie besser ist als deine)?

Die nehme ich höchstens als Inspiration den Viewer mal zu überarbeiten. Es fehlen ja noch viele andere Primitive wie Linien, Polygone, Text uns so weiter.

Und einfach so fremden Code einbauen lassen mich die Anwälte eh nicht.

Ponto

Zur Erinnerung. Heute um 18 Uhr ist Einsendeschluss.

Sobald ich zurück bin, werde ich mich an die Auswertung machen.

TomasRiker

Ich habe dir meine Lösung jetzt zugeschickt.
Bitte sag mir bescheid, dass sie angekommen ist

Ponto

Hallo,

ich habe 4 Einsendungen erhalten:

otze
Jens
TomasRiker
camper

Ich werde mich morgen an die Auswertung setzen.

Badestrand

Ach verflucht, ich hab irgendeinen doofen Fehler nicht rausgekriegt

rapso

Badestrand schrieb:

Ach verflucht, ich hab irgendeinen doofen Fehler nicht rausgekriegt

und mir klang das ein wenig spanish von den anforderungen her, als ob jemand gratis die optimierungsarbeit von anderen sehen moechte *hehe*

Ponto

rapso schrieb:

Badestrand schrieb:

Ach verflucht, ich hab irgendeinen doofen Fehler nicht rausgekriegt

und mir klang das ein wenig spanish von den anforderungen her, als ob jemand gratis die optimierungsarbeit von anderen sehen moechte *hehe*

Wenn du nicht völlig realitätsfremde Probleme sehen möchtest, hast du diese Gefahr immer. Dass du mir nicht vertraust, dass es hier nur um den Wettbewerb geht, kann ich verstehen. Warum sollte man das auch tun.

Ponto

Ich suche übrigends Ideen für einen folgenden Programmierwettbewerb. Wenn jemand eine interessante Problemstellung hat, kann er sich an die obige Adresse melden.

jenz

@rapso:

ich hatte ja mal wegen der threads nachgefragt.
warum meinst du, dass das "random" ist?
ich finde, dass sich das problem recht gut parallelisieren ließe.
einfach die plane aufteilen und wenn ein thread dann schneller fertig ist, als andere, dann bekommt er einen teil von dessen plane.

würde in mein verfahren recht gut reinpassen.

ich verstehe nicht, was daran dann nicht von vorteil sein sollte, natürlich nur bei mehreren kernen/prozessoren, aber das kann man im rahmen der optimierung ja anpassen.

@ponto:
optimieren auf mehrere threads/prozessoren vielleicht?

jenz

Ponto

jenz schrieb:

@ponto:
optimieren auf mehrere threads/prozessoren vielleicht?

jenz

Dazu bräuchte man aber auch eine andere Aufgabe.

rapso

Ponto schrieb:

rapso schrieb:

Badestrand schrieb:

Ach verflucht, ich hab irgendeinen doofen Fehler nicht rausgekriegt

und mir klang das ein wenig spanish von den anforderungen her, als ob jemand gratis die optimierungsarbeit von anderen sehen moechte *hehe*

Wenn du nicht völlig realitätsfremde Probleme sehen möchtest, hast du diese Gefahr immer. Dass du mir nicht vertraust, dass es hier nur um den Wettbewerb geht, kann ich verstehen. Warum sollte man das auch tun.

tja, am ende hast du selbst zugegeben dass du das nutzen moechtest (nutzen!=copy&paste), andere zahlen mir mein gehalt damit ich sowas fluessig auf dem schirm zaubere, da kann ich das ja nicht gratis hier machen (zumal das mein arbeitsvertrag auch verbietet, wie vielleicht von einigen anderen auch).

rapso

jenz schrieb:

@rapso:

ich hatte ja mal wegen der threads nachgefragt.
warum meinst du, dass das "random" ist?
ich finde, dass sich das problem recht gut parallelisieren ließe.
einfach die plane aufteilen und wenn ein thread dann schneller fertig ist, als andere, dann bekommt er einen teil von dessen plane.

würde in mein verfahren recht gut reinpassen.

ich verstehe nicht, was daran dann nicht von vorteil sein sollte, natürlich nur bei mehreren kernen/prozessoren, aber das kann man im rahmen der optimierung ja anpassen.

multithreading haengt oft stark von der architektur ab auf der es laeuft, manchmal kannst du cachetrasching produzieren die deine 4threads langsammer als einen machen, manchmal kann genau der selbe code fast 4mal schneller laufen, wenn man da nicht sehr genau weiss was man macht und auf welcher maschine koennen die resultate random sein.
natuerlich hat man im schnitt wenn alle hier teilnehmen ne bessere geschwindigkeit, aber es kann gut sein dass auf einer anderen maschine der letzte der erste wird.