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
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)