Hi Medium,
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.
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 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 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!