riesiger bitvector und Adressierung der bits

GentleGiant

Hi, ich habe ein Implementierungsproblem, über welches ich mir schon geraume Zeit den Kopf zerbreche ...

- ich benötige einen (spärlich besetzten) bitvector
- allerdings beträgt die Länge ca 90^256

den bitvector zu implementieren ist garnicht das problem
(einfach häppchenweise im Speicher ablegen)

ich sehe das Problem eher darin, das ich ja ca 1700 bits nur für die Adresse einens bits im vector brauche, und wie ich die Adresse darstellen soll,
bzw. wie ich die Adressierung allgemein umsetzen soll, ist mir schleierhaft.

Auf einem 64bit System sind das ja immernoch 25 ints,
und dann 25 mal indirekt zu addressieren frisst imho viel zu viel Performance

jemand eine bessere Idee?

TyRoXx

Als Adresse kannst du ein std::array<std::size_t, N> mit passendem N nehmen. Spärlich besetzt hört sich nach Hashset an. Zusammen macht das also std::unordered_set<std::array<std::size_t, N>> .

Techel

Die Frage ist eher ob es vielleicht andere Möglichkeiten zur Lösung deinen Problems gibt.
Was hast du denn genau vor?

GentleGiant

TyRoXx schrieb:

Als Adresse kannst du ein std::array<std::size_t, N> mit passendem N nehmen. Spärlich besetzt hört sich nach Hashset an. Zusammen macht das also std::unordered_set<std::array<std::size_t, N>> .

das hört sich gut an, peinlich das ich darauf nicht gekommen bin

Um die Frage nach dem Warum zu beantworten :

ich benötige eine sehr speichersparende Möglichkeit um viele Strings im Speicher zu halten.

- die Struktur muss dabei eigentlich nur insert und contains unterstützen.
- angefangen habe ich mit einem prefix baum, allerdings benötigen dort schon die Zeiger auf die Kinder viel Speicher
- ich möchte nun versuchen den Baum in ein Array einzubetten, dann benötige ich für jede Vater-Kind-Relation nur noch ein bit ...

daraus ergibt sich auch die Länge die Bitvectors ( ich hoffe ich habe richtig gerechnet )
Die Strings werden über einem Alphabet der Grösse 90 gebildet, max length ist 255, ergibt dann maximale Tiefe im Baum von 256, und der grösste Index in der Einbettung müsste dann 90^256 sein .. ( alle Angaben gerundet )

Da die String meist gleich anfangen, und sich auch sonst eher am Ende unterscheiden, sollte imho so ein Baum die speicher-sparenste Möglichkeit sein
( im Speicher komprimieren möchte ich irgendwie nicht, weil dann das contains meiner Meinung nach total lahm wird, weil ich ja entpacken und suchen muss )

TyRoXx

GentleGiant schrieb:

ich benötige eine sehr speichersparende Möglichkeit um viele Strings im Speicher zu halten.

Das bezweifle ich bereits. Was ist denn die konkrete Anwendung hier? Warum tut es nicht eine Datenbank?
Wenn du mir beantworten kannst, um welchen Faktor zum Beispiel SQLite tatsächlich zu langsam ist, kann man anfangen zu optimieren.
Auf welcher Kategorie von Hardware soll das überhaupt laufen?

volkard

GentleGiant schrieb:

ich benötige eine sehr speichersparende Möglichkeit um viele Strings im Speicher zu halten.

- die Struktur muss dabei eigentlich nur insert und contains unterstützen.

Und vielleicht in der einen Richtung unglaubhaft? Bloomfilter, quasi 4 Bits pro beliebig langem abzuspeichernden String.

In beiden sicher, trie, quasi nur ein byte pro abzuspeicherndem byte.

Möchstest Du aber *sehr* viele beliebige Strings anspeichern und sicher schnell befragen können, und arbeitest für bekannte Hochlohnzahler wie die arabischen Spekulanten, dann ruf mich an, ich forsche gern ein Jahr vergebens bezahlt.