Spezialisiertes set für Integers



  • Ich bräuchte ein std::set-Äquivalent für Integers, was nahe beieinanderliegende Elemente speichereffizient ablegen kann, indem es selbstständig entscheidet, für bestimmte Wertebereiche Bitmaps zu verwenden.

    Beispiel: im Bereich 0-300 Millionen befindet sich jeder 100. Wert im set -> daher lohnt sich für diesen Abschnitt die Speicherung der Werte als Baum oder sortierter Vektor wie auch in einem normalen set.

    Im Bereich 500-600 Millionen befindet sich jeder 2. Wert im Set -> die Werte sind für diesen Abschnitt als Bitmap abzulegen, ein Baum wäre hier Platzverschwendung.

    Bevor ich einen solchen Container selbst schreibe, wollte ich fragen, ob jemand eine vorhandene Implementierung schon kennt? Ist vielleicht etwas speziell, aber nicht so speziell, dass es das wahrscheinlich nicht schon gibt.



  • Moment, was hast du vor?

    Datenstrukturen sind eigentlich so angelegt, dass sie sich nicht dynamisch in ihrem Verhalten ändern, sondern sich in der Theorie für alle Größen gleich verhalten.



  • Da ist einiges unklar.

    - Sind die Daten statisch, tust du alles auf einmal einmal einfügen und dann nur noch abfragen, oder wechseln sich einfügen/abfragen immer ab?
    - Sind die Häufungen im voraus bekannt?
    - Ist das *wirklich* performance-kritisch? Von wie vielen Einträgen und wie vielen Queries sprechen wir?
    - Bist du sicher, dass du schneller als unordered_set sein kannst?



  • Skym0sh0 schrieb:

    Moment, was hast du vor?

    Ich stopfe laufend Integers in das set und schaue noch öfter, ob ein Wert schon drin ist. Das war's eigentlich schon.

    Skym0sh0 schrieb:

    Datenstrukturen sind eigentlich so angelegt, dass sie sich nicht dynamisch in ihrem Verhalten ändern, sondern sich in der Theorie für alle Größen gleich verhalten.

    Deswegen kommt std::set und andere allgemeine set-Implementierungen nicht in Frage. Ich würde es auch nicht unbedingt als Verhaltensänderung bezeichnen, die interne Repräsentation der Werte ist ja nur ein Implementationsdetail. Aber trotzdem ein wichtiges Detail, da sonst der RAM-Verbrauch aus dem Ruder laufen würde.



  • unordered_fat schrieb:

    - Sind die Daten statisch, tust du alles auf einmal einmal einfügen und dann nur noch abfragen, oder wechseln sich einfügen/abfragen immer ab?

    Wechselt sich ständig ab. Gelöscht wird aber nie.

    unordered_fat schrieb:

    - Sind die Häufungen im voraus bekannt?

    Nicht unbedingt. Das kann für jeden Datensatz wieder anders sein.

    unordered_fat schrieb:

    - Ist das *wirklich* performance-kritisch? Von wie vielen Einträgen und wie vielen Queries sprechen wir?
    - Bist du sicher, dass du schneller als unordered_set sein kannst?

    Nein, das ist überhaupt nicht performancekritisch, darf ruhig langsamer als ein normales set sein (höchstens 200 Zugriffe pro Sekunde). Aber es ist speicherkritisch (hunderte Millionen Einträge).



  • Wie lang sind die einzelnen "Integer"?



  • TyRoXx schrieb:

    Wie lang sind die einzelnen "Integer"?

    Normalerweise 64 bit, kann auch 32 bit sein.





  • Falls falsche Antworten aktzeptabel sind würde sich auch ein Bloom-Filter anbieten, der braucht dann quasi gar kein Speicher: http://en.wikipedia.org/wiki/Bloom_filter



  • Es gibt auch Ausnahmen, aber meist brauche ich solche sets für IDs von Datensätzen, daher wäre Korrektheit wichtig.

    unordered_fat schrieb:

    In dem Fall: https://code.google.com/p/cpp-btree/

    Google's btree::set ist super und ich verwende es bereits. Auch wenn es als allgemeiner Container mit nur 10% Overhead selbst für kleine Objekte spitze ist (besonders beim Vergleich mit den 4400% Overhead von std::set), kann ein nichtspezialisierter Container selbst bei 0% Overhead nie unter die 64 bit selbst kommen. Genau das würde ich aber gerne erreichen, bei dicht popularisierten Bereichen z.B. höchstens 2 bit pro Element.

    Hab derweil mal eine quick and dirty-Implementation angefangen, bin bisher bei 6x weniger Speicherverbrauch als btree::set und ist sogar schneller. Aber es fehlen Iteratoren, erase() und viele andere Dinge für std::set-Kompatibilität...


Log in to reply