Wie verwalte ich so viele Daten?

[Medium]

Ich hab mit binärer bzw. arithmetischer Suche in Listen hervorragende Erfahrungen gemacht, auch bei mehreren zigtausend Einträgen. Im Worst-Case bist du da mit einer Suchzeit von O(log(n)) unterwegs, und der WC tritt selten genug auf, bzw. je homogener die Liste, desto seltener.
Vorteil dabei ist zudem, dass eine Suche nach einem Eintrag im Falle des Nichtfindens auch gleich die Position liefert, an der einzufügen wäre um gleich während des Aufbaus die Sortierung zu gewährleisten, und Suchen+Einfügen damit im Grunde ein und die selbe Operation ist, die auch nur ein Mal pro Durchlauf gemacht werden muss.

Nach meinem Empfinden ist hier eine Hashtable fast schon Overkill, wenn auch nicht weniger Elegant. Aber ein Array der Länge Max(Cardinal) ist größtmöglicher Unfug

[stoxx]

Hi Medium,

guck mal da, und wahrscheinlich wird auch Deine binäre Suche im Nachteil gegenüber Hashtabellen sein ...

http://www.delphipraxis.net/internal...light=skiplist

Gruss stoxx

[alzaimar]

Zitat von Medion:

Im Worst-Case bist du da mit einer Suchzeit von O(log(n)) unterwegs, und der WC tritt selten genug auf, bzw. je homogener die Liste, desto seltener.

Nee. WC ist zwar O(log(n)), aber dieser Fall tritt in der Hälfte aller Fälle auf, denn bei z.B. 1024 Einträgen haben wir 512 Blätter (im binären Suchbaum), für die man also 10 Vergleiche (10=log(1024)) benötigt, bei 256 Werten benötigt man 9 Vergleiche usw. Ich frage mich, wie homogen eine Liste sein muss, damit man wesentlich weniger als O(Log(n)) Schritte benötigt Zwinkern

Zitat von Medion:

Nach meinem Empfinden ist hier eine Hashtable fast schon Overkill

Na ja, wenn die Klasse doch schon fix und fertig ist, dann ist das kein Overkill, sondern ein Unterschied zwischen Stunden und Minuten. Bei -sagen wir- 1.000.000 unterschiedlichen 4-Tupeln würde eine Binäre Suche 1 Mio * log(1 mio), also ca. 19.000.000 Vergleiche benötigen (o.g. Rechnung mit einbezogen), die Hashtabelle kommt dagegen mit ca. 1.1 Mio Vergleichen aus. Das ist 17x schneller! Wenn das kein Grund für einen Overkill ist...

Das von stoxx verlinkte Demo-Programm zeigt diese gravierenden Unterschiede (Sorted List = binäre Suche). Bei 1Mo Werten dauert die BS einfach viel zu lange. Für das Verwalten von Schlüssel/Wert-Paare verwende ich ausschließlich Hashmaps (außer bei 20 Einträgen, da reicht auch ne Stringlist).

Aber selbstverständlich macht man mit der binären Suche gute Erfahrungen, schließlich funktioniert sie ja. Wie Skiplisten und Hashmaps auch.

[Medium]

Zitat von alzaimar:

Bei -sagen wir- 1.000.000 unterschiedlichen 4-Tupeln würde eine Binäre Suche 1 Mio * log(1 mio), also ca. 19.000.000 Vergleiche benötigen

Nene, du nimmst gerade O(n*log(n)) an, aber es ist O(log(n)). Bei 1 Mio Einträgen sind nur rund 20 Vergleiche nötig um an das Ziel zu kommen. Halbiere mal 1000000 N mal, und du wirst nach N=20 ein Intervall von ~1,9 erhalten, was mit evtl. noch einem Vergleich mehr einem Fund entspricht. Das ist der Worst-Case.

Noch schneller wirds wie gesagt mit der arithmetischen Suche, die Wikipedia als Interpolationssuche kennt. Das ungefähre Laufzeitverhalten ist dabei O(log(log(n))), wobei ein Worst-Case mit O(n) auftauchen kann. Um das zu "fixen" kann man sich der Quadratischen Binärsuche bedienen, die im Wiki leider nur angerissen wird, aber an sich klar wird was da passiert.

O(log(log(n))) ist im Falle von n=1000000 ca. 4,3. Schneller ist dann fast nur noch indizierter Zugriff auf ein Array[Cardinal].

Mich würde tatsächlich interessieren, ob ich da nun grundsätzlich was missverstanden habe.

[stoxx]

Zitat:

Nene, du nimmst gerade O(n*log(n)) an, aber es ist O(log(n)). Bei 1 Mio Einträgen sind nur rund 20 Vergleiche nötig um an das Ziel zu kommen.

ich bin da zwar jetzt auch nciht ganz so sicher, was alzaimer da jetzt gemeint hat, aber bei einem Hash brauchst Du im theoretischen Fall nur einen Vergleich, um zu finden, plus lineare Suche bei eventuellen Überlaufketten.
Nachteil allerdings, dass Du Dir die "Position" erst berechnen musst. Was also dann letztendlich schneller ist, lässt sich mit theoretischen Methoden dann nur noch bedingt berechnen. Und zeigt am besten ein praktischer Test, und die Demo im Link zeigt das ja eindeutig recht gut, dass ein Hash schneller ist, wenn man denn die Daten nicht sortiert benötigt
so ist das eben, mit den Vor und Nachteilen .. je nach Anwendung eben ...

[Medium]

Jau, da wirds dann in der Tat sehr von der Grundmenge und dem Einsatz abhängig. Insbesondere die Frage nach der Sortierung wird dann wohl interessant. Aber gut, der TE hat ja jetzt eine Menge sehr guter Verfahren zur Auswahl, und kann sich dann was passendes aussuchen

[alzaimar]

Medion, stoxx ihr habt beide einen Denkfehler.

Meine Beispielrechnung bezog sich -wie beschrieben- auf eine Datei mit 1 Mio 4-Tupeln, die es zu analysieren gilt. Der Einfachheit halber habe ich angenommen, das bei BEIDEN Verfahren bereits 1 Mio Einträge in der Liste enthalten sind. Ansonsten müsste man das nichtlineare Verhalten der binären Suche mit einbeziehen, und das habe ich mir gespart. Insofern stimmt meine Rechnung: Ich muss also bei der BS 1 Mio * 19 Vergleiche machen (für jedes der 1 Mio 4-Tupel im Mittel 19 Vergleiche) , bei der Hashmap eben 'nur' 1,1 Mio. In Wirklichkeit wird der Unterschied vermutlich etwas geringer ausfallen (weil eben die Liste anfangs leer ist), aber es geht ums Prinzip.

Einen weiteren Nachteil hat eine sortierte Liste: Man muss beim Einfügen den ganzen Speicher verschieben, also im Mittel die halbe Liste. Das Problem hat man mit einer Hashmap nicht.

Zitat von Medium:

O(log(log(n))) ist im Falle von n=1000000 ca. 4,3. Schneller ist dann fast nur noch indizierter Zugriff auf ein Array[Cardinal].

Jo, oder eben eine Hashmap mit 1,1.

Zitat von stoxx:

...Was also dann letztendlich schneller ist ...

zeigt die von Dir verlinkte Demo, die doch aussagekräftig genug ist. Binäre Suche lohnt sich nur, wenn (1) die Liste übersichtlich und (2) das sortierte Ergebnis instantan benötigt wird. Sonst nicht. Bei massivem Numbercrunching degeneriert die binäre Suche eben zu einer lahmen Angelegenheit.

Die 'Berechung' der Position in der Hashmap ist zudem bei einer Integer-Hashmap ein einziges 'MOD', sodaß man hier nicht gerade von komplexen Berechnungen reden kann...

Letztendlich kann man diskutieren und rumrechnen: Die Demo beantwortet alle Fragen. Allerdings verwendet sie Strings als Schlüssel, also sind die Zeiten zwar vergleichbar, aber absolut sollte das schon wesentlich schneller gehen. Auf meinem Laptop dauert mein oben geposteter Code bei 1Mio Elementen 300ms (Mobile Pention 1,5GHz, also ne alte Mühle)

Im MS SQL-Server kommt übrigens bei der Verwaltung der freien Speicherblöcke eine Skiplist zum Einsatz, weil sie von der Speicherfragmentierung besser (=besser vorhersagbar) als eine Hashmap ist.

