Eine Woche Programmierwettbewerb: Rechtecke

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.

Ponto

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).

Wie gesagt habe ich Verständnis dafür, dass du deine Ideen für dich behalten möchtest oder gar musst. Andererseits wäre es dumm, nicht mit den anderen Ideen den eigenen Horizont zu erweitern. Das gilt für diesen und für alle folgenden Wettbewerbe. Es tut mir auch leid, dass du Zeit in diese Sache gesteckt hast, ohne etwas einsenden zu dürfen.

Ich denke jedoch, dass es nichts zuzugeben gab. Ich habe auf jede Frage zu der Aufgabe bereitwillig geantwortet. Wofür man eine Lösung der Aufgabe nutzen kann, ist auch nicht schwer zu erraten. Dann muss man sich von Anfang an fragen, ob man eine Lösung beisteuern kann oder nicht. Hättest du die Aufgabe anders bewertet, wenn ich gesagt hätte, dass mir kein praktischer Nutzen einfällt? Oder wenn keiner nach dem Ursprung gefragt hätte? Ich denke also, dass sich durch meine späteren Aussagen grundsätzlich nichts geändert hat.

jenz

okay, wenn die caches gemeinsam genutzt werden, dann kann ich mich darauf einlassen, dass es schief gehen kann. auch wenn die threads ja so ziemlich auf den gleichen daten arbeiten.
lesend auf den rechtecken, schreibend auf der plane. lesen muss man nicht kontrollieren, das schreiben in die plane bei meinem verfahren auch nicht.

jeder thread hätte dann noch eine eigene "verwaltugsstruktur", die könnte natürlich den cache durcheianderbringen...

bei getrennten caches sollte die geschwinigkeitssteigerung aber ziemlich deutlich sein. eben fast verdoppelt, wenn man 2 nimmt.

jenz

rapso

Ponto schrieb:

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).

Wie gesagt habe ich Verständnis dafür, dass du deine Ideen für dich behalten möchtest oder gar musst. Andererseits wäre es dumm, nicht mit den anderen Ideen den eigenen Horizont zu erweitern. Das gilt für diesen und für alle folgenden Wettbewerbe. Es tut mir auch leid, dass du Zeit in diese Sache gesteckt hast, ohne etwas einsenden zu dürfen.

keine sorge, ich kann das ja nach dem release der resultate usw. mit meiner version vergleichen. Bisher hab ich nicht viel zeit reingesteckt, leidglich das framework gesetzt und jesters version umgestellt mit trivialoptimierungen. (da sind nichtmal deine generatoren integriert).
wobei es mich auch mehr reizt dann das ganze fluessig darzustellen (was du ja als eigentliche anwendung genannt hast) als punkte in nem vector<vector<>> zu setzen *hehe*.

Ich denke jedoch, dass es nichts zuzugeben gab. Ich habe auf jede Frage zu der Aufgabe bereitwillig geantwortet. Wofür man eine Lösung der Aufgabe nutzen kann, ist auch nicht schwer zu erraten. Dann muss man sich von Anfang an fragen, ob man eine Lösung beisteuern kann oder nicht. Hättest du die Aufgabe anders bewertet, wenn ich gesagt hätte, dass mir kein praktischer Nutzen einfällt?

wenn ich gesehen haette dass es keinen nutzen gibt, haette ich eventuell code eingesand, aber da ich die benches auch alleine fuer mich machen kann wenn die sources und resultate freigegeben sind...

Oder wenn keiner nach dem Ursprung gefragt hätte? Ich denke also, dass sich durch meine späteren Aussagen grundsätzlich nichts geändert hat.

es wirkte von anfang an sehr auf einen speziellen context bezogen, deine aufgabenstellung implizirte das (vielleicht deine wortwahl )

Ich finde es ja gut dass du nen contest hier machst, raetsel loesen macht ja auch spass selbst wenn man sich nicht oeffentlich mit anderen misst oder es grossartige preise gibt.

Ponto

