C++ Wortsuche
-
@hustbaer sagte in C++ Wortsuche:
Genau so wie die "restartable" Suchfunktion nicht gefordert wurde und den Code unnötig kompliziert macht.
Wie vermeidest Du doppelt und dreifach dasselbe zu finden?
-
@hustbaer sagte in C++ Wortsuche:
Und die Optimierung ist nichtmal sinnvoll implementiert. Sinnvoller wäre es gleich die Start- und Endwerte der Schleifen anzupassen.
???
-
@Jockelx sagte in C++ Wortsuche:
@hustbaer sagte in C++ Wortsuche:
Das ist aber eine Optimierung
Ja und? Darf ja auch eine sein. Die Optimierung ist aber nicht der Grund für die Änderung, sondern weil ich das anschaulicher finde. Ist das so schwer zu verstehen?
Ja
Also auf die Idee dass man das anschaulicher finden könnte wäre ich nicht gekommen. Und es sollte mMn. kein Grund sein es einzubauen. Wenn man es als Optimierung haben möchte, OK. Aber wenn einem die Optimierung egal ist, dann ist es ein Stück Code das genau keinen Sinn macht. Und Code der Teile enthält die keinen Sinn machen, finde ich persönlich nicht anschaulicher.
-
@Swordfish sagte in C++ Wortsuche:
@hustbaer sagte in C++ Wortsuche:
Genau so wie die "restartable" Suchfunktion nicht gefordert wurde und den Code unnötig kompliziert macht.
Wie vermeidest Du doppelt und dreifach dasselbe zu finden?
So:
for each X for each Y for each word for each direction if word starts here print out word, pos, directionWie soll da was doppelt oder dreifach gefunden werden?
-
@hustbaer Ok. 1:0. Darf mir meine Lösung trotzdem gefallen?
-
@Swordfish sagte in C++ Wortsuche:
@hustbaer sagte in C++ Wortsuche:
Und die Optimierung ist nichtmal sinnvoll implementiert. Sinnvoller wäre es gleich die Start- und Endwerte der Schleifen anzupassen.
???
Wenn...
- Meine Zeile 20 Zeichen lang ist
- Das gesuchte Wort 10 Zeichen lang ist
- Ich von Links nach Rechts suche
Wieso sollte ich dann die Schleife von X=0 bis X=19 laufen lassen, und dann in der Schleife immer prüfen ob X <= 10 ist? Das macht doch keinen Sinn. Dann lass ich gleich die Schleife nur von 0...10 laufen.
-
@hustbaer Ist eben die Frage ob man vorher anhand der Suchrichtung entscheidet oder nachher.
-
@Swordfish sagte in C++ Wortsuche:
@hustbaer Ok. 1:0. Darf mir meine Lösung trotzdem gefallen?
Sicher. Ich hab doch nicht behauptet dass deine Lösung irgendwie besonders schlecht wäre. Also bis auf den Range-Check den man eben effizienter machen kann -- wenn man ihn schon unbedingt optimieren will.
Ich sage nur man kann es viel einfacher machen wenn man einfach nur die Aufgabe machen möchte.
-
@hustbaer sagte in C++ Wortsuche:
Also bis auf den Range-Check den man eben effizienter machen kann -- wenn man ihn schon unbedingt optimieren will.
Kannst Du das bei mir mal einbauen, weil ehrlichgesagt stehe ich auf der Leitung.
-
@Swordfish sagte in C++ Wortsuche:
@hustbaer Ist eben die Frage ob man vorher anhand der Suchrichtung entscheidet oder nachher.
Richtig. OK, kann man so oder so machen. Was wirklich schneller ist müsste man vermutlich Benchmarken. Bei kleinen Matrizen die in den L1 passen vermutlich "meine" Variante. Bei grösseren ... keine Ahnung. Und wenn man wirklich optimieren will, muss man das sowieso nochmal ganz anders angehen.
-
@hustbaer sagte in C++ Wortsuche:
Und wenn man wirklich optimieren will, muss man das sowieso nochmal ganz anders angehen.
Optimal wäre wahrscheinlich "im Kreis" zu suchen:
4 3 X 1 2
-
@Swordfish sagte in C++ Wortsuche:
@hustbaer sagte in C++ Wortsuche:
Also bis auf den Range-Check den man eben effizienter machen kann -- wenn man ihn schon unbedingt optimieren will.
Kannst Du das bei mir mal einbauen, weil ehrlichgesagt stehe ich auf der Leitung.
Ich könnte, aber ich bin grad zu faul. Aber falls es darum geht: Es stimmt schon dass man dazu die Verschachtelung ändern müsste. Also du machst Word->Pos->Direction und das funktioniert natürlich nur mit Word->Direction->Pos.
-
-
@Swordfish sagte in C++ Wortsuche:
@hustbaer sagte in C++ Wortsuche:
Und wenn man wirklich optimieren will, muss man das sowieso nochmal ganz anders angehen.
Optimal wäre wahrscheinlich "im Kreis" zu suchen:
4 3 X 1 2Glaub ich nicht. Ich denke eher sowas in der Art:
check_h: for all rows for all possible start offsets for all words check extend word list by adding all words > 1 character in reserve check_h transpose matrix check_h
-
@hustbaer Da sind mir zu viele Fremdwörter die ich nicht verstehe. Ich glaube aber auch daß Du nicht verstanden hast was ich mit
@Swordfish sagte in C++ Wortsuche:
4 3 X 1 2meinte.
-
@hustbaer sagte in C++ Wortsuche:
transpose matrix
Also den Input rumdrehen anstatt die Suchrichtung zu ändern?
-
@Swordfish
Möglich dass ich es nicht genau verstanden habe. Aber ich bin mir trotzdem ziemlich sicher dass es langsamer sein wird als mein Vorschlag.Da sind mir zu viele Fremdwörter die ich nicht verstehe.
- Alle Wörter die länger als 1 Buchstabe sind nochmal rückwärts in die Wort-Liste aufnehmen. Dadurch können wir immer vorwärts suchen.
- Wir suchen immer horizontal, vorwärts. Also aus Speicher-Sicht immer in "+1" Richtung.
- Um dann vertikal suchen zu können spiegeln wir die Matrix an der Diagonale und suchen dann wieder horizontal.
Alternativ kann man auch nur jeweils eine Spalte in einen kompakten Zwischenspeicher kopieren und dann in diesem suchen.
Das ist viel günstiger was die Cache-Nutzung angeht. Wenn man nur nach einem Wort sucht, gewinnt man nichts damit. Aber wenn man nach mehr als einem Wort sucht, und die Matrix nicht mehr in den L1 Cache passt, dann gewinnt man dadurch einiges.
Also den Input rumdrehen anstatt die Suchrichtung zu ändern?
Ja, genau.
ps:
Alternativ kann man auch nur jeweils eine Spalte in einen kompakten Zwischenspeicher kopieren und dann in diesem suchen.
Es würde mich aber nicht wundern wenn es effizienter wäre wirklich die ganze Matrix zu transponieren. Das kann man nämlich effizienter machen als wenn man Spalte für Spalte aus dem Speicher in einen Zwischenpuffer liest.
-
@hustbaer ja, das klingt schneller.
-
So richtig verstehe ich die Kritik an @Jockelx s Vorschlag nicht. Die Daten müssen nur einmal durchlaufen werden, daher ist das doch naheliegend.
Nach den Vorschlägen hier habe ich mal ein wenig rumgespielt.
Gesucht werden immer drei Wörter, die immer an der gleichen Position sind:
https://i.imgur.com/kXg2tKe.png
0, 0 →
width-1, height/2 ←
width/2, height-1 ↑Die MT-Varianten laufen in 4 Threads (auf meinem betagten i7 mit 4 physischen Kernen). Die erste Variante sucht parallel in jeweils einer Richtung, die zweite teilt die Daten in 4 gleich große Bereiche auf.
50x50 --------------------------- Nacheinander: 0.000059 alle Richtungen: 0.000033 MT: 0.000235 MT (alle Richtungen): 0.000320 100x100 --------------------------- Nacheinander: 0.000244 alle Richtungen: 0.000128 MT: 0.000349 MT (alle Richtungen): 0.000259 500x500 --------------------------- Nacheinander: 0.006062 alle Richtungen: 0.003105 MT: 0.002605 MT (alle Richtungen): 0.001615 1000x1000 --------------------------- Nacheinander: 0.026402 alle Richtungen: 0.012442 MT: 0.010958 MT (alle Richtungen): 0.005402 10000x10000 --------------------------- Nacheinander: 6.184115 alle Richtungen: 1.142791 MT: 2.801702 MT (alle Richtungen): 0.439780 20000x20000 --------------------------- Nacheinander: 24.657569 alle Richtungen: 4.531628 MT: 12.044550 MT (alle Richtungen): 1.557231 30000x30000 --------------------------- Nacheinander: 61.878514 alle Richtungen: 10.184429 MT: 30.797580 MT (alle Richtungen): 3.93516850000x50000 habe ich abgebrochen.
Und die Rotation habe ich zwar probiert, aber mögliche Vorteile wurden anscheinend durch die Rotation selber zunichte gemacht. Eine sinnvolle (eben auch einfache) MT-Lösung ist mir da leider nicht eingefallen.
-
Ich würde eher ersteinmal verschiedene Such-Funktionen je Dimension (horizontal, vertikal) erstellen.
Und darauf aufbauend eine allgemeine (mitdirectionals Parameter), welche diese dann entsprechend aufruft.Wenn man eure Suchfunktion dann auch noch um diagonale Suche erweitern würde (wie man es von den "Wortsuche"-Rätseln in Kreuzworträtselheften kennt), würde der Code noch komplexer werden.