[klugscheiss]Hat mir keine Ruhe gelassen, kleine Demo gebaut....
Man sind wir besch**** da rechnen wir mit irgendwelchen O's rum, wo der absolute bottleneck dieses Einfügen in die Liste ist. Beweis: die Demo. Hier kann man zwei Werte angeben:
1. Anzahl der einzufügenden Werte.
2. Anzahl der unterschiedlichen Werte. (for i:=1 to Total do insert (i mod unterschiedlich)

Binärsuche kann man total vergessen. Auch jeder andere Algorithmus, der eine statische Liste befüllt, scheidet wohl aus.
[/klugscheiss]

edit: Demo verbessert: Es werden nun Random-Zahlen (jeweils gleicher RandSeed) gezählt.

[Medium]

Ohne mir die Demo jetzt angesehen zu haben, vermute ich ganz stark auch auf Grund deiner Äusserung, dass man beim Einfügn die halbe Liste verschieben müsste, dass du als Datencontainer ein Array verwendest, vermutlich sogar noch ein dynamisches. Dass dann eine Einfügeoperation um Kardinalitäten langsamer als eine Anfügeoperation ist, sollte einleuchten.
Eine doppelt verkettete echte Liste macht hingegen genau keinen Unterschied dabei, ob ich nun hinten anfüge oder in der Mitte etwas zwischenhänge. Ohne jeweils passende Datenstrukturen nützt der ganze Vergleich leider nichts.

Letztlich will ich hier ja garkeinen Flamewar zwischen binärer Suche und Hashmaps anzetteln, sondern nur darauf hinweisen, dass Hashmaps nicht in jedem Fall das nun plus ultra sind. Auch gibt es einen gewissen Overhead, dass in Kollisionsfällen doch wieder Listen zum Einsatz kommen, und damit in sehr degenerierten Fällen eine Hashmap wieder zu einer Liste machen. (Dabei ist dann die Länge des Hashes, also indirekt der Speicherbedarf wieder interessant.)
Insbesondere die implizite Sortierung dürfte der binären Suche (bzw. ihren Verbesserungen, die du bislang nicht beachtet hast) einen großen Pluspunkt verschaffen, weil zumindest is sehr vielen Anwendungen mit derart vielen Daten letztlich eine Sortierung mindestens wünschenswert ist (um z.B. Daten in einer bestimmten Range auszugeben etc.).

Die Wahl ist daher stark von der Beschaffenheit der Datenmenge, und dem Einsatzzweck abhängig.


Allerdings:

Zitat:

Meine Beispielrechnung bezog sich -wie beschrieben- auf eine Datei mit 1 Mio 4-Tupeln, die es zu analysieren gilt. Der Einfachheit halber habe ich angenommen, das bei BEIDEN Verfahren bereits 1 Mio Einträge in der Liste enthalten sind. Ansonsten müsste man das nichtlineare Verhalten der binären Suche mit einbeziehen, und das habe ich mir gespart.

Dass du das nicht-lineare Verhalten einfach ignorierst ist ungenügend, da die binäre Suche immer nichtlinear ist. Gerade wenn bereits viele Einträge vorhanden sind. Ich weiss nicht, wie du zu einem anderen Schluss kommst hier. Bei 1 Mio vorhanderer Einträge, weisst du gesichert nach spätestens 20 Vergleichen, wo dein Wert steht, bzw. wo er eingefügt werden muss um die Sortierung beizubehalten. Immer. Und bei den angesprochenen 2 Verbesserungen nochmals deutlich weniger. Das aber nur noch nachgeschoben, es ändert an oben gesagtem nichts

[alzaimar]

Zitat von Medium:

Eine doppelt verkettete echte Liste macht hingegen genau keinen Unterschied dabei, ob ich nun hinten anfüge oder in der Mitte etwas zwischenhänge. Ohne jeweils passende Datenstrukturen nützt der ganze Vergleich leider nichts.

Verkettete Listen kann man nicht binär durchsuchen. Wir vergleichen Verfahren und die binäre Suche benötigt nun mal ein Array, scheidet also *aus*.

Zitat von Medium:

Letztlich will ich hier ja garkeinen Flamewar zwischen binärer Suche und Hashmaps anzetteln,

Flamewares gibts bei mir nicht.

Zitat von Medium:

sondern nur darauf hinweisen, dass Hashmaps nicht in jedem Fall das nun plus ultra sind.

Mir ist kein Fall bekannt. Wenn ich nur einige Tausend Werte habe und ich sofort eine sortierte Liste möchte, ist eine Array-Struktur mit BS natürlich praktischer. Schneller ist es in keinem mir bekannten Fall.

Zitat von Medium:

Auch gibt es einen gewissen Overhead, dass in Kollisionsfällen doch wieder Listen zum Einsatz kommen, und damit in sehr degenerierten Fällen eine Hashmap wieder zu einer Liste machen.

Dieser Overhead führt zu einem Faktor von ca. 1.1 anstelle von 1.0.
Ich kann jedoch einen theoretische Worstcase konstruieren, wenn ich die Hash-Funktion der Hashmap kenne, und dafür sorge, das meine Schlüssel immer auf dem gleichen Bucket landen. Dieser Worstcase kommt aber in der Realität eigentlich nie vor.

Zitat von Medium:

(Dabei ist dann die Länge des Hashes, also indirekt der Speicherbedarf wieder interessant.)

Der Hash wird nicht gespeichert, sondern dient zur Berechnung des Indexes in der Hashmap.

Zitat von Medium:

Insbesondere die implizite Sortierung dürfte der binären Suche (bzw. ihren Verbesserungen, die du bislang nicht beachtet hast) einen großen Pluspunkt verschaffen, weil zumindest is sehr vielen Anwendungen mit derart vielen Daten letztlich eine Sortierung mindestens wünschenswert ist (um z.B. Daten in einer bestimmten Range auszugeben etc.).

Nein. Hinterher einmalig Sortieren ist immer schneller, als ständig die Ordnung der Liste zu gewährleisten.

Zitat von Medium:

Die Wahl ist daher stark von der Beschaffenheit der Datenmenge, und dem Einsatzzweck abhängig.

Auch falsch. Es gibt nur einen sehr sehr seltenen Fall: Die Schlüssel mappen auf immer die gleichen Buckets. Bei Strings ist das sehr unwahrscheinlich (ELF-Hash), bei Zahlen als Schlüssel müssten diese bei meiner Implementierung immer ein Vielfaches der aktuell internen Länge der Hashmap (Primzahl) sein. Beides ist verdammt selten in freier Wildbahn anzutreffen

Zitat von Medium:

Dass du das nicht-lineare Verhalten einfach ignorierst ist ungenügend, da die binäre Suche immer nichtlinear ist.

Meine Rechnung stimmt auch bei der Vereinfachung. Die korrekte Zahl liegt bei ca. 17 Mio. Die 19 Mio als Überschlag sind also innerhalb eines Fehlers von 10%. Nicht schlecht für eine grobe Schätzung.

Zitat von Medium:

Ich weiss nicht, wie du zu einem anderen Schluss kommst hier. Bei 1 Mio vorhanderer Einträge, weisst du gesichert nach spätestens 20 Vergleichen, wo dein Wert steht, bzw. wo er eingefügt werden muss um die Sortierung beizubehalten.

Du meinst, über den WorstCase eine Entscheidung über die Güte eines Verfahrens fällen zu können. Ich nehme den Normalfall, denn das tritt in der Praxis nun mal auf. Ich schlage vor, Du verwendest einfach mal eine Hashmap. Du wirst sehen, um wie viel schneller deine Anwendungen werden. Wenn es Dir um den WC geht, dann verwende eine SkipList, die reorganisiert sich selbst.
Bei den von Dir erwähnten Verbesserungen hätte man weniger Vergleiche, aber *immer* mehr als bei einer Hashmap. Weiterhin kenne ich keine Implementierung, die eine der erwähnten Suchverfahren auf einer verketteten Liste anwenden kann, wir haben es hier also letztendlich mit Arrays zu tun, die dann nicht zu gebrauchen sind.

Natürlich sind deine Überlegungen bezüglich des WC richtig, aber wenn der WC in der Praxis nicht vorkommt, dann ist das irrelevant. Jede Hash-Funktion hat einen WC (zwei Strings mappen auf den selben Wert). Werden sie deshalb nicht eingesetzt? Jeder Quicksort auch. Trotzdem verwendet man ihn. Und eine Hashmap hat einen extrem lahmen Worst Case, trotzdem sind die Teile im Einsatz, wie eben ein Quicksort oder ein KMP-Search etc.

Meine Demo simuliert die vom Fragesteller thematisierte Problematik: Es werden Häufigkeiten gezählt. Da interessiert mich irgend ein Worst Case oder eine theoretische Berechnung nicht. Ich starte und schaue auf das Ergebnis.
In der ersten Version habe ich einfach aufsteigend die 'i mod X' gezählt, das führt bei der BS zum Worst Case und ist insofern unfair. Also habe ich eine neue Version eingestellt, die Zufallszahlen (jeweils mit gleichem Seed) zählt. Die Ergebnisse sind immer noch so, das man das BS letztendlich in die Tonne treten kann. Wenn Du natürlich eine deiner Suchverfahren mit einer verketteten Liste durchführen kannst, wäre das Ergebnis zwar immer noch langsamer als eine Hashmap, dafür hätten wir aber eine Struktur mit einem akzeptablen weil deterministischen Worst Case. Diese Implementierung würde ich dann als akzeptable Alternative zu Hashmaps, Skiplisten, DAWGs etc. ansehen.

[Medium]

Zitat von alzaimar:

Verkettete Listen kann man nicht binär durchsuchen. Wir vergleichen Verfahren und die binäre Suche benötigt nun mal ein Array, scheidet also *aus*.

Den wahlfreien Zugriff kann man sich auf zwei Weisen herstellen:
1) Ein Verweis-Array mitführen (was jedoch selbst dann das Problem hat, dass es Verschiebungen darin gibt. Es lohnt also nur, wenn die Daten erheblich länger ausfallen und somit beim Umkopieren ein echter Unterschied existiert)
2) In Schleifchen durchhangeln. Klingt zunächst suboptimal, ist aber schnell genug, da man bedenken muss, dass man sich pro Iterationschritt nur noch maximal um die Hälfte nochmal hangeln muss, bzw. bei den verbesserten Versionen nochmals weniger. So mache ich es in einem Programm, bei dem eine Liste von rund 30 Mio Punkten im Raum verarbeitet wird, und ich bin eigentlich recht zufrieden mit der Geschwindigkeit. Wenn ich Zeit und Muße hab, werd ich das mal testweise mit einer Hashmap bauen.

