Du bist nicht angemeldet.

#15: "Rutschige Angelegenheit", Geschwindigkeit, 03.03.2013

Werbeanzeige

Schrompf

Alter Hase

Beiträge: 1 403

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

31

11.02.2013, 19:55

Ja, schwierig auf jeden Fall. Die plumpe Lösung wäre ja, jeden Stein von jeder benachbarten Wand "abstoßen" zu lassen und dann *alle* Felder bis zur nächsten Wand als potentielle Vorgänger-Position zu listen. Damit fliegt einem schon nach ganz wenigen Schritten die Anzahl der Möglichkeiten um die Ohren. Ich habe da aber eine Validierungsmöglichkeit im Hinterkopf, wodurch ich vielleicht vier Fünftel der Möglichkeiten gleich knicken könnte... ach verdammt, jetzt investiere ich doch noch Zeit.

Ich schicke Dir schonmal die Lösung, dann kannst Du selbst messen. Der Prozessor ist ein Core I7 950 mit 3.07GHz, also doch schon ziemlich kräftig.

Und mache mal bitte eine offizielle Ansage: soll ich _BitScanForward() und _BitScanReverse() ersetzen oder kann ich die drinlassen? Die werden relativ direkt auf Prozessorbefehle abgebildet und machen das Finden des höchsten bzw. niedrigsten Bits zu einer O(1)-Aktion - ein substanzieller Teil meines Tricks basiert auf diesem Phänomen :-)

[edit]Ok, sorry, BlueCobold hat ja Recht, das ist alles schon deutlich gesagt. Ich baue die Intrinsics aus.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 297

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

32

11.02.2013, 20:07

Jetzt hast du mich neugierig gemacht.
Bin noch nicht dahinter gekommen, was du mit dem Bit-Scan anstellst ;)
Übrigens, auch ohne Intrinsics kannst du das doch in O(1) machen, schließlich gibt es ja nur 32 bzw. 64 Bits.

Ich möchte mir deinen Code aber lieber nicht ansehen - ich will nicht schummeln (obwohl ich natürlich außer Konkurrenz teilnehme).
Vielleicht versuche ich aber ganz am Ende noch aus allen Einsendungen die besten Ideen zu kombinieren.
David Scherfgens Website | Konzentrationstest Polizei

Schrompf

Alter Hase

Beiträge: 1 403

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

33

11.02.2013, 20:19

Zitat von »David Scherfgen«

Jetzt hast du mich neugierig gemacht.
Bin noch nicht dahinter gekommen, was du mit dem Bit-Scan anstellst ;)

Och, da ist kein Wunderwerk dahinter. Ich habe einfach die Kollisionskarte als Bitmuster abgelegt. Auf die Art werden manche der Tests, wie weit ein Spielstein rutschen kann, so einer Ermittlung des niedrigsten bzw. höchsten gesetzten Bits, wofür es ja so freundliche Intrinsics gibt :)

Zitat

Übrigens, auch ohne Intrinsics kannst du das doch in O(1) machen, schließlich gibt es ja nur 32 bzw. 64 Bits.
Wie denn? In dem Fall ist eine Zeile 16Bit, das könnte ich notfalls noch als Tabelle abbilden, auch wenn bei Tabellen jenseits der FirstLevelCache-Größe kaum Performance zu erwarten ist. Aber bei 32Bit wüsste ich nicht, wie das in O(1) machbar sein sollte.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

Evrey

Treue Seele

Beiträge: 246

Beruf: Weltherrscher

  • Private Nachricht senden

34

11.02.2013, 20:33

Das Stichwort ist "Bit Twiddle Hack". Da gibt es Tricks für allen Scheiß, auch um Branches zu sparen, was die BPU entlastet.

C-/C++-Quelltext

 
1
2
3
4

int main(int _argc, char** _argv) noexcept {
  asm volatile("lock cmpxchg8b %eax");
  return 0;
} // ::main
(Dieses kleine Biest vermochte einst x86-Prozessoren lahm zu legen.)

=> Und er blogt unter Hackish.Codes D:

Delop

Alter Hase

Beiträge: 610

  • Private Nachricht senden

35

11.02.2013, 20:35

Schrompf

Alter Hase

Beiträge: 1 403

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

36

11.02.2013, 20:40

Joa, die Seite habe ich schon in den Bookmarks. Nur leider ist auch da - prinzipiell bedingt - die Bestimmung des niedrigsten/höchsten Bits eine O(log n)-Operation. Besser als das wird es nur mit Tabellen oder halt Intrinsics. Nuja... egal. Das eigentliche Wunderwerk passiert eh woanders.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

Helmut

5x Contest-Sieger

Beiträge: 691

Wohnort: Bielefeld

  • Private Nachricht senden

37

11.02.2013, 20:41

Zitat von »Schrompf«

Hab jetzt mit 2h Zeitaufwand eine Lösung gebastelt, die erstmal eine plumpe Breadth First-Suche über alle Zugmöglichkeiten macht. Damit komme ich schonmal auf 17,5ms für die erste Map und auf 370ms für die dritte Map.

Nicht übel :) Meine Werte sind zur Zeit viermal so hoch, aber ich hoffe mal das liegt nur an meiner lahmen CPU :)
Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 297

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

38

11.02.2013, 20:45

Zitat von »Schrompf«

Nur leider ist auch da - prinzipiell bedingt - die Bestimmung des niedrigsten/höchsten Bits eine O(log n)-Operation.

Ich behaupte mal, dass selbst folgender naiver Ansatz in O(1) läuft:

C-/C++-Quelltext

 
1
2
3
4
5
6

int highestBit(uint32_t x)
{
    int result = -1;
    for(int i = 0; i < 32; ++i) if(x & (1 << i)) result = i;
    return result;
}
David Scherfgens Website | Konzentrationstest Polizei

Schrompf

Alter Hase

Beiträge: 1 403

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

39

11.02.2013, 21:05

Gerade ausprobiert. Die lineare Bittest-Schleife anstatt der Intrinsics hat meine Zeiten nahezu verdoppelt :-( Auf zu den Bithacks.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

BlueCobold

Community-Fossil

Beiträge: 10 859

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

40

11.02.2013, 21:10

Zitat von »Schrompf«

[edit]Ok, sorry, BlueCobold hat ja Recht, das ist alles schon deutlich gesagt. Ich baue die Intrinsics aus.

Ich bezog mich eigentlich auf das Problem des Rückwärts-Tracens, nicht auf die Intrinsics ;)
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Werbeanzeige

Ähnliche Themen