C++ Wortsuche
-
@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.