Datenstruktur umschichten (Relation umkehren?)
-
Hi,
ich habe eine Abbildung
int->int[], kennt jemand einen effizienten Algorithmus (besser als O2) um die Relation umzukehren? Z.B.Haus->Bewohner[]nachBewohner->Haus[](ich hoffe es ist klar, was ich meine)?
Das Ganze sollte auch halbwegs praktikabel sein und nicht immensen Speicherplatz fressen
-
Eine Möglichkeit wäre eine Hashmap:
Für alle x aus dem Definitionsbereich von f ist f(x) ein Array, das nennst du {a, b, c, ...}. Dann trägst du in die Hashmap alle Key/Value-Paare der Form (a, x), (b, x), (c, x), ... ein. Das Aufbauen der Hashmap läuft praktisch in Linear-Zeit, das Abfragen der fertigen Hashmap sogar praktisch in Konstantzeit. Damit kannst du dann die Umkehrfunktion sehr schnell bestimmen (*).Allerdings braucht so eine Hashmap recht viel Speicher, mindestens für jeden Key einen Eintrag. Ein Baum würde tendenziell weniger Overhead benötigen, aber wahrscheinlich nicht so viel weniger, dass es in der O-Notation auffallen würde.
Wenn du signifikant weniger Speicher verwenden musst, wird es schwieriger. Dann könntest du evtl. die Struktur der Werte ausnutzen (ähnlich wie Radix-Sort das macht) oder du musst eine höhere Laufzeit in Kauf nehmen, nehme ich an.(*) Edit: Hashmap ist nur eine Option, wenn es für die Werte eine gute Hash-Funktion gibt.
-
Bewohner->Haus[]hat denn ein bewohner mehrere häuser oder wie soll man das verstehn?
wahrscheinlich ist es einfacher, wenn du bei erzeugung referenzen mit anlegst oder ne extra table machst.
-
ich habe eine Abbildung int->int[], kennt jemand einen effizienten Algorithmus (besser als O2) um die Relation umzukehren?
Ja, jeder Sortier-Algorithmus der in unter O(N²) ("O²" ist Unfug) läuft kann für sowas verwendet werden. z.B. Merge-Sort, Heap-Sort oder Introsort.
D.h. du sammelst alle "Haus, Bewohner" Paare im 1. Schritt (O(N)), und sortierst sie dann nach "Bewohner" (O(N log N)). Dann hast du ein sortiertes Array, in dem du mit einer binären Suche (O(log N)) Bewohner finden kannst, und das zugehörige Haus nachschlagen.Nachteil: das nachträgliche Einfügen dauert relativ lange.
Alternative: gleich einen Baum aufbauen (std::map) - läuft auch in O(N log N).
Oder eine Hash-Map, wie schon vorgeschlagen wurde (im Idealfall O(N)).
Das Ganze sollte auch halbwegs praktikabel sein und nicht immensen Speicherplatz fressen
Was praktikabel ist, und was "viel Speicher" ist, hängt wohl sehr davon ab um wieviel Daten es geht, und auf welcher Plattform es laufen soll.
Sämtliche hier diskutierten Dinge funktionieren gut wenn die Daten + der Overhead der Datenstrukturen komplett in den Speicher (RAM) passen. Sobald man auf die Disk ausweichen muss gelten etwas andere Regeln, und man muss andere Datenstrukturen bzw. Algorithmen verwenden wenn man möchte dass irgendwas in endlicher Zeit fertig wird.
-
Ok, super, hat geklappt. Hatte noch kurz gehangen, weil der Quicksort den Stack gesprengt hat, der Heapsort für n-äre Heaps tut's jetzt. Danke euch!
Map oder Hashmap kamen leider nicht infrage wegen Speicherverbrauch, ich brauche möglichst zusammenhängende Speicherstücke.
Also ich hab's jetzt quasi so gemacht:
hustbaer schrieb:
D.h. du sammelst alle "Haus, Bewohner" Paare im 1. Schritt (O(N)), und sortierst sie dann nach "Bewohner" (O(N log N)). Dann hast du ein sortiertes Array, in dem du mit einer binären Suche (O(log N)) Bewohner finden kannst, und das zugehörige Haus nachschlagen.
, nur dass ich beim Einlesen statt einem pair-Array zwei separate Arrays (einmal für Haus, einmal für Bewohner) konstruiert hab, dann einen Index erstellt mit dem ich mit dem Bewohner den zugehörigen Start-Index in dem Haus-Array anfragen kann. Dann konnte ich halt nach dem Erstellen vom Index das originale Bewohner-Array wegwerfen, wegen Speicher und so; das Ganze ist übrigens statisch.
