Kürzlich ist in einem der Projekte ein Problem aufgetreten: Es gibt eine Reihe von Mengen (Set), die effizient im RAM gespeichert werden müssen. Weil es viele Sets gibt, aber wenig Speicher. Und wir müssen etwas dagegen tun.
Da die Sprache, in der dies alles geschrieben ist, C # ist, dh die Nuancen. Das Standard-HashSet <int> verwendet nämlich 16 Bytes, um eine Zahl zu speichern. Der Füllfaktor wirkt sich auch aus. Es gibt effizientere Implementierungen (eines Tages werde ich darüber schreiben), aber andererseits können Sie dumm in Arrays 4 Bytes pro Nummer speichern (Sie müssen Ints speichern), was ziemlich effizient ist. Aber kann es weiter reduziert werden?
Ich muss sofort sagen, dass ich keine Antwort darauf habe, wie es am besten geht, vielleicht existiert es nicht, weil mit der Verteilung spezifischer Daten viele Faktoren verbunden sind. Aber es gibt Ideen, die ich teilen werde: Welche Optionen gibt es, um Speicherplatz zu sparen? Ich empfehle Ihnen auch, vor dem Lesen des Beitrags selbst zu überlegen, schließlich ist dies ein gutes Training für den Verstand. Um genau zu sein, werde ich das Problem wie folgt formulieren:
Es gibt eine Reihe nicht negativer eindeutiger Ints (32 Bit). Es ist erforderlich, sie aus Operationen effizient im RAM zu speichern - einen Satz zu erstellen und alle Elemente abzurufen. Es ist nicht erforderlich, Elemente nach Index abzurufen, neue hinzuzufügen oder zu löschen.
Der Artikel enthält viele Buchstaben und Zahlen und kein einziges Bild (mit Ausnahme einer gepackten Katze auf dem KDPV).
, , .. , . . - , - , . - , - .
, — , .
, : , . 10
Wir haben also Basisdaten - ein Array von Ints, 4 Bytes (32 Bit) pro Nummer. Wir werden auf diesem Indikator aufbauen.
Zunächst möchte ich eine brillante Idee zum Ausdruck bringen: Damit eine Zahl weniger als 32 Bit im Speicher belegt, müssen Sie sie mit weniger Bit speichern. Coole Idee, oder? Und die Leute bekommen dafür Ruhm und Anerkennung. Je schlimmer ich bin.
Lyrischer Exkurs: Vor einigen Jahren haben Spezialisten der Russischen Eisenbahnen herausgefunden, dass der Zug schneller und leiser fährt, wenn Sie die Räder rund und gleich groß machen.
Zahlen nach Größe trennen
Eine einfache Lösung zum Starten: Zahlen von 0 bis 255 können mit 1 Byte pro Zahl gespeichert werden, bis zu 65536 mit zwei, bis zu 16777216 mit drei. Daher die erste Lösung:
Wir erstellen 4 Arrays, in einem speichern wir Zahlen nach 1 Byte, in dem anderen nach 2, im dritten nach 3, und was ich im vierten vorschlage, selbst zu erraten.
Klatschen, und wir sparen bereits. Aber warum bleibst du wo du warst? Verwenden wir 32 Arrays! Und speichern Sie Zahlen um 1, 2 ... Bits. Es ist noch wirtschaftlicher geworden.
Was ist ein Array? Dies ist ein Zeiger auf einen Speicherblock (8 Byte), eine Länge und für C # auch einen Speicher für das Array-Objekt selbst (20 Byte). Insgesamt kostet uns jedes Array 32 Bytes (tatsächlich benötigt ein Objekt in C # mindestens 24 Bytes in Schritten von 8, von denen 20 Bytes pro Objekt sind, und 4 ist für das, was übrig bleibt oder für die Ausrichtung dumm ist). Nachfolgend Berechnungen für ein 64-Bit-System. Bei 32 Bit sind Zeiger 2-mal kleiner, die Ausrichtung ist ebenfalls 4, sodass fast alles 2-mal wirtschaftlicher ist.
Wofür ist diese Passage? Außerdem verschlingen 32 Arrays 1 KB Speicher nur für sich. Was tun? Und alles ist einfach: Wir werden diese 32 Arrays in einem Array speichern!
Im ersten Element speichern wir die Länge eines Ein-Bit-Arrays, dann das Array selbst, dann die Länge für zwei Bits usw. Infolgedessen gibt es nur 32 Bytes Overhead und effizienten Speicher.
Ein neugieriger Leser (ich habe diesen Satz immer gemocht) kann ein bestimmtes Problem bemerken: Um Zahlen von einem Bit zu speichern, geben wir zuerst 2 Bits für die Länge (0, 1 oder 2) und dann 2 Bits für die Zahlen selbst aus. Sie können jedoch nur 2 Bits ausgeben: Das erste Bit - gibt es eine 0, das zweite - gibt es eine 1.
Wir haben gerade eine Bitmap erstellt . Mit dieser Methode können Sie sich keine Sorgen machen und Zahlen von 0 bis 255 speichern - es gibt eine Zahl - 1, keine - 0. Und 32 Bytes dafür ausgeben (8 Bits in einem Byte * 32 = 256). Natürlich nimmt mit jedem neuen Wert die Effektivität der Karte ab. Jene. Um alle Ints zu speichern, benötigen wir 536870912 Bytes ... Es ist ein bisschen zu viel. Wann also aufzuhören: bei 256, bei 16, bei 65536 - hängt von den Daten ab. Lass es 256 sein. Ich mag diese Nummer, sie ist wunderschön.
Jene. Wir speichern die ersten 256 Zahlen mit einer Bitmap, dann speichern wir die Länge von Zahlen einer bestimmten Länge in Bits und die Zahlen selbst.
Aber schauen Sie, was passiert: Zahlen von 0 bis 511 benötigen 9 Bits zum Speichern. Gleichzeitig sind wir Zahlen von 0 bis 255 - wir haben bereits gespeichert. Jene. im Bereich von 9 Bit kann die Nummer 12 nicht gefunden werden. Nur 256 und mehr. Warum also in 9 Bit speichern, wenn Sie eine Zahl von 0 bis 255 speichern und dann die fehlenden 256 in Ihrem Kopf hinzufügen können? Noch ein Bit gespeichert! Natürlich wird jeder nächste Bereich auch 1 Bit wirtschaftlicher sein. Wir sind großartig!
Was kannst du noch tun? Und Sie können sich die Daten ansehen. Wenn sie sehr dicht sind (1,2,3,5,6), können Sie nicht die Zahlen selbst speichern, sondern diejenigen, die nicht existieren (4). Jene. Anstatt bedingte 5 Zahlen zu speichern, speichern wir eine. Eine einfache Regel: Wir haben mehr als die Hälfte - wir behalten diejenigen, die nicht existieren, sonst umgekehrt. Wo lagern? Und in der Länge! Schauen Sie: Um 10 Bit lange Zahlen zu speichern, benötigen wir 11 Bit (von 0 bis einschließlich 1024). Gleichzeitig können Sie 2048 Werte in 11 Bit verschieben, und wir verwenden nur 1025. Wir speichern also: positive Länge - wir speichern Zahlen. Negativ - wir speichern, was nicht ist. Ich schlage vor, dass der Leser selbst eine detaillierte Berechnung als unabhängige Übung vornimmt (weil ich nicht sicher bin, ob alles zusammenpasst, also werde ich so tun, als wäre es notwendig).
Als Ergebnis haben wir: ein Array, in dem die ersten 16 Bytes eine Bitmaske für das Vorhandensein von Zahlen von 0 bis 255 sind, dann - die Länge mit einer Angabe - speichern wir die Zahlen oder ihre Abwesenheit, die Zahlen selbst, die Bitlänge für die nächsten usw.
Nachdem Sie dies implementiert haben und auch ohne Fehler, werden Sie wahrscheinlich direkt zum Durke übergehen. Nachfolgende Programmierer, die versuchen, diesen Code zu verstehen, werden Ihnen folgen. Probieren wir also einige weitere Optionen aus.
Wir denken über Ordnung nach
Aussehen. Wir haben ein Array. Was hat er im Gegensatz zu vielen? Und er hat: die Reihenfolge der Elemente. Dies sind zusätzliche Informationen, die wir noch nicht verwendet haben. Was können Sie dagegen tun?
Und Sie können nicht die Elemente selbst speichern, sondern den Unterschied zwischen ihnen:
1,2,3,4,8 => 1,1,1,1,4 Dh
. Wir speichern das erste so wie es ist, das zweite - wir addieren den Wert des ersten zum zweiten usw. Was gibt es uns? Und die Tatsache, dass, wenn wir das Array im Voraus sortieren , die darin enthaltenen Werte im Allgemeinen kleiner werden und sie in weniger Bits gespeichert werden können.
Zusätzlich sind gemäß dem Zustand des Problems alle Elemente unterschiedlich, d.h. Wir können immer noch eins von der Differenz subtrahieren, um Bits zu speichern:
1,2,3,4,8 => 1,1,1,1,4 => 1,0,0,0,3
Dies ist nicht schwierig, also warum und nein.
Aber jetzt ist das Problem gelöst. weil Jetzt können wir Zahlen nicht unabhängig speichern, sondern nur in derselben Reihenfolge, dann ist die Methode mit einem Array und Längen nicht mehr geeignet. Es ist notwendig, sich etwas anderes auszudenken, weil Alle Nummern müssen der Reihe nach gespeichert werden.
Speichern Sie die Länge der Nummer in Bits vor der Nummer selbst.
Keine schlechte Option. Die Zahl dauert 1 bis 32 Bit, d.h. Für die Länge benötigen wir 5 Bits und dann die Zahl selbst. Der Einfachheit halber können Sie Extremfälle abschneiden (nun, warum speichern wir dort? Pennies!) Oder umgekehrt, sie separat markieren - zum Beispiel, wenn die Länge 0 ist, bedeutet dies die Zahl 0, wenn die Länge 1 ist - die Zahl - 1, wenn die Länge 2 ist, dann die nächsten 2 Bit Nummer 2,3,4,5 (wir wissen bereits, dass wir zu etwas wechseln können, das nicht sein kann) usw.
Oder kann die Länge einer Nummer in der Nummer selbst gespeichert werden?
Menge variabler Länge
Egal wie wir als Erste diese Frage stellen, es gibt also eine Standardlösung. Wird zum Speichern von Zeichenfolgen in UTF-8 und an vielen anderen Orten verwendet. Die Bedeutung ist einfach.
Wenn die Zahl zwischen 0 und einschließlich 127 liegt, speichern wir sie in 1 Byte (obwohl wir nur 7 Bits verwendet haben). Wenn mehr, setzen Sie das 8. Bit auf 1 und verwenden Sie das nächste Byte auf die gleiche Weise (7 Bit, fehlen - Kontrollkästchen und nächstes). Jene. kleine Zahlen werden in einem Byte gespeichert, etwas mehr - in zwei und so weiter bis zu 5.
Man kann sagen - fuu ... wir haben nur mit den Bits gespielt, und dann gingen die Bytes, nicht cool! Ja, es ist nicht cool, andererseits ist das Arbeiten mit Bytes immer noch einfacher als mit Bits, etwas weniger Einsparungen, aber die Arbeitsgeschwindigkeit ist höher und der Code ist klarer. Aber ... ein bisschen pro Byte auszugeben ist irgendwie nicht sehr cool, vielleicht gibt es bessere Lösungen?
Werte als Flags verwenden
Lassen Sie uns alle Überlegungen überspringen und sofort entscheiden. Wir werden es wie folgt speichern:
- Zahlen von 0 bis 252 werden in einem Byte gespeichert. Wenn mehr, dann:
- Wenn die Zahl zwischen 252 und 252 + 256 = 508 liegt, setzen wir den Wert 252 und im nächsten Byte ist die Zahl 252 (ja, wir wissen bereits, wie man Werte verschiebt).
- Wenn zwischen 252 + 256 und 252 + 256 + 65536, setzen Sie 253 und verwenden Sie die nächsten 2 Bytes, um die Nummer selbst zu speichern - ein unnötiger Unterschied
- Wenn zwischen 252 + 256 + 65536 und 252 + 256 + 65536 + 16777216, setzen Sie 254 und 3 Bytes
- sonst - 255 und 4 Bytes.
Ist das ein guter Weg? Alles ist relativ. In einem Byte können wir Werte bis zu 252 verschieben, während in VLQ nur bis zu 127, aber nur 508 in 2 Bytes und bereits 16383 in VLQ. Die Methode ist gut, wenn Ihre Zahlen dicht genug sind, und hier werden wir gewinnen. Das Gute an der Methode ist jedoch, dass sie an verschiedene Bereiche angepasst werden kann. Wenn wir beispielsweise wissen, dass die meisten Zahlen zwischen 10.000 und 50.000 liegen, können wir sie immer in zwei Bytes speichern. Wenn jedoch eine große Zahl herauskommt, schreiben wir 65535 und verwenden bereits 4. Tatsächlich optimieren wir die Speicherung des erforderlichen Bereichs auf Kosten einer ineffizienten Speicherung nicht notwendig.
Fazit
Wir haben die wichtigsten Möglichkeiten untersucht, um Speicherplatz zu sparen (tatsächlich ist meine Vorstellungskraft erschöpft, aber ich werde es nicht zugeben). Diese Techniken können kombiniert, für andere Aufgaben verwendet und an die jeweilige Situation angepasst werden. Was ist am Ende die beste Technik? Es hängt alles von Ihren Daten ab. Nimm sie und probiere sie aus. Glücklicherweise ist es nicht notwendig, alles auf einmal vollständig zu implementieren. Es ist einfach genug, Code zu schreiben, der einfach die Länge bewertet. Und implementieren Sie nach der Bewertung bereits, was Ihnen gefallen hat.
Vergessen Sie nicht die Geschwindigkeit dieser ganzen Sache: Sind Sie bereit, viel Zeit damit zu verbringen, Daten vorzubereiten oder abzurufen? Lohnt es sich, einen Kampf mit Bits zu beginnen, oder sollten Sie nicht unter Bytes gehen? Reicht es aus, häufige Situationen zu optimieren und seltene Situationen mit ineffektiver Implementierung zu belassen? Ist es möglich, abhängig von den Daten unterschiedliche Speichermethoden zu verwenden (zum Beispiel ist es dumm, bis zu 8 Bytes in einem Array zu speichern, da Nebenkosten den gesamten Gewinn verschlingen und ab 1 Byte - im Allgemeinen in einem Pseudo-Array eines Elements, d. H. In der Nummer).
Auch ein paar Worte zur Komprimierung: Hier wird es nicht sehr effektiv sein. Komprimierungsalgorithmen mögen Wiederholungen sehr, aber es gibt hier nicht sehr viele davon. Wenn Sie eine bedingte Zip-Datei verwenden, die aus LZ77 + Huffman besteht, ist es unwahrscheinlich, dass mit LZ77 etwas Nützliches herauskommt, aber Huffman versucht möglicherweise, Bytes zu speichern. Also wird Zip halb nutzlos sein. Aber die Geschwindigkeit wird sehr, sehr stark sinken.
Die Situationen, in denen wir wissen, dass wir viele Sets haben und sie alle zusammen mit verschiedenen Slices speichern können, wurden noch nicht berücksichtigt. Hier gestehe ich - ich bin mir nicht sicher, ob es klappen wird. Sofort habe ich mir keine Optionen ausgedacht. Aber mir wurde klar, dass es schwierig werden würde. Möglicherweise haben Sie jedoch unterschiedliche Meinungen.
Teilen Sie also Ihre Ideen in den Kommentaren mit, vielleicht habe ich einen offensichtlichen Elefanten verpasst, der noch mehr Bytes spart und ein solches Ergebnis erzielt, dass die Hausfrauen aus der Waschmittelwerbung (die für einen Tropfen ausreicht) uns alle beneiden werden!