3. C++ Wortsuche

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.

    0

  • @hustbaer sagte in C++ Wortsuche:

    transpose matrix

    Also den Input rumdrehen anstatt die Suchrichtung zu ändern?

    0

  • @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.

    1. 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.
    2. Wir suchen immer horizontal, vorwärts. Also aus Speicher-Sicht immer in "+1" Richtung.
    3. 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.

    0 1 Antwort

  • @hustbaer ja, das klingt schneller.

    0
  • Y

    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.

    0
    J
     1 Antwort

  • Ich würde eher ersteinmal verschiedene Such-Funktionen je Dimension (horizontal, vertikal) erstellen.
    Und darauf aufbauend eine allgemeine (mit direction 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.

    0 1 Antwort

  • @Th69 Die Zeichen vergleichen in verschiedenen Richtungen ist überhaupt kein Problem.

    0

  • 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 Funktion find_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).

    0 1 Antwort

  • @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().

    0
  • J

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

    0
Anmelden zum Antworten