Wie verwalte ich so viele Daten?

[Neutral General]

Hi,

Ich würde gerne eine Datei nach 4-Byte-Folgen durchsuchen und diese Zählen. Also z.B. wie oft kommt

$25$75$DA$2F

in Datei.xyz vor. Nur das ich nicht nur 1 4-Byte-Folge zählen will, sondern alle von $00000000 bis $FFFFFFFF...

Also bräuchte ich theretisch sowas wie:

Delphi-Quellcode:

Zaehlarray: Array[0..High(Cardinal)] of Word;

Aber das sprengt ja alle Rahmen...

Wie mache ich sowas am besten?

Gruß
Neutral General

[Medium]

Ein Großteil wird ja garnicht vorkommen. Also nimm statt eines Arrays eine Liste, und füge jede Folge die du neu findest in diese ein. Findest du diese öfter, dann einen Zähler jeweils mit erhöhen.

[Neutral General]

Ja dachte ich mir auch schon aber das nachgucken, ob eine Folge schon in der Liste ist, dass dauert ja auch ne Weile... Wird das nicht irgendwann zu aufwendig (CPU)?

[marabu]

Hallo,

wenn die Liste sortiert ist, dann kannst du mittels binärer Suche sehr effizient zugreifen.

Übrigens hat ein Word nur zwei Byte ...

Grüße vom marabu

[Neutral General]

Zitat:

Zitat von marabu

Hallo,

wenn die Liste sortiert ist, dann kannst du mittels binärer Suche sehr effizient zugreifen.

Übrigens hat ein Word nur zwei Byte ...

Grüße vom marabu

Zu der binären Suche müsste ich mich mal informieren... Das ein Word 2 Byte groß ist, wusste ich.

Das ganze sollte ja ungefähr so laufen (theorie)

Delphi-Quellcode:

var Arr: Array[0..High(Cardinal)] of Word;
    buf: Cardinal;
begin
stream.LoadFromFile(datei);
stream.Read(buf,4);
inc(Arr[buf]);

Gruß
Neutral General

[Apollonius]

Wenn du das nicht mit MMFs machst, bist du verloren.

[Neutral General]

Und was sind MMFs ? Mapped Files?

Und wenn ja - wie benutze ich die?

[Die Muhkuh]

Memory Mapped Files

[marabu]

Hi Michael,

mit zwei Byte zählst du nur bis 64K - das könnte in einigen Fällen zu wenig sein.

Dein statisches Array würde in jedem Fall 2^34 Byte (16GB) belegen. Mit einem entsprechenden Server unter 64bit Windows kein Problem - ich beneide dich um deine HW Austattung.

Nimm eine TList und erweitere sie um die binäre Suche - besser ist dass.

Freundliche Grüße

[alzaimar]

Ich würde sogar noch weiter gehen, und eine Hashmap verwenden. Hier ist eine.

Eine binäre Suche dauert doch etwas, wenn auch nicht viel, aber der Suchaufwand nimmt mit der Größe der Liste doch zu. Das passiert bei einer Hashmap nicht. Die Hashmap wächst dynamisch.

Bei der o.g. Hashmap (TIntegerDictionary) wird zu jedem 4-Byte Schlüssel eine Nutzerinformation (Pointer) gespeichert. So würde die Zählfunktion aussehen:

Delphi-Quellcode:

Procedure Count (aDict : TIntegerDictionary; aCardinal : TCardinal);
Var
  cnt : PInteger;

Begin
  If aDict.Find (aCardinal, Cnt) Then // Wenn schon in der dictionary
    Cnt^ := Cnt^ + 1                  // ... Zähler erhöhen
  Else Begin
    new (Cnt);                        // Ansonsten neuen Zähler anlegen
    Cnt^:= 1;                         // Initalisieren
    aDict.Add (aCardinal, Cnt);       // und ab in die dictionary
  End
End;

Das geht -wie schon erwähnt- sehr schnell, schneller gehts eigentlich nicht (ok, eine Skiplistei ist marginal schneller, wenn sie nicht zu groß wird).

Klitzekleiner Pferdefuß: Die Ergebnisse sind unsortiert, du musst sie am Schluss auslesen, in eine Liste packen und diese dann sortieren, aber das hättest Du bei einer Liste ja auch.

[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:

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:

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:

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:

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. :mrgreen:

Zitat:

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:

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:

Zitat von Medium

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

Flamewares gibts bei mir nicht.

Zitat:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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.

[alzaimar]

Hi Medium,

Zitat:

Zitat von Medium

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...

Hmmm. 1x Schritt (bis zur Mitte: N/2 Hüpfer. Dann wieder: N/4... ich komm auf O(N). Außerdem reden wir über binary search, lenk also nicht vom Thema ab. :mrgreen:

Zitat:

Zitat von Medium

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.

Nö. Ich verdopple immer. Wenn ich 2^31 Elemente einfüge, muss ich also nur 20x umkopieren (Ich fange bei 997 Elementen an),

Zitat:

Zitat von Medium

... 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 :)

Ach mann, das ist doch einfach. Ich rechne die Gesamtanzahl *aller* Vergleiche aus, um 1 Mio Elemente hintereinander zu finden und einzufügen. Da jedes Element im Mittel 17 Vergleiche benötigt (die ersten Elemente weniger, das die Liste fast leer ist, die letzten Elemente mehr, da die Liste voll sind), kommt man -wenn man eine sortierte Liste von 1 Mio Elementen aufbauen will- auf insgesammt im Mittel auf 17 Mio Vergleiche. PRO Element natürlich nur 17 Elemente, aber für alle zusammengenommen eben 17 Mio. Ist doch einfach.
.

Zitat:

Zitat von Medion

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.

Na, dann schau Dir mal die Skiplist an, die perfektioniert deine Vorwärtsverkettung, sodaß diese Struktur so schnell wie eine Hashmap ist. Das Lustige an der SL ist, das sie mit einem Random-Generator arbeitet!

[grenzgaenger]

och kommt jetzt, medium meint sicherlich 'n binary tree, statt 'ner verketteten liste :-) . ausserdem geb ich alzaimar recht, dass es nichts schnelleres gibt, als 'ne hash-verwaltung :-)

nur, frag ich mich, wie Neutral General hieraus konsequenzen ziehen soll, um zu wissen, wie er jetzt seine 4 bytes ablegen soll.

so denn, noch 'n schönen abend. :-)

GG

btw: ist immer nett experten beim fachsimplen zuzuhören :-)

[Neutral General]

Zitat:

Zitat von grenzgaenger

och kommt jetzt, medium meint sicherlich 'n binary tree, statt 'ner verketteten liste :-) . ausserdem geb ich alzaimar recht, dass es nichts schnelleres gibt, als 'ne hash-verwaltung :-)

nur, frag ich mich, wie Neutral General hieraus konsequenzen ziehen soll, um zu wissen, wie er jetzt seine 4 bytes ablegen soll.

so denn, noch 'n schönen abend. :-)

GG

btw: ist immer nett experten beim fachsimplen zuzuhören :-)

Der Neutral General hat schon die letzten Seiten nicht mehr weiterverfolgt, weil ihm das z.T. etwas zu hoch/zu anstrengend wird^^ Ist ja ne nette Diskussion hier aber ich muss mir (zu gegebenem Zeitpunkt) halt nochmal überlegen wie ichs genau mache, bzw den Thread ganz durchlesen. Wobei zur Zeit tendiere ich zu Hash-Maps. Mal sehn ;)