[Python-de] dictionary > hauptspeicher

Diez B. Roggisch deets at web.de
Don Sep 22 13:23:49 CEST 2005


> ich habe eine sehr lange Liste von Strings, die ich sequentiell
> durchgehen muß. In dieser Liste gibt es sehr viele Duplikate, die
> ich gern herausfiltern würde. Dummerweise ist jetzt die Liste so
> lang, daß das Dictionary zum Rausfiltern der Duplikate nicht mehr
> in den Hauptspeicher passt.
>
> Tjo, also irgendwie brauche ich da wohl eine Datenstruktur, die
> dann eben auf die Platte schreibt, sobald kein Hauptspeicher mehr
> da ist. Schön wäre natürlich, wenn nur selten vorkommende Strings
> auf Platte ausgelagert würden. Gibt es soetwas schon? Oder sollte
> man da Berkely DB oder etwas ähnliches verwenden?

Ja, sowas gibt: heisst datenbank :) Ob berkleydb dabei gut genug ist - KA. 
Abgesehen davon, das uU auch andere Herangehensweisen funktionieren:

Wenn deine strings laenger sind als ein MD5-hash, dann koenntest du im ersten 
schritt einen index aus

(hash, position_im_file) 

erstellen. Der sollte noch in den Speicher passen... Die sortierst du dann 
nach hash - und alle gleichen hashes pruefst du dann ueber die Datei auf 
echte gleichheit. Wahrscheinlich ist das noch nicht mal  notwendig. Als 
Ergebnis hast du dann eine Liste von eindeutigen Strings. Die Sortierst du 
nach file-postition - und dann gehst du die durch und schreibst halt die 
Ergebnisstrings weg. 

Die Verwendung von mmap ist dabei wohl auch angezeigt - habe ich aber nicht 
aus dem Kopp parat.

MfG Diez