Paralleler Algorithmus zum Konstruieren eines Trie?

Ein offensichtlicher Lock-Free-Algorithmus wäre:

1. Bucket: Sortiert die Eingabezeichenfolgen nach dem Präfix length- k (normalerweise k = 1, aber bei kleinen Alphabeten erhöhen Sie k ).
2. Konstruiere für jeden Buchstaben einen Trie, der den k Suffix aller Strings enthält, die mit diesem Buchstaben beginnen.
3. Verschmelzen Sie die Versuche aus dem vorherigen Schritt (wenn k = 1, fügen Sie einfach einen Stammknoten hinzu).

Unter der Annahme einer gleichmäßigen Verteilung von Präfixen kann dies eine lineare Beschleunigung bis zur Größe des Alphabets zur Potenz k ergeben.

Es ist mir gerade in den Sinn gekommen, dass dies gesperrt werden kann, indem atomare Test-and-Set-Operationen an den Zeigern statt an den Sperren verwendet werden. Insbesondere, wenn ein Thread einem Zeiger folgen möchte, macht es Folgendes:

1. Lesen Sie den Zeigerwert atomisch.
2. Wenn der Zeiger nicht null ist, folgen Sie ihm. Du bist fertig.
3. Ansonsten weise einen neuen Knoten zu.
4. Testen Sie den Zeiger atomisch auf Null und setzen Sie ihn auf den neuen Knoten, wenn er null ist.
5. (Anmerkung: Der Zeiger ist hier definitiv nicht Null. Entweder setzen wir ihn einfach oder er wurde von einem anderen Thread gesetzt).
6. Folge dem Zeiger.

Abhängig von der Hardware könnte dies viel schneller sein, da es den Aufwand für das ständige Sperren und Entsperren vermeidet und dafür sorgt, dass kein Thread ewig läuft.

Ein Nachteil ist, dass die Anzahl der involvierten Zuweisungen steigt, da mehrere Threads alle versuchen könnten, einen Knoten zuzuordnen, um den Trie an einer bestimmten Stelle zu setzen, aber nur einer kann ihn dort platzieren. Glücklicherweise kann dies durch die folgende Optimierung gemildert werden: Wenn ein Thread jemals einen Knoten unnötig zuweist, anstatt ihn sofort freizugeben, speichert er den Knoten nur im temporären Bereich. Wenn es später einen neuen Knoten zuweisen muss, kann es den zwischengespeicherten Knoten verwenden. Wenn nicht, kann es es am Ende befreien.

Hoffe, das hilft!

Nun, es gibt einen offenkundigen Kompromiss zwischen feiner VS-Grobgranularität von Festlegen einer Sperre für eine Menge von Knoten (anstatt einer).

Ein einfacher Weg, dies zu tun, ist über Hashing - haben Sie m verschiedene Sperren, und für jeden Knoten, den Sie zugreifen möchten, erwerben Sie die Sperre nummeriert hash(node) % m . Beachten Sie, dass dieser Ansatz im Wesentlichen eine Verallgemeinerung des vorgeschlagenen Ansatzes (mit perfektem Hashing und n == m ) und des seriellen Ansatzes (mit m == 1 ) ist.

Eine andere Sache, die verwendet werden könnte, ist optimistisches Design - wenn der Ansatz tatsächlich zunimmt die Leistung hängt natürlich von der Verteilung des Wörterbuchs und der Größe des Trie ab und kann sehr hilfreich sein, wenn Kollisionen eher selten sind (was bei einem Wörterbuch mit sehr langen Wörtern der Fall sein kann).
Die Idee ist, die Wörter einfach ohne Synchronisation zum Trie hinzuzufügen, und wenn Sie auf eine Kollision stoßen - rollen Sie zurück zum letzten bekannten stabilen Zustand (das erfordert natürlich eine Momentaufnahme der Daten und ist möglicherweise nicht machbar wenn wir über Datenströme sprechen, die nicht gespeichert werden können.

Abhängig davon, wie Ihr Wörterbuch aussieht, benötigen Sie die Sperren möglicherweise gar nicht, wenn Sie jeden Thread dazu bringen können, unabhängige Teilbäume zu erstellen. Wenn dies kein Online-Algorithmus ist, ordnen Sie die Wörter mit einem Präfix voran (erster Buchstabe, wenn Sie & lt; 26 Threads haben, erster und zweiter, wenn Sie mehr haben oder Sie wissen, dass die Daten nicht ausgeglichen sind, zum Beispiel 90% der Wörter beginnen mit A). Im Grunde wäre dies eine O (n) -Operation, bei der Sie einen Durchlauf durchführen, um zu zählen, wie viele Wörter es gibt, die mit einem gegebenen Buchstaben beginnen, dann einen Durchlauf, um zu sortieren (nach der Radix-Sortierung nach dem gewählten Präfix). Teilen Sie dann die Präfixe zwischen den Threads, und jeder Thread erstellt diese unabhängigen Subbäume. Schließlich muss ein Thread jeden dieser Teilbäume zum Stamm hinzufügen. Ich werde unten ein Beispiel durchgehen.

Ihr Wörterbuch:
Rinde
Apfel
Plätzchen
Und
Baby und Baby Mais
Blaues
Kuchen
Speck

Nach dem Sortieren:
Apfel
Und
Rinde
Baby und Baby Blaues
Speck
Mais
Plätzchen
Kuchen

Dann teilen wir Präfixe unter den Threads. Für dieses Beispiel haben wir 3 Threads, die die Präfixe [A] [B] [C] erhalten und die folgenden Bäume bilden:

Und dann hast du einen Thread, der diese an der Wurzel kombiniert:

Ich hoffe, das ergab einen Sinn.

Vorteile dieser Methode: Die Threads arbeiten im Wesentlichen unabhängig voneinander, und Sie haben nicht den Aufwand, sich mit dem Erwerben und Freigeben von Sperren befassen zu müssen.

Nachteile dieser Methode: Wenn Sie nichts über das Wörterbuch wissen, kann es zu einem schwerwiegenden Workload-Ungleichgewicht kommen, und im schlimmsten Fall (sagen wir, alle Wörter beginnen mit 'A') wird es im Grunde ein einzelner Thread, der einen Baum bildet. Es gibt ein paar Möglichkeiten, dies zu verbessern, zum Beispiel können Sie einige Prüfungen hinzufügen, wenn Sie so sortieren, dass die Arbeitslast schwerwiegend ist, wenn Sie mit einem einzelnen Buchstabenpräfix umgehen, um nach den ersten beiden Buchstaben zu suchen. t garantieren, dass es ausgeglichen ist.

Sie haben vielleicht auch untätige Threads, wenn Sie sagen, dass Sie 20 Threads haben und nach dem ersten Buchstaben sortieren, dann werden Sie 6 Threads haben, die zwei Unterbäume machen müssen, während 14 von ihnen die Hälfte der Zeit leer sind. Möglicherweise können Sie die Teilbäume weiter unterteilen, um damit umzugehen, aber das ist zusätzliche Zeit für einen Vorverarbeitungsschritt.

Wie auch immer, keine Garantie dafür, dass dies schneller ist als Ihre Methode, aber es ist etwas zu beachten.