Datenstruktur gesucht: schneller Random Access, Indizes unverändert nach Löschen, sequentiell

SeppJ

Hi,
ich arbeite derzeit an einem Projekt, das ich um eine neue Funktionalität erweitern muss. Bisher waren die Daten in zwei vectoren gehalten. Die Objekte in dem vector enthalten Verweise auf andere Objekte in dem vector, genauer gesagt leben in dem vector mehrere doppelt verkettete Listen. Der eine Vector, nennen wir ihn root , speichert die Anfänge der Listen, der andere ( data ) enthält die restlichen Elemente.
Das sieht dann Beispielsweise so aus:

root[0]   ->           data[0]   // Anfang von Liste 1
root[1]   ->           data[4]   // Anfang von Liste 2

data[0]   ->   data[1],root[0]   // nächstes Element und vorhergehendes
data[1]   ->   data[2],data[0]  
data[2]   ->   data[3],data[1]  
data[3]   ->           data[2]   // kein Nachfolger, letztes Element von Liste 1
data[4]   ->   data[5],root[1]  
data[5]   ->   data[6],data[4]  
data[6]   ->   data[7],data[5]  
data[7]   ->           data[6]   // letztes Element von Liste 2

Mit Verweisen meine ich dabei übrigens die Indizes der Elemente im Vector, keine Iteratoren.

Bisher wurde für die Speicherung der Daten ein Vector verwendet, weil

Zeiteffizienter random-access für die Primärfunktion des Programms EXTREM wichtig ist
Die Datenelemente für die Sekundärfunktionalität des Programms vorzugsweise sequentiell im Speicher liegen sollten

Nun stehe ich vor dem Problem: Für meine neue Funktionalität muss ich solche "Sublisten" hinzufügen und entfernen können. Hinzufügen ist ja kein Problem, aber es dürfte offensichtlich sein, dass das Entfernen Schwierigkeiten macht, denn wenn ich Elemente aus einem Vector lösche, werden die Verweise ungültig.

Ich suche also eine Datenstruktur mit folgenden Eigenschaften, nach Wichtigkeit sortiert:

Effizienter wahlfreier Zugriff
Indizes für besagten wahlfreien Zugriff werden beim Löschen von Elementen nicht geändert
Sequentiell (oder ohne großen Lücken) im Speicher

Und da fällt mir leider gar nichts ein, was da so richtig passt. Vorschläge? Man sollte noch sagen, dass immer ganze Listen aus dem Vectoren entfernt werden, falls dies hilft. Das Löschen der Listen kann aber natürlich auch elementweise erfolgen.

Mein jetziger Plan ist es, die Vectoren beizubehalten, dafür aber den Löschalgorithmus etwas cleverer zu gestalten, indem ich die Vorteile der doppelt verketteten Listen ausnutze. Wenn ich ein Element löschen will, würde ich daher so vorgehen:

(Verweise bei den Vor- und Nachfolgern des Löschkandidaten umändern. Entfällt bei mir, da ich gleich die ganze Liste lösche)
Das letzte Element des Vectors an die Stelle des zu löschenden Elementes kopieren
Die Vorgänger und Nachfolger des verschobenen Elementes anpassen
Das letzte Element des Vektors löschen

Da das Löschen von Listen relativ selten vorkommen wird, ist es egal, wenn die ganze Aktion etwas dauert.

Nexus

Wäre es nicht möglich, freigewordene Indizes abzuspeichern? Also dass die nachfolgenden Elemente bei einer Löschung nicht aufrücken. So bleiben Indizes gültig, und zusätzlich kopierst du weniger. Nach dem Löschen hast du Lücken, die wieder aufgefüllt werden können. Deren Indizes könntest du in einem Stack oder so speichern. Der Rest wie gehabt...

Kann aber auch sein, dass ich was komplett übersehe.

drakon

Wie eng ist das mit dem Wahlfreien Zugriff? Darf es gehashed sein?

Klingt eher nach einem Designproblem, als einem Problem der Datenstruktur.

SeppJ

@Nexus: Das war auch mein erster Gedanke. Was mich daran störte: Das Programm benötigt sowohl Iteration über alle Elemente als auch Zugriff bei welchem man sich die Liste entlanghangelt. Sofern ich nur die Listen entlang gehe, ist der Vorschlag ziemlich gut. Wenn ich aber den vector entlang gehe, muss ich immer prüfen, ob ich einen gültigen Index vorliegen habe. Entweder muss ich alle Stellen ändern, an denen ich über den vector iteriere (sind viele, wäre mühsam) oder der Elementzugriffsoperator müsste die Prüfung durchführen. In diesem Fall wäre jeglicher Zugriff ausgebremst und das wäre zeitlich nicht verantwortbar. Damit bliebe nur die Handarbeit, die ich natürlich eher vermeiden möchte. Immerhin wird im innersten Loop aber nicht sequentiell iteriert, von daher käme es laufzeitlich in Frage wenn ich nur die sequentiellen Stellen ändere.

@drakon: Zugriffszeit ist ziemlich kritisch. Ich habe noch nie mit hash-tables gearbeitet, weiß nicht wie schwer das wiegt. Ich habe die Profilerdaten jetzt gerade nicht vorliegen, aber ich meine, der innerste Loop verbringt mindestens 10-20% mit Zugriff auf die Vectorelemente. Eine Verlangsamung würde da schon arg reinhauen. Gesamtlaufzeit liegt im Bereich von Tagen bis Wochen. Was würdest du denn machen, wenn hashen in Frage käme? Der innerste Loop benutzt Listeniteration und gezielten Zugriff ungefähr zu gleichen Teilen.

@Janjan: Eigentlich ist das schon recht gut überlegt, finde ich. Da ist auch viel Designarbeit von den vorherigen Projektarbeitern reingeflossen. Beim bisherigen Programm muss man über die Daten sowohl sequentiell als auch in Listenreihenfolge iterieren können als auch einzelne Elemente direkt anspringen können. Das alles ungefähr zu gleichen Teilen. Da passt das bisherige Modell schon ganz gut. Und da das Programm parallel ist, ist die sequentielle Abspeicherung auch nicht verkehrt, da man dann mit MPI einfach den ganzen Datenblock verteilen kann, anstatt jedes Element einzeln. Ich bin aber natürlich gerne für Vorschläge offen, was man besser machen könnte.

Nexus

Mir fiele da eine spezielle Iterationsweise ein, um doch den Lückenansatz verfolgen zu können. Du könntest in jedem Vector-Element speichern, um wieviel ein Iterator vorrücken kann (also 1 + Anzahl der folgenden Lücken). Das ist verhältnismässig günstig und hat vor allem keinen Einfluss auf den Random Access.

Da deine Iterationen schon fix im Anwendercode stehen, ist dieser Ansatz natürlich etwas doof. Wie sehen die momentan aus? Iterierst du mit Indizes oder Iteratoren?

Von wo aus hast du überhaupt Random Access? Hauptsächlich aus den verketteten Listen selbst oder über die ganze Anwendung verstreut? Denn ohne Lücken musst du Elemente verschieben und Verweise (in dem Fall Indizes) neu setzen. Dürfte recht teuer sein, neben der benötigten Zeit auch vom Verwaltungsaufwand her. Wenn ich das richtig sehe, wird dieser Schritt mit deinem bisher vorgestellten Plan notwendig, oder?

Falls sowas vertretbar wäre, hättest du zwar einiges an Overhead und langsame Löschungen, dafür aber einen defragmentierten Container und sehr schnelle Iterationen und Wahlzugriffe.

hustbaer

@SeppJ:
Wenn ich das richtig verstehe geht es nur um den 2. Vektor, wo die "nicht-head" Listenelemente drinstehen. Soweit richtig?

Beim 1. Vektor mit den "nur-head" Elementen hast du ja immer das Problem, dass sämtliche Indexe sich ändern, sobald du was verschiebst. Oder geht es dir gerade um den, also um da Ersatz zu finden?

Den "nicht-head" Vektor könnte man vermutlich einfach durch den Heap ersetzen, also einfach zusammenhängende Arrays vom Heap anfordern. Bzw. auch viele kleine Vektoren.

Beim "nur-head" Vektor... pfuh. Einfach Löcher lassen? Das sequenzielle Drübergehen könnte man ja immer noch machen, indem man auch die Elemente im "nur-head" Vektor in einer doppelt verketteten Liste hält, und anstelle von "i+1" einfach den "next" Zeiger/Index verwendet.

Kann sein dass ich dich jetzt total falsch verstanden habe. Dei deinen Ausführungen ist mir nämlich nicht ganz klar auf welchen der beiden Vektoren du dich jeweils beziehst.

SeppJ

Nexus schrieb:

Mir fiele da eine spezielle Iterationsweise ein, um doch den Lückenansatz verfolgen zu können. Du könntest in jedem Vector-Element speichern, um wieviel ein Iterator vorrücken kann (also 1 + Anzahl der folgenden Lücken). Das ist verhältnismässig günstig und hat vor allem keinen Einfluss auf den Random Access.

Gute Idee.

Da deine Iterationen schon fix im Anwendercode stehen, ist dieser Ansatz natürlich etwas doof. Wie sehen die momentan aus? Iterierst du mit Indizes oder Iteratoren?

Es ist alles Indexbasiert, da es manchmal zu Reallokationen kommen kann und außerdem die Daten über mehrere Prozesse verteilt werden (und Iteratoren sind nicht austauschbar).

Von wo aus hast du überhaupt Random Access? Hauptsächlich aus den verketteten Listen selbst oder über die ganze Anwendung verstreut?

Verstreut. Das macht die Sache ja gerade so schwer . Zugriff erfolgt sowohl über Listen als auch über eine weitere Datenstrukturen die ebenfalls Indizes von Elementen gespeichert haben, die andere logische Untergruppierungen bilden. Und es wird auch häufig stumpf über alles iteriert. Diese externen Datenstrukturen müssten wohl auch angepasst werden, aber das ist im Grunde die gleiche Problemstellung und sollte daher die gleiche Lösung haben, wenn für den Fall der Sublisten eine gute Lösung gefunden ist.

Denn ohne Lücken musst du Elemente verschieben und Verweise (in dem Fall Indizes) neu setzen. Dürfte recht teuer sein, neben der benötigten Zeit auch vom Verwaltungsaufwand her. Wenn ich das richtig sehe, wird dieser Schritt mit deinem bisher vorgestellten Plan notwendig, oder?

Ja, deshalb frage ich ja nach besseren Lösungen. Immerhin wäre dieser Verwaltungsschritt aber jeweils nur beim Löschen eines Elements nötig, was eine eher seltene Aktion ist. Dafür könnte man den Rest alles so lassen wie es ist.
Mir fällt gerade noch etwas wichtiges ein: Die Listen sind alle gleich lang.

Falls sowas vertretbar wäre, hättest du zwar einiges an Overhead und langsame Löschungen, dafür aber einen defragmentierten Container und sehr schnelle Iterationen und Wahlzugriffe.

Und das ist eigentlich recht vertretbar, das Löschen darf ruhig dauern, der wahlfreie Zugriff findet um 3-4 Größenordnungen häufiger statt.

SeppJ

hustbaer schrieb:

@SeppJ:
Wenn ich das richtig verstehe geht es nur um den 2. Vektor, wo die "nicht-head" Listenelemente drinstehen. Soweit richtig?

Nein, es sollen ganze Sublisten gelöscht werden, inklusive "head". Es ist aber durchaus denkbar, beide Fälle gesondert zu behandeln. Schon jetzt ist es so, dass bei vielen Sachen die das Programm macht die Elemente in dem vector der Listenanfänge anders behandelt werden als die Elemente in dem Vector der Listenreste.

Den "nicht-head" Vektor könnte man vermutlich einfach durch den Heap ersetzen, also einfach zusammenhängende Arrays vom Heap anfordern. Bzw. auch viele kleine Vektoren.

Das wäre eine zusätzliche Pointerindirektion bei jedem Zugriff, das dürfte Geschwindigkeitstechnisch akzeptabel sein und ließe sich gut kapseln, so dass ich am Rest des Programms nichts ändern brauche. Passt nur leider nicht so ganz zu meinem Problem, da ich wie gesagt aus beiden vectoren gleichzeitig löschen möchte. Ich werde aber mal ein Testprogrämmchen schreiben, wie schnell diese Art der Organisation wäre, einfach weil es mich interessiert. Wenn die Ergebnisse zufriedenstellend sind, lässt sich der Rest der Struktur ja vielleicht auch entsprechend verbiegen.

SeppJ

Ich wollte dann noch erwähnen, dass ich mich entschieden habe, den Vorschlag von Nexus umzusetzen. Die Eigenschaft der Indizes, sich fest auf ein Element zu beziehen ist im Programm tiefer verankert, als die Eigenschaft, dass alle aktiven Elemente an einem Stück im Speicher liegen. Also wage ich den Mut zur Lücke und werde lieber die freigewordenen Indizes irgendwo speichern, anstatt beim Verschieben von Elementen alle Referenzen zu suchen und zu ändern.

Nexus

Schön, dass ich dir helfen konnte. Zumindest vorerst

Der andere Ansatz mit dem Verweise Aktualisieren hätte wohl eher kompliziert ausgesehen (nicht zuletzt durch die Einbindung in bestehenden Code). Ich hätte es wahrscheinlich mit einer Indexklasse und einem zentralen Registriersystem versucht. Vielleicht kommst du aufgrund von Performanceproblemen doch noch dazu...