Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Geschwindigkeitsoptimierung StringList


Bergmann89 - Mi 20.10.10 22:05
Titel: Geschwindigkeitsoptimierung StringList
Hey,

ich hab zur Zeit ein Problem wo ich nicht so richtig weiter weiß. Es geht darum, das ich Strings in eine StringList schreiben will. Die Strings sind alle genau 13-Zeichen lang. Jetzt gibt es aber die Bedingung, das ein neuer String der in die Liste eingetragen werden soll mind. x unterscheidliche Zeichen zu allen anderen in der Liste gespeicherten Strings haben muss. Da aber ca. 1Mio Strings eingetragen werden müssen dauert das Ganze auch entsprechend lange. Jetzt hab ich mir überlegt, wie man das alles optimieren könnte und da scheiter ich grad dran. Mir ist die Idee gekommen eine Hashmap zu nutzen, aber ich bin mir nicht ganz sicher ob das mein Problem löst, und ich bin auch noch nicht so bewandert in der Benutzung von Hashmaps. Aus diesem Grund wollt ich hier erstmal fragen ob das der richtige Weg ist, oder ob es noch effektivere Möglichkeiten gibt.

MfG & Thx Bergmann


Gausi - Mi 20.10.10 22:49

Ich sehe jetzt nicht, wie da eine Hashmap helfen könnte :gruebel:

Was bedeutet denn genau "mind. x unterscheidliche Zeichen"? Meine Idee wäre, die eingefügten Strings zusätzlich in einer Art DAWG (directed acyclic word graph) zu speichern. Da sind die Knoten des Graphen Buchstaben, und Wege von der Wurzel des Graphen/Baumes naach unten bilden die Strings, die schon eingefügt sind. Bei einem neuen String kann man dann relativ schnell feststellen, ob das neue Wort schon drin ist oder nicht.
Aber wie das mit den unterschiedlichen Zeichen genau zu modifizieren ist, weiß ich auch noch nicht so genau...


elundril - Mi 20.10.10 22:55

user profile iconGausi hat folgendes geschrieben Zum zitierten Posting springen:
Ich sehe jetzt nicht, wie da eine Hashmap helfen könnte :gruebel:

Was bedeutet denn genau "mind. x unterscheidliche Zeichen"? Meine Idee wäre, die eingefügten Strings zusätzlich in einer Art DAWG ...


Yo Dawg, we heard you like Dawgs so we put a Dawg in a Dawg so you can look at Dawg while your looking at Dawg. :mrgreen:

SCNR.

lg elundril


Gausi - Mi 20.10.10 23:01

Also die Jugend von heute versteh ich nicht... :gruebel:

