Existiert eine solche Datenstruktur?

Question

Ich bin auf der Suche nach einer Datenstruktur, die so schnell wie eine einfache Liste sortiert werden kann und die Elemente auf die folgende Weise entfernen können. Lassen Sie uns sagen, dass wir eine Liste wie diese haben:

[{2,[1]}, 
{6,[2,1]}, 
{-4,[3,2,1]}, 
{-2,[4,3,2,1]}, 
{-4,[5,4,3,2,1]}, 
{4,[2]}, 
{-6,[3,2]}, 
{-4,[4,3,2]}, 
{-6,[5,4,3,2]}, 
{-10,[3]}, 
{18,[4,3]}, 
{-10,[5,4,3]}, 
{2,[4]}, 
{0,[5,4]}, 
{-2,[5]}] 

heißt eine Liste mit Tupeln (dies ist Erlang-Syntax). Jedes Tupel enthält eine Nummer und eine Liste, die die Mitglieder einer Liste enthält, die zur Berechnung der vorherigen Nummer verwendet wurde. Was ich mit der Liste machen möchte, ist folgendes. Zuerst, Sortieren es, dann nehmen Sie den Kopf der Liste, und schließlich sauber die Liste. Mit sauber Ich meine, alle Elemente aus dem Schwanz zu entfernen, die Elemente enthalten, die im Kopf sind, oder mit anderen Worten, alle Elemente aus dem Schwanz, die Kreuzung mit Kopf ist nicht leer. Zum Beispiel nach dem Sortieren des Kopfes ist {18,[4,3]}. Im nächsten Schritt alle Elemente der Liste zu entfernen, die 4 oder 3, das heißt die resultierende Liste enthalten soll diese sein:

[{6,[2,1]}, 
{4,[2]}, 
{2,[1]}, 
{-2,[5]}] 

Der Prozess folgt mit dem neuen Kopf zu nehmen und wieder reinigen, bis die ganze Liste verbraucht wird. Beachten Sie, dass, wenn der Bereinigungsvorgang die Reihenfolge beibehält, die Liste nicht bei jeder Iteration neu sortiert werden muss.

Der Engpass hier ist der saubere Prozess. Ich brauche eine Struktur, die es mir ermöglicht, schneller zu reinigen als jetzt.

Kennt jemand eine Struktur, die dies auf effiziente Weise ermöglicht, ohne die Reihenfolge zu verlieren oder zumindest eine schnelle Sortierung zu ermöglichen?

Answer 1

Ja, können Sie schneller als diese. Ihr Problem besteht darin, dass Sie die zweiten Tupelmitglieder als Listen darstellen. Sie zu suchen ist mühsam und ziemlich unnötig. Sie sind alle zusammenhängenden Teilstrings von 5..1. Sie könnten sie einfach als ein Tupel von Indizes darstellen!

Und in der Tat brauchen Sie nicht einmal eine Liste mit diesen Indextupel. Setzen Sie sie in einem zweidimensionalen Feld rechts an der Position der jeweiligen Tupel gegeben, und Sie erhalten eine triangular array:

h\l| 1 2 3 4 5 
---+---------------------- 
1 | 2 
2 | 6 2 
3 | -4 -6 -10 
4 | -2 -4 18 2 
5 | -4 -10 -10 0 -2 

Statt die Daten in einem zweidimensionalen Array zu speichern, möchten Sie vielleicht speichern sie in einem einfachen Array mit etwas Index-Magie, um die dreieckige Form zu berücksichtigen (wenn Ihre Programmiersprache nur rechteckige zweidimensionale Arrays zulässt), aber das hat keinen Einfluss auf die Komplexität.

Dies ist die gesamte Struktur, die Sie brauchen, um die "Liste" schnell zu filtern, indem Sie einfach die Dinge nachschlagen.

Stattdessen erste Sortier- und immer den Kopf, iterieren wir einfach einmal durch die ganze Struktur der maximale Wert und seine Indizes zu finden:

max_val = 18 
max = (4, 3) // the two indices 

Der Filter ist ganz einfach. Wenn wir keine Listen (not (any (substring `contains`) selection)) oder Sätze (isEmpty (intersect substring selection)) verwenden, sondern Tupel, dann ist es nur sel.high < substring.low || sel.low > substring.high.Und wir brauchen nicht einmal die ganze dreieckigen Array zu durchlaufen, können wir einfach Iterierte die higer und die unteren Dreiecke:

result = [] 
for (i from 1 until max[1]) 
    for (j from i until max[1]) 
     result.push({array[j][i], (j,i)}) 
for (i from max[0] until 5) 
    for (j from i until 5) 
     result.push({array[j+1][i+1], (j+1,i+1)}) 

Und Sie haben die Elemente, was Sie brauchen:

[{ 2, (1,1)}, 
{ 6, (2,1)}, 
{ 4, (2,2)}, 
{-2, (5,5)}] 

Jetzt Sie müssen nur das sortieren und Sie haben Ihr Ergebnis.

---

Tatsächlich wird die Gesamtkomplexität mit der Dreiecksanordnung nicht besser. Sie haben immer noch O(n) aus dem Erstellen der Liste und der Suche nach dem Maximum. Ob Sie in O(n) filtern, indem Sie für jedes Teilzeichenkettentupel testen, oder in O(|result|) durch intelligente Auswahl filtern, spielt keine Rolle mehr, aber Sie haben speziell nach einem schnellen Reinigungsschritt gefragt. Dies kann in der Realität nützlich sein, wenn die Daten groß sind oder wenn Sie mehrere Bereinigungen durchführen müssen.
Das einzige, was die Gesamtkomplexität beeinflusst, ist, nur das Ergebnis zu sortieren, nicht die gesamte Eingabe.

Answer 2

Ich frage mich, ob Ihre ursprüngliche Datenstruktur als eine Adjazenzliste für eine gerichtete Grafik angesehen werden kann? Z.B;

{2,[1]}, 
{6,[2,1]} 

bedeutet, dass Sie diese Knoten und Kanten haben;

node 2 => node 1 
node 6 => node 2 
node 6 => node 1 

So kann Ihre Frage umgeschrieben werden als;

Wenn ich einen Knoten finde, der mit den Knoten 4 und 3 verknüpft ist, was passiert dann mit dem Graph, wenn ich die Knoten 4 und 3 lösche?

Ein Ansatz wäre, eine Adjazenzmatrix zu erstellen; eine NxN-Bitmatrix, wobei jede Flanke das 1-Bit ist. Dein Problem wird jetzt;

setzen Sie jedes Bit in der 4-Zeile und jedes Bit in der 4-Spalte auf Null.

Das bedeutet, dass in diesem gelöschten Knoten keine Verbindung hergestellt wird.

Als Optimierung ein Bit-Array der Länge N beibehalten. Das Bit wird gesetzt, wenn der Knoten nicht gelöscht wurde.Also, wenn Knoten 1, 2, 4 und 5 sind 'live' und 3 und 6 'gelöscht', das Array wie

sieht

[1,1,0,1,1,0] 

Jetzt löschen '4', die Sie gerade das Bit löschen;

[1,1,0,0,1,0] 

Wenn Sie das Löschen getan, gehen durch die Adjazenzmatrix, aber jede Kante ignorieren, die in einer Zeile oder Spalte mit 0 Satz codiert wird.

Vollständiges Beispiel. Lassen Sie uns sagen Sie

[ {2, [1,3]}, 
    {3, [1]}, 
    {4, [2,3]} ] 

haben, dass die Adjazenzmatrix

1 2 3 4 
1 0 0 0 0 # no entry for 1 
2 1 0 1 0 # 2, [1,3] 
3 1 0 0 0 # 3, [1] 
4 0 1 1 0 # 4, [2,3] 

und die Maske löschen

[1 1 1 1] 

ist der Knoten 2, ändern Sie einfach die Maske;

[1 0 1 1] 

nun die Struktur, um herauszufinden, Pseudo-Code wie:

rows = [] 
for r in 1..4: 
    if mask[r] == false: 
    # this row was deleted 
    continue; 

    targets = [] 
    for c in 1..4: 
    if mask[c] == true && matrix[r,c]: 
     # this node wasn't deleted and was there before 
     targets.add(c) 

    if (!targets.empty): 
    rows.add({ r, targets}) 

Adjazenzmatrizen kann groß werden - es ist NxN Bits, nachdem alle - diese so wird nur besser auf kleinen, dichten Matrizen, nicht große, spärliche.

Ist dies nicht groß ist, könnten Sie feststellen, dass es einfacher ist für Graphenalgorithmen Google als sie selbst erfinden :)