C++ Wortsuche
-
@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 2
Glaub 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 2
meinte.
-
@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.935168
50000x50000 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 (mitdirection
als 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.
-
@Th69 Die Zeichen vergleichen in verschiedenen Richtungen ist überhaupt kein Problem.
-
Glaubst du wirklich, daß dein Code von einem Anfänger verstanden wird (erinner dich mal an deine eigenen Anfänge)?
Also selbst ich verstehe nicht auf Anhieb, was deine Funktionfind_word
genau macht (und wozu z.B. die<=
Abfragen auf die Richtung sind?).Für ähnliche Aufgaben (z.B. für "Vier gewinnt") habe ich eine Funktion, welche je Dimension einen Richtungsparameter (-1, 0, 1) als Offset bekommt.
Gerade für Algorithmen hat es mir geholfen, während des Studiums funktionale Programmierung gelernt zu haben, so daß es nur auf die passende Kombination von (Teil-)Funktionen ankommt (und anschließend verallgemeinert man möglichst diese Funktionen um die benötigten, d.h. konkret verwendeten, Parameter).
-
@Th69 sagte in C++ Wortsuche:
Glaubst du wirklich, daß dein Code von einem Anfänger verstanden wird (erinner dich mal an deine eigenen Anfänge)?
Ich habe das Ding als Reaktion auf @hustbaer geschrieben weil ich argumentieren wollte daß die Aufgabe für Anfänger eben nicht simpel ist.
@Th69 sagte in C++ Wortsuche:
und wozu z.B. die <= Abfragen auf die Richtung sind?
Damit bereits gecheckte Richtungen nicht nochmal drankommen.
@Th69 sagte in C++ Wortsuche:
Für ähnliche Aufgaben (z.B. für "Vier gewinnt") habe ich eine Funktion, welche je Dimension einen Richtungsparameter (-1, 0, 1) als Offset bekommt.
Mein
strcmp()
.
-
@yahendrik sagte in C++ Wortsuche:
So richtig verstehe ich die Kritik an @Jockelx s Vorschlag nicht
Es ging nicht darum, ob das im Prinzip sinnvoll ist (das ist es), sondern ob es in dem Anfänger-Grundgerüst sinnvoll ist.
Ich hatte einfach die Idee: "Finde Anfangsbuchstaben und gucke dann in alle Richtungen".
Aber jetzt in Pseudo-Code gegossen gebe ich @hustbaer recht: Ist einfach mehr und daher komplexer.