Wie verwalte ich so viele Daten?

[Medium]

Zitat von alzaimar:

Verkettete Listen kann man nicht binär durchsuchen. Wir vergleichen Verfahren und die binäre Suche benötigt nun mal ein Array, scheidet also *aus*.

Den wahlfreien Zugriff kann man sich auf zwei Weisen herstellen:
1) Ein Verweis-Array mitführen (was jedoch selbst dann das Problem hat, dass es Verschiebungen darin gibt. Es lohnt also nur, wenn die Daten erheblich länger ausfallen und somit beim Umkopieren ein echter Unterschied existiert)
2) 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, bzw. bei den verbesserten Versionen nochmals weniger. So mache ich es in einem Programm, bei dem eine Liste von rund 30 Mio Punkten im Raum verarbeitet wird, und ich bin eigentlich recht zufrieden mit der Geschwindigkeit. Wenn ich Zeit und Muße hab, werd ich das mal testweise mit einer Hashmap bauen.

Zitat von alzaimar:

Der Hash wird nicht gespeichert, sondern dient zur Berechnung des Indexes in der Hashmap.

Schon klar, aber das Array muss ja genau so viele Indizes aufweisen, wie es Hashes geben kann. Bei einem z.B. 2 Byte Hash hast du ein schlankes Array von nur 64k, aber bei über 1 Mio Einträgen etliche Kollisionen. Bei einem 4 Byte Hash sind wir wieder bei einem Array(Cardinal). Lösung 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.

Zitat von alzaimar:

Nein. Hinterher einmalig Sortieren ist immer schneller, als ständig die Ordnung der Liste zu gewährleisten.

Kommt darauf an. Ich hab in einem Fall die Situation, dass ich "Snapshots" einer Range einer Liste anzeigen lasse, während diese noch befüllt wird. Das passiert alle paar hundert Millisekunden, und würde ich hier jedes Mal den Bereich erst noch sortieren müssen, wäre es vorbei mit der Schnelligkeit. Es gibt also tatsächlich solche Fälle

Zitat von alzaimar:

Meine Rechnung stimmt auch bei der Vereinfachung. Die korrekte Zahl liegt bei ca. 17 Mio. Die 19 Mio als Überschlag sind also innerhalb eines Fehlers von 10%. Nicht schlecht für eine grobe Schätzung.

Den Teil habe ich bis jetzt nicht ganz verstanden. 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

Zitat von alzaimar:

Wenn Du natürlich eine deiner Suchverfahren mit einer verketteten Liste durchführen kannst, wäre das Ergebnis zwar immer noch langsamer als eine Hashmap, dafür hätten wir aber eine Struktur mit einem akzeptablen weil deterministischen Worst Case. Diese Implementierung würde ich dann als akzeptable Alternative zu Hashmaps, Skiplisten, DAWGs etc. ansehen.

Ich wäre nie auf die Idee gekommen, ein Array als Container zu verwenden, eben weil es dynamisch sein müsste, mindestens aber unglaublich viel Kopiererei stattfinden würde. 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.


Dass Hashmaps zur Verwaltung von Strings eigentlich immer überlegen sind kann ich gut nachvollziehen, und in diesem Zusammenhang hab ich sie auch bisher nur gesehen. Bei numerischen bzw. binären Werten sind sie mir eigentlich noch nicht über den Weg gelaufen.