Zitat von alzaimar:

Der Hash wird nicht gespeichert, sondern dient zur Berechnung des Indexes in der Hashmap.

Schon klar, aber das Array muss ja genau so viele Indizes aufweisen, wie es Hashes geben kann. Bei einem z.B. 2 Byte Hash hast du ein schlankes Array von nur 64k, aber bei über 1 Mio Einträgen etliche Kollisionen. Bei einem 4 Byte Hash sind wir wieder bei einem Array(Cardinal). Lösung des Problems wäre ein dynamisches Array, dass aber auch bei "intelligentem" Wachstum noch immer als Overhead kräftig zuschlägt (umkopieren). Eine Liste scheitert ja hier definitiv am wahlfreien Zugriff. Das meinte ich damit lediglich.

Zitat von alzaimar:

Nein. Hinterher einmalig Sortieren ist immer schneller, als ständig die Ordnung der Liste zu gewährleisten.

Kommt darauf an. Ich hab in einem Fall die Situation, dass ich "Snapshots" einer Range einer Liste anzeigen lasse, während diese noch befüllt wird. Das passiert alle paar hundert Millisekunden, und würde ich hier jedes Mal den Bereich erst noch sortieren müssen, wäre es vorbei mit der Schnelligkeit. Es gibt also tatsächlich solche Fälle

Zitat von alzaimar:

Meine Rechnung stimmt auch bei der Vereinfachung. Die korrekte Zahl liegt bei ca. 17 Mio. Die 19 Mio als Überschlag sind also innerhalb eines Fehlers von 10%. Nicht schlecht für eine grobe Schätzung.

Den Teil habe ich bis jetzt nicht ganz verstanden. Was tust du, um auf so viele Vergleiche zu kommen? Ich ging bisher immer von der Suchzeit aus, bis man ein Element in einer bestehenden Menge von Daten gefunden hat, und um dafür 17 Mio Vergleiche zu brauchen, müsste die Liste ja 2^17.000.000 Einträge haben

Zitat von alzaimar:

Wenn Du natürlich eine deiner Suchverfahren mit einer verketteten Liste durchführen kannst, wäre das Ergebnis zwar immer noch langsamer als eine Hashmap, dafür hätten wir aber eine Struktur mit einem akzeptablen weil deterministischen Worst Case. Diese Implementierung würde ich dann als akzeptable Alternative zu Hashmaps, Skiplisten, DAWGs etc. ansehen.

Ich wäre nie auf die Idee gekommen, ein Array als Container zu verwenden, eben weil es dynamisch sein müsste, mindestens aber unglaublich viel Kopiererei stattfinden würde. Ich hab für o.g. Anwendung eine Liste im Einsatz, bei der die Nodes nicht nur die direkten Nachbarn kennen, sonden die jeweils nächsten 3 in jeder Richtung. Das macht beim Einfügen dann zwar etwas mehr Arbeit, da aber der zeitkritische Teil in diesem Fall nicht das Einfügen, sondern das anschließende Arbeiten damit ist, lohnt es sich.


Dass Hashmaps zur Verwaltung von Strings eigentlich immer überlegen sind kann ich gut nachvollziehen, und in diesem Zusammenhang hab ich sie auch bisher nur gesehen. Bei numerischen bzw. binären Werten sind sie mir eigentlich noch nicht über den Weg gelaufen.