jenz schrieb:

okay, wenn die caches gemeinsam genutzt werden, dann kann ich mich darauf einlassen, dass es schief gehen kann. auch wenn die threads ja so ziemlich auf den gleichen daten arbeiten.
lesend auf den rechtecken, schreibend auf der plane. lesen muss man nicht kontrollieren, das schreiben in die plane bei meinem verfahren auch nicht.

jeder thread hätte dann noch eine eigene "verwaltugsstruktur", die könnte natürlich den cache durcheianderbringen...

bei getrennten caches sollte die geschwinigkeitssteigerung aber ziemlich deutlich sein. eben fast verdoppelt, wenn man 2 nimmt.

Nehmen wir mal an, dass du folgendermaßen parallelisierst:

Jeder Thread bekommt einen Teil der plane. Dann geht er durch die Rechteckliste und aktualisiert seinen Planeanteil, wenn das Rechteck darin liegt.

Wir können leicht dafür sorgen, dass die Planeteile, in die die Threads schreiben sich Cachemässig nicht in die Quere kommen. Dennoch wird man keinen Faktor 2 bei 2 Threads erhalten, denn wir machen jetzt manche Arbeit doppelt.

Nehmen wir an die Gesamtarbeit ist GA und der Anteil für das Schreiben in die Plane ist x*GA. Dann haben wir noch (1-x)*GA an Arbeit, die für das Durchlaufen der Rechteckliste und für die Bestimmung, ob die Rechecke in die Plane passen, draufgehen. Den ersten Teil kann man parallelisieren, den zweiten macht man jedoch doppelt.

Damit steigt die Arbeit im Falle zweier Threads auf x*GA + 2*(1-x)*GA und mit perfekter parallelisierung macht dann jeder Thread: 0.5*x* GA + (1-x)*GA

Der Speedupfaktor gegenüber der seriellen Lösung ist dann GA/(0.5*x* GA + (1-x)*GA) = 1 /(0.5*x + (1-x)) = 1/(1 - 0.5x).

Je näher also das x an 1 ist, desto näher ist der Speedup bei 2. Aber wenn x klein ist, können wir nur ganz geringe Speedups erwarten.

rapso

jenz schrieb:

okay, wenn die caches gemeinsam genutzt werden, dann kann ich mich darauf einlassen, dass es schief gehen kann. auch wenn die threads ja so ziemlich auf den gleichen daten arbeiten.

du kannst pech haben und jeder thread hat seine daten so, dass sie sich im cache ueberlagern, sodass sich die threads gegenseitig die daten "wegschmeissen" aus dem cache.

lesend auf den rechtecken, schreibend auf der plane. lesen muss man nicht kontrollieren, das schreiben in die plane bei meinem verfahren auch nicht.

das ist dem cache relativ egal beim mappen von cache-adress-space auf den echten addressspace.

jeder thread hätte dann noch eine eigene "verwaltugsstruktur", die könnte natürlich den cache durcheianderbringen...

koennte, koennte auch ein gewinn sein, je nach architektur.

bei getrennten caches sollte die geschwinigkeitssteigerung aber ziemlich deutlich sein. eben fast verdoppelt, wenn man 2 nimmt.

koennte aber auch doppelte belastung des rams sein, was wenn das ram das limitierende in dem fall ist? dann zerschiessen sich die threads die sequential reads?

was ist bei nem intel quadcore, 2cores teilen sich jeweils den cache, greifen die cores in der falschen combination auf die daten zu, muessen die daten aus dem einen cache ueber den FSB ins ram geschrieben werden und dann in den anderen cache....

klar, am ende hat man irgend ne beschleunigung, einer hat eventuell ne arschkarte und die ergebnisse sehen auf jeder maschine aus wie anders ausgewuerfelt

mag sein dass ich hier zu sehr schwarzmale, aber ich hab schon erlebt, dass je besser eine optimierung fuer threads ist, desto anfaelliger ist sie auf anderen architekturen.