Ich meinte auf jeden Fall so einen DAWG [http://en.wikipedia.org/wiki/Directed_acyclic_word_graph].


Bergmann89 - Mi 20.10.10 23:17

Hey,

so ne ähnliche Idee hatte ich auch, aber mein Gedankengang endete wie deiner dabei das ganze auf mein Problem zuzuschneidern. Hier nochma n kleines Beispiel (stark vereinfacht).
Strings die eingefügt werden sollen: (List1)
aaaaaa
aaaabb
abaabb
der unterschied muss mindestens 2 Zeichen betragen (also x = 2)

Quelltext
1:
2:
3:
4:
5:
für alle Einträge in List1 (Schleife1)
  für alle Einträge in List2 (Schleife2)
    wenn unterschiedliche Zeichen < x, dann...
      beende Schleife2 und starte mit nächstem Eintrag in Schleife 1
  übernimm Eintrag in List2

List2 wäre dann wie folgt:
aaaaaa
aaaabb

als 1. kommt aaaaaa in die List2, is ja klar weil es keine Strings zum vergleich in der Liste gibt. Dann kommt auch aaaabb in List2, weil es mind. 2 Zeichen Unterscheid zu aaaaaa hat (nämlich die 2 b). Dann wird abaabb geprüft, hat mehr als 2 unterschiedliche Buchstaben zu aaaaaa also weiter. Beim Vergleich von abaabb mit aaaabb ist aber nur ein Zeichen anders, somit erfüllt abaabb die Bedingung nicht und kommt nicht in die List2...

ich schlaf erstma ne Runde dadrüber.

gn8 Bergmann


Gausi - Do 21.10.10 10:38

Um mal bei der Idee zu bleiben: Du könntest den Dawg beim Einfügen aufbauen. Beim Einfügen des nächsten Strings startest du in dem Baum eine Tiefensuche. Dabei zählst du einen Zähler hoch, wenn du eine "falsche Kante" entlangläufst. Wenn der Zähler bei 2 ist, kannst du den Tiefensuchdurchlauf in diesem Teilbaum abbrechen - die Strings in diesem Teil des Baumes sind alle um mindestens 2 Zeichen verschieden. Dann gehst du in der Rekursion einen Schritt nach oben, verringerst dabei ggf. wieder den Zähler und machst in dem nächsten Ast weiter. Wenn du an einem Blatt in dem DAWG ankommst, und der Zähler ist kleiner als 2, dann hast du bereits ein ähnliches Wort in deiner Liste. Die Suche kann dann abgebrochen und das Wort verworfen werden.


Bergmann89 - Do 21.10.10 11:51

Hey,

gut, das sollte funktionieren, ich werd das heute mal umsetzten. Bleibt dann nur zu hoffen, das diese Methode schneller ist als die jetzige... Ich halt euch auf dem laufenden.

MfG Bergmann


Kha - Do 21.10.10 13:39

Ist "n unterschiedliche Zeichen" nun positionsunabhängig gemeint oder nicht :nixweiss: ?


Gausi - Do 21.10.10 13:50

So ganz sicher bin ich mir da auch noch nicht, für meine Idee bin ich einfach mal von der Hamming-Distanz [http://de.wikipedia.org/wiki/Hamming-Distanz] ausgegangen. Wenn also an der x-ten Position in den beiden Strings zwei unterschiedliche Zeichen stehen, dann ist das "ein Unterschied".

Also

Quelltext
1:
2:
3:
4:
5:
6:
7:
abcdef
bcdefa
 Unterschied = 6

abcdef
abcfff
  Unterschied = 2


Lemmy - Do 21.10.10 14:06

Hi,

bevor du jetzt die Tastatur quälst: Delphi F1 und THashedStringList eingeben:

Zitat:

Beschreibung

Ein THashedStringList-Objekt ist eine Stringliste, die intern eine Hash-Tabelle verwendet, um die Suche nach Strings zu beschleunigen. Es wird intern von TMemIniFile verwendet, um die Strings in einer INI-Datei zu verwalten. Das Objekt kann jedoch wie jede andere Stringliste genutzt werden. Insbesondere bei Listen mit einer großen Anzahl von Strings kann die Leistung durch die Verwendung der Klasse THashedStringList anstelle von TStringList optimiert werden.


sprich tausch mal TStringList durch THashedStringlist aus und schau ob dir die Performance ausreicht....

cu


jaenicke - Do 21.10.10 14:09

Was soll die denn hier in diesem Fall für Geschwindigkeitsvorteile bringen? :gruebel:


Lemmy - Do 21.10.10 14:34

Asche auf mein Haupt! Ich habe überlesen, dass sich die Strings in X Zeichen unterscheiden müssen und nicht nur einfach unterschiedlich sein müssen...

Grüße


Flamefire - Do 21.10.10 15:27

In dem Fall würde ich sogar auf die Stringlist verzichten und ein ähnliches Control schreiben (vl von TList ableiten) dass intern NUR den Baum verwendet. Da ja schon alles drin.


Thorsten83 - Fr 22.10.10 10:42

Darf man erfahren wie viel das gebracht hat? :)


Bergmann89 - Fr 22.10.10 14:51

Hey,

noch nix. Bin noch nich dazu gekommen. Werd ich heut abend/nacht machen oder morgen. Mal sehen. Aber auf alle Fälle dieses WE. Ich sag bescheid wenns funktioniert.

MfG Bergmann.


Bergmann89 - Sa 23.10.10 03:14

Hey,

habs soweit fertig und der Unterschied zur normalen Liste ist seeeehr groß^^
Das neue läuft mit x = 4 (mind. 4 Zeichen Unterschied) mit knapp 19sec, das alte hat mehr als 100sec gebraucht!!!
Hier der Code, wenn sich jmd dafür interessiert:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//püft ob der String mind x unterschiednliche Zeichen zu allen anderen Strings im Baum hat
//x = fMinCharDif --> property MinCharDif
//@p: Zeiger auf den String, der geprüft werden soll;
//@result: TRUE, wenn Sring gültig ist und die Bedingungen erfüllt; 
function TStringTree.CheckCharCountDif(p: PAnsiString): Boolean;

  function Check(d, Count: Integer; Item: PStringTreeItem): Boolean;
  var
    c: Byte;
  begin
    result := True;
    if (d > 13or not Assigned(Item) then begin
      if d > 13 then
        result := False;
      exit;
    end;

    if (p^[d] <> Item^.Value) and (d > 0then
      inc(Count);

    if Count >= fMinCharDif then
      exit;

    if d = 0 then
      c := Ord(p^[d+1]) - $30
    else
      c := Ord(p^[d]) - $30;
    case c of
      1begin
        result := Check(d+1, Count, Item^.Children[0]);
        if result then
          result := Check(d+1, Count, Item^.Children[2]);
      end;
      0begin
        result := Check(d+1, Count, Item^.Children[1]);
        if result then
          result := Check(d+1, Count, Item^.Children[2]);
      end;
      2begin
        result := Check(d+1, Count, Item^.Children[0]);
        if result then
          result := Check(d+1, Count, Item^.Children[1]);
      end;
    end;
    if result then
      result := Check(d+1, Count, Item^.Children[c]);
  end;

begin
  result := Check(00, fValues);
end;
Das ist jetz natürlich auf mein Problem zugeschnitten (Stringlänge 13 Zeichen; Zeichen nur '1', '0' und '2'), sollte aber nich so schwer sein, das auch auf allgemeine Sachen zu übertragen.
Ich überleg auch schon die ganze Zeit, wie man das evtl auf mehrere Thread verteilen könnte, aber das wird wohl nich gehen, weil er ja dauernt auf den Baum zugreift. Oder hat jmd ne Idee dazu (so großartig hab ich mit Threads noch nich gearbeitet).

MfG & gn8 Bergmann.


Kha - Sa 23.10.10 15:40

user profile iconBergmann89 hat folgendes geschrieben Zum zitierten Posting springen:
Ich überleg auch schon die ganze Zeit, wie man das evtl auf mehrere Thread verteilen könnte, aber das wird wohl nich gehen, weil er ja dauernt auf den Baum zugreift.
Gleichzeitiges Suchen im und Ändern des Graphen (kein Baum, falls du wirklich einen DAWG und keinen Trie benutzt ;) ) wird natürlich nicht funktionieren, das stimmt. Aber deine Check-Methode selbst lässt sich als Divide-and-Conquer-Algorithmus wunderbar parallelisieren [http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm#Parallelism], such einfach mal nach einem parallelen Quicksort als Beispiel.
Sollte sich herausstellen, dass dabei die einzelnen Aufgaben zu "fine-grained" sind, also der Thread-Overhead überwiegt, kannst du auch mehrere einzufügende Strings erst einmal in einem Batch sammeln. Für jeden String suchst du im alten DAWG, überprüfst dann noch die Ähnlichkeit zu den restlichen Strings im Batch und fügst am Ende alle (die den Test bestanden haben) auf einmal in den Graph ein. Die ersten beiden Schritte lassen sich dabei problemlos parallelisieren.


BenBE - So 31.10.10 02:36

Die Sache bzgl. Sammeln mehrerer Strings dürfte sogar recht vorteilhaft sein, weil man dann wirklich schon mal vorfiltern kann und dadurch die wirklichen Schreiboperationen im DAWG/Trie stark verringern kann. Also in parallel X String vorfiltern und danach single-threaded die verbliebenen Kandidaten gegen die vorhandene Liste filtern und einfügen.

Die generalisierte Variante könnte für Multithread-Filtering auch einfach mit nem Task-Stack (oder Prio-Queue) arbeiten, bei dem die Rekursionsschritte auf dem Stack abgelegt werden. Hilfreich könnten hier theoretisch auch Fibers sein, weil dann das Switching zwischen den einzelnen Aufgaben um einiges beschleunigt wird. (Kleinerer Context Switch Overhead).


Tranx - So 31.10.10 04:23

user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Die Sache bzgl. Sammeln mehrerer Strings dürfte sogar recht vorteilhaft sein, weil man dann wirklich schon mal vorfiltern kann und dadurch die wirklichen Schreiboperationen im DAWG/Trie stark verringern kann. Also in parallel X String vorfiltern und danach single-threaded die verbliebenen Kandidaten gegen die vorhandene Liste filtern und einfügen.

Die generalisierte Variante könnte für Multithread-Filtering auch einfach mit nem Task-Stack (oder Prio-Queue) arbeiten, bei dem die Rekursionsschritte auf dem Stack abgelegt werden. Hilfreich könnten hier theoretisch auch Fibers sein, weil dann das Switching zwischen den einzelnen Aufgaben um einiges beschleunigt wird. (Kleinerer Context Switch Overhead).


Ist doch nett, was ich hier lesen kann, doch allein, mir fehlt der Sinn dessen, was der Autor mir sagen will.


jaenicke - So 31.10.10 06:56

user profile iconTranx hat folgendes geschrieben Zum zitierten Posting springen:
Ist doch nett, was ich hier lesen kann, doch allein, mir fehlt der Sinn dessen, was der Autor mir sagen will.
Solange es user profile iconBergmann89 weiß... :mrgreen: :P

Aber was fehlt dir denn? Die Priority Queue [http://de.wikipedia.org/wiki/Vorrangwarteschlange]? Oder Fibers [http://www.delphi-forum.de/viewtopic.php?t=94597]?


Tranx - So 31.10.10 13:04

Ich weiß nicht, ob jeder weiß, was mit dieser Anhäufung von Spezialbegriffen in dem besagten Text gemeint ist. Ich finde es wenig hilfreich, solche Texte zu schreiben, denn es setzt ja voraus, dass der Empfänger weiß, was mit dem Inhalt gemeint ist. Und das - mit Verlaub - kann man bei Laien nicht immer erwarten. Oder sehe ich das falsch?


jaenicke - So 31.10.10 13:07

Es steht doch jedem frei konkrete Fragen zu stellen, wenn etwas unklar ist. Und zu den Stichworten lässt sich ja auch viel finden, wenn man diese noch nicht kennen sollte. :nixweiss:

// EDIT:
Und im Gegenteil, gerade wenn man das noch nicht kennt, ist es erst recht hilfreich, wenn man das dadurch kennenlernen kann. Dass man sich ein wenig damit beschäftigen muss, ist klar.