Speichersparender Algorithmus gesucht

SeppJ

Hallo! Ich habe Daten der Form

1. A Nutzdaten11
2. A Nutzdaten12
3. B Nutzdaten13
4. B Nutzdaten14
---break---
1. B Nutzdaten21
2. B Nutzdaten22
3. B Nutzdaten23
4. B Nutzdaten24
---break---
1. A Nutzdaten31
2. A Nutzdaten32
3. A Nutzdaten33
4. A Nutzdaten34

und zusätzlich

1-2
3-4

Erklärung des ersten Teils: Eine Position, ein Identifier (hier A und B, können beliebig viele verschiedenen sein, werden in der Regel aber nur eine handvoll sein), zu diesen ein paar Nutzdaten. Es gibt Blöcke von Daten und die Anzahl der Datenelemente in jedem Block ist gleich (und muss immer gleich sein). Die Identifier zu einer Position können sich in jedem Abschnitt verändern.
Erklärung des zweiten Teils: Gibt an, welche Positionen mit welchen anderen Positionen verknüpft sind. Die Identifier von zusammengehörigen Positionen sind in jedem Abschnitt gleich, können sich aber von Abschnitt zu Abschnitt alle gleichzeitig ändern.

Nun habe ich ein Analyseprogramm, auf dessen Code habe ich keinen Zugriff. Das Programm kommt nicht mit wechselnden Identifiern klar. Aber man kann dem Programm Nulldaten unterschieben, da die Position der Daten selber nicht wichtig ist, sondern nur welcher Identifier zu welchen Nutzdaten gehört und welche Datensätze zusammen gehören. Das heißt, wenn ich die Daten von oben analysieren will (bei denen der Teil 1-2 von A->B->A wechselt und Teil 3-4 von B->A, dann kann ich diese Umwandeln zu:

1. A Nutzdaten11
2. A Nutzdaten12
3. B Nutzdaten13
4. B Nutzdaten14
5. B Nulldaten
6. B Nulldaten
7. A Nulldaten
8. A Nulldaten
---break---
1. A Nulldaten
2. A Nulldaten
3. B Nutzdaten23
4. B Nutzdaten24
5. B Nutzdaten21
6. B Nutzdaten22
7. A Nulldaten
8. A Nulldaten
---break---
1. A Nutzdaten31
2. A Nutzdaten32
3. A Nulldaten
4. A Nulldaten
5. B Nulldaten
6. B Nulldaten
7. A Nutzdaten33
8. A Nutzdaten34

mit den Abschnitten:

1-2
3-4
5-6
7-8

Alle mitgekommen? Durch das Hinzufügen von Dummydaten konnte ich dem Analyseprogramm vormachen, dass in jedem Abschnitt 8 Datensätze sind, mit jeweils konstanten Identifiern. Im ersten Abschnitt sind die neuen Daten auf 0 gesetzt und zählen nicht mit. Im zweiten Abschnitt, bei dem im Original der 1-2 Teil von A nach B wechselte, wird nun der 1-2 Teil auf Null gesetzt, dafür bekommt einer der neuen B-Teile die Nutzdaten. Im dritten Abschnitt wechselte 1-2 wieder zurück nach A und 3-4 wechselte ebenfalls nach A. Der 3-4 Abschnitt hat dafür den Dummyteil 7-8 bekommen, der nun aktiv wird und für den 1-2/5-6-Teil kann man den alten 1-2-Teil wieder benutzen, da dieser schon den korrekten Identifier A hat. So wird verhindert, das bei häufigem hin und her die Ausgabe nicht ewig lang wird.

Ich habe auch schon einen Algorithmus, der mir das erledigt. Problem: Der Speicherbedarf meines Algorithmus geht ungefähr quadratisch mit der Eingabemenge. Die Eingabemenge kann auch sehr groß werden. Seit gestern sprengt das Programm bei der größten Eingabe die Kapazität meines Rechners (zig Gigabytes).
Nun suche ich einen Algorithmus, der mit weniger Speicher auskommt. Es ist wichtiger, dass der Algorithmus durchläuft, als dass er schnell ist. Da er aber bereits jetzt im Minuten bis Stundenbereich arbeitet, wäre es aber auch gut, wenn er wenigstens ähnlich schnell bleibt.

Ihr könnte ja schon einmal nachdenken und nötigenfalls nachfragen, während ich beschreibe, wie mein derzeitiger Algorithmus aussieht und wieso er so viel Speicher benötigt. Das wird sicherlich eine Weile dauern, bis ich das aufgeschrieben habe.

SeppJ

Derzeit erzeuge ich die Ausgabe wie folgt:
Ich habe eine Liste (vector) mit den Abschnitten (die Teile zwischen den ---break---s). Zu jedem Abschnitt gehört eine Liste mit den Daten, bestehend aus der Position in der Liste, dem Identifier und den Nutzdaten. Das ist die Repräsentation des ersten Code-Abschnitts aus dem Eingangspost. Außerdem habe ich eine Liste der zusammengehörigen Positionen (der zweite Code-Abschnitt von oben).

Den 0'ten Abschnitt lasse ich vorerst unverändert. Ich gehe nun alle weiteren Abschnitte durch und vergleiche, ob ein Datum an einer bestimmten Position den gleichen Identifier wie in Abschnitt 0 hat.

Wenn ein Datum seinen Identifier gegenüber dem Abschnitt 0 geändert hat, so wird in einer Map aus "Assoziationen" nachgeguckt, ob es bereits ein passendes Dummydatum zu diesem Datum gibt.

Wenn es kein passendes Dummydatum gibt, so wird zu jedem Abschnitt ein neues Datum hinzugefügt. Außerdem wird gespeichert, zu welcher Position in Abschnitt 0 dieses Dummydatum gehört (die oben genannte "Assoziation"). Die Nutzdaten werden für den aktuellen Abschnitt korrekt gesetzt.
Weiterhin wird geguckt, ob das Datum zu einem der Positionsbereiche gehört und es wird auf ähnliche Art ein assoziierter Dummybereich angelegt.

Gibt es bereits eine passende Assoziation, so wird diese für den aktuellen Abschnitt benutzt.

Wenn alle Abschnitte betrachtet wurden, wird die Datenstruktur herausgeschrieben.

Warum braucht das so elendigviel Speicher?
Weil die ganze Datenstruktur die gesamte Zeit lang im Speicher gehalten werden muss, denn selbst bei Betrachtung des letzten Abschnitts kann es noch einen Identifierwechsel irgendwo geben, der in jedem Abschnitt das Hinzufügen eines Dummyteilchens nötig macht.

Michael E.

Trivialer Tipp (der Vollständigkeit halber): Beim Herausfinden, wie viele Dummypositionen du brauchst, brauchst du die Nutzdaten noch nicht. Wenn die Nutzdaten den Speicherverbrauch also in die Höhe steigen lassen, kannst du sie auch nachträglich einfügen.

Ein paar Fragen: Sind je zwei Positionen miteinander verbunden oder können das mehr sein? Kann eine Dummyposition zu unterschiedlichen Zeitpunkten von verschiedenen Ur-Positionen benutzt werden?

SeppJ

Entschuldigung für die späte Antwort, ich war ein paar Tage weg.

Michael E. schrieb:

Trivialer Tipp (der Vollständigkeit halber): Beim Herausfinden, wie viele Dummypositionen du brauchst, brauchst du die Nutzdaten noch nicht. Wenn die Nutzdaten den Speicherverbrauch also in die Höhe steigen lassen, kannst du sie auch nachträglich einfügen.

Ehrlich gesagt sind die Nutzdaten derzeit noch drin, da es nur jeweils ein paar Bytes sind. Daran habe ich natürlich auch schon gedacht, aber ich hatte mir von einem Umschreiben des Programmes etwas mehr erhofft als einen Faktor zwei bis drei, den ich hiermit erreichen würde.

Ein paar Fragen: Sind je zwei Positionen miteinander verbunden oder können das mehr sein? Kann eine Dummyposition zu unterschiedlichen Zeitpunkten von verschiedenen Ur-Positionen benutzt werden?

Jede Position kann nur zu je einer Gruppe gehören. zu einer Gruppe gehören derzeit immer gleich viele Positionen (aber mehr als zwei, eher so um die 10), aber das würde ich gerne flexibel sein. Die Gruppen sind statisch.

Derzeit sind die Dummypositionen auch an die Gruppe (genauer: sogar die Ur-Position) gebunden, zu der sie zuerst erstellt wurden. Hier ließe sich möglicherweise ein kleines bisschen Einsparen. Das wäre jedoch algorithmisch vermutlich sehr viel aufwändiger, wobei aber die mögliche Einsparung nicht so gewaltig wäre, da diese Wechsel nicht so extrem häufig sind und der Gesamtanteil der verschiedenen Gruppentypen in den typischen Fällen ungefähr gleich bleibt. Wenn es sehr gut läuft, würde ich geschätzt 15-20% sparen können, pessimistische Schätzung wäre eher 5%.

Michael E.

Wenn die Gruppen etwas größer sind, kannst du auch mit jeweils einem Repräsentanten pro Gruppe berechnen, wie viele Dummypositionen du brauchst. Dadurch sparst du dann den Faktor 10. Ich weiß, ist auch nur ein trivialer Tipp, den du vielleicht schon implementiert hast, aber mehr fällt mir im Moment nicht ein. Ich zweifle auch daran, dass es deutlich besser geht.