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.