Gibt es eine natürliche Parallele zu rot-schwarzen Bäumen mit ähnlichen oder gar nicht so schlimmen Eigenschaften für Aktualisierungen bei angemessener Arbeitseffizienz?
Was können wir allgemein am besten für die parallele Suche mit Updates tun?
ds.algorithms
ds.data-structures
dc.parallel-comp
concurrency
dynamic-algorithms
Suresh Venkat
quelle
quelle
Antworten:
Nach allem, was ich sagen kann, müssen bei Strategien die Gleichgewichtsbedingungen gelockert und die Aktualisierungen in Bursts neu ausgeglichen werden. Hier ist ein Artikel von Hanke et al., 1997 [PDF] , der sich meiner Meinung nach auf ihre Technik konzentriert, Aktualisierungsvorgänge so zu aggregieren und aufzulösen, dass sie gleichzeitig ausgeführt werden können.
quelle
Ich denke, Sie finden interessante Antworten in Okasakis Buch Purely Functional Data Structures . In diesem Buch werden viele Datenstrukturen gezeigt, so dass jedes Update nicht teuer ist (normalerweise dauert es nur eine konstante oder logarithmische Zeit).
Angenommen, "d" ist eine Struktur kurz vor dem Zeitpunkt, an dem Sie das Gleichgewicht wieder herstellen müssen. In einer rein funktionalen Datenstruktur haben Sie persistente Datenstrukturen, daher können Sie Dinge zu "d" hinzufügen und müssen mal neu balancieren . Dies ist der Grund, warum amortisierte Komplexität in dieser Einstellung nicht funktioniert, und er hat einen anderen Weg gefunden, um einen guten Algorithmus zu erhalten, bei dem jeder Schritt mit Updates nicht teuer ist.n n
quelle