| alzaimar |
2. Mai 2008 19:16 |
Re: Wie verwalte ich so viele Daten?
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! |
