Wie verwalte ich so viele Daten?

[alzaimar]

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!

[grenzgaenger]

och kommt jetzt, medium meint sicherlich 'n binary tree, statt 'ner verketteten liste . ausserdem geb ich alzaimar recht, dass es nichts schnelleres gibt, als 'ne hash-verwaltung

nur, frag ich mich, wie Neutral General hieraus konsequenzen ziehen soll, um zu wissen, wie er jetzt seine 4 bytes ablegen soll.

so denn, noch 'n schönen abend.

GG

btw: ist immer nett experten beim fachsimplen zuzuhören

[Neutral General]

Zitat von grenzgaenger:

och kommt jetzt, medium meint sicherlich 'n binary tree, statt 'ner verketteten liste . ausserdem geb ich alzaimar recht, dass es nichts schnelleres gibt, als 'ne hash-verwaltung

nur, frag ich mich, wie Neutral General hieraus konsequenzen ziehen soll, um zu wissen, wie er jetzt seine 4 bytes ablegen soll.

so denn, noch 'n schönen abend.

GG

btw: ist immer nett experten beim fachsimplen zuzuhören

Der Neutral General hat schon die letzten Seiten nicht mehr weiterverfolgt, weil ihm das z.T. etwas zu hoch/zu anstrengend wird^^ Ist ja ne nette Diskussion hier aber ich muss mir (zu gegebenem Zeitpunkt) halt nochmal überlegen wie ichs genau mache, bzw den Thread ganz durchlesen. Wobei zur Zeit tendiere ich zu Hash-Maps. Mal sehn