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.