Gibt es eine Optimierung für den wahlfreien Zugriff auf ein sehr großes Array, wenn der Wert in 95% der Fälle entweder 0 oder 1 ist?

Gibt es eine mögliche Optimierung für den wahlfreien Zugriff auf ein sehr großes Array (ich verwende derzeit uint8_tund frage, was besser ist)?

uint8_t MyArray[10000000];

wenn der Wert an einer beliebigen Position im Array ist

• 0 oder 1 für 95% aller Fälle,
• 2 in 4% der Fälle,
• zwischen 3 und 255 in den anderen 1% der Fälle?

Gibt es etwas Besseres als ein uint8_t Array, das dafür verwendet werden kann? Es sollte so schnell wie möglich sein, das gesamte Array in zufälliger Reihenfolge zu durchlaufen, und dies ist sehr belastend für die RAM-Bandbreite. Wenn also mehr als ein paar Threads dies gleichzeitig für verschiedene Arrays tun, gilt derzeit die gesamte RAM-Bandbreite ist schnell gesättigt.

Ich frage, da es sich sehr ineffizient anfühlt, ein so großes Array (10 MB) zu haben, wenn tatsächlich bekannt ist, dass fast alle Werte außer 5% entweder 0 oder 1 sind. Wenn also 95% aller Werte im Array würde tatsächlich nur 1 Bit anstelle von 8 Bit benötigen, würde dies die Speichernutzung um fast eine Größenordnung reduzieren. Es scheint, dass es eine speichereffizientere Lösung geben muss, die die dafür erforderliche RAM-Bandbreite erheblich reduziert und infolgedessen auch für den wahlfreien Zugriff erheblich schneller ist.

Eine einfache Möglichkeit, die in den Sinn kommt, besteht darin, ein komprimiertes Array von 2 Bits pro Wert für die allgemeinen Fälle und ein getrenntes Array mit 4 Bytes pro Wert (24 Bit für den ursprünglichen Elementindex, 8 Bit für den tatsächlichen Wert usw. (idx << 8) | value)) für das zu sortieren andere.

Wenn Sie einen Wert nachschlagen, führen Sie zuerst eine Suche im 2bpp-Array durch (O (1)). Wenn Sie 0, 1 oder 2 finden, ist dies der gewünschte Wert. Wenn Sie 3 finden, bedeutet dies, dass Sie es im sekundären Array nachschlagen müssen. Hier führen Sie eine binäre Suche durch, um nach dem Index Ihres Interesses zu suchen, der um 8 nach links verschoben ist (O (log (n) mit einem kleinen n, da dies 1% sein sollte), und extrahieren Sie den Wert aus dem 4- Byte Ding.

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    main_arr.resize((size+3)/4);
    for(size_t idx = 0; idx < size; ++idx) {
        uint8_t in = source[idx];
        uint8_t &target = main_arr[idx>>2];
        // if the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

Für ein Array wie das von Ihnen vorgeschlagene sollte dies 10000000/4 = 2500000 Bytes für das erste Array plus 10000000 * 1% * 4 B = 400000 Bytes für das zweite Array dauern. Daher werden 2900000 Bytes, dh weniger als ein Drittel des ursprünglichen Arrays, und der am häufigsten verwendete Teil im Speicher zusammengehalten, was für das Caching gut sein sollte (es kann sogar für L3 passen).

Wenn Sie mehr als 24-Bit-Adressierung benötigen, müssen Sie den "Sekundärspeicher" optimieren. Eine einfache Möglichkeit, es zu erweitern, besteht darin, ein Zeigerarray mit 256 Elementen zu haben, um die oberen 8 Bits des Index umzuschalten und wie oben beschrieben an ein indiziertes sortiertes 24-Bit-Array weiterzuleiten.

Schneller Benchmark

#include <algorithm>
#include <vector>
#include <stdint.h>
#include <chrono>
#include <stdio.h>
#include <math.h>

using namespace std::chrono;

/// XorShift32 generator; extremely fast, 2^32-1 period, way better quality
/// than LCG but fail some test suites
struct XorShift32 {
    /// This stuff allows to use this class wherever a library function
    /// requires a UniformRandomBitGenerator (e.g. std::shuffle)
    typedef uint32_t result_type;
    static uint32_t min() { return 1; }
    static uint32_t max() { return uint32_t(-1); }

    /// PRNG state
    uint32_t y;

    /// Initializes with seed
    XorShift32(uint32_t seed = 0) : y(seed) {
        if(y == 0) y = 2463534242UL;
    }

    /// Returns a value in the range [1, 1<<32)
    uint32_t operator()() {
        y ^= (y<<13);
        y ^= (y>>17);
        y ^= (y<<15);
        return y;
    }

    /// Returns a value in the range [0, limit); this conforms to the RandomFunc
    /// requirements for std::random_shuffle
    uint32_t operator()(uint32_t limit) {
        return (*this)()%limit;
    }
};

struct mean_variance {
    double rmean = 0.;
    double rvariance = 0.;
    int count = 0;

    void operator()(double x) {
        ++count;
        double ormean = rmean;
        rmean     += (x-rmean)/count;
        rvariance += (x-ormean)*(x-rmean);
    }

    double mean()     const { return rmean; }
    double variance() const { return rvariance/(count-1); }
    double stddev()   const { return std::sqrt(variance()); }
};

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    main_arr.resize((size+3)/4);
    for(size_t idx = 0; idx < size; ++idx) {
        uint8_t in = source[idx];
        uint8_t &target = main_arr[idx>>2];
        // if the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

volatile unsigned out;

int main() {
    XorShift32 xs;
    std::vector<uint8_t> vec;
    int size = 10000000;
    for(int i = 0; i<size; ++i) {
        uint32_t v = xs();
        if(v < 1825361101)      v = 0; // 42.5%
        else if(v < 4080218931) v = 1; // 95.0%
        else if(v < 4252017623) v = 2; // 99.0%
        else {
            while((v & 0xff) < 3) v = xs();
        }
        vec.push_back(v);
    }
    populate(vec.data(), vec.size());
    mean_variance lk_t, arr_t;
    for(int i = 0; i<50; ++i) {
        {
            unsigned o = 0;
            auto beg = high_resolution_clock::now();
            for(int i = 0; i < size; ++i) {
                o += lookup(xs() % size);
            }
            out += o;
            int dur = (high_resolution_clock::now()-beg)/microseconds(1);
            fprintf(stderr, "lookup: %10d µs\n", dur);
            lk_t(dur);
        }
        {
            unsigned o = 0;
            auto beg = high_resolution_clock::now();
            for(int i = 0; i < size; ++i) {
                o += vec[xs() % size];
            }
            out += o;
            int dur = (high_resolution_clock::now()-beg)/microseconds(1);
            fprintf(stderr, "array:  %10d µs\n", dur);
            arr_t(dur);
        }
    }

    fprintf(stderr, " lookup |   ±  |  array  |   ±  | speedup\n");
    printf("%7.0f | %4.0f | %7.0f | %4.0f | %0.2f\n",
            lk_t.mean(), lk_t.stddev(),
            arr_t.mean(), arr_t.stddev(),
            arr_t.mean()/lk_t.mean());
    return 0;
}

(Code und Daten werden in meinem Bitbucket immer aktualisiert)

Der obige Code füllt ein 10M-Element-Array mit zufälligen Daten, die als OP in ihrem Beitrag angegeben verteilt sind, initialisiert meine Datenstruktur und dann:

• führt eine zufällige Suche von 10 Millionen Elementen mit meiner Datenstruktur durch
• macht das gleiche durch das ursprüngliche Array.

(Beachten Sie, dass bei einer sequentiellen Suche das Array immer um ein Vielfaches gewinnt, da dies die cachefreundlichste Suche ist, die Sie durchführen können.)

Diese beiden letzten Blöcke werden 50 Mal wiederholt und zeitlich festgelegt. Am Ende werden der Mittelwert und die Standardabweichung für jede Art der Suche berechnet und zusammen mit der Beschleunigung (lookup_mean / array_mean) gedruckt.

Ich habe den obigen Code mit g ++ 5.4.0 ( -O3 -staticplus einige Warnungen) unter Ubuntu 16.04 kompiliert und auf einigen Computern ausgeführt. Die meisten von ihnen verwenden Ubuntu 16.04, einige ältere Linux, andere neuere Linux. Ich denke nicht, dass das Betriebssystem in diesem Fall überhaupt relevant sein sollte.

            CPU           |  cache   |  lookup (µs)   |     array (µs)  | speedup (x)
Xeon E5-1650 v3 @ 3.50GHz | 15360 KB |  60011 ±  3667 |   29313 ±  2137 | 0.49
Xeon E5-2697 v3 @ 2.60GHz | 35840 KB |  66571 ±  7477 |   33197 ±  3619 | 0.50
Celeron G1610T  @ 2.30GHz |  2048 KB | 172090 ±   629 |  162328 ±   326 | 0.94
Core i3-3220T   @ 2.80GHz |  3072 KB | 111025 ±  5507 |  114415 ±  2528 | 1.03
Core i5-7200U   @ 2.50GHz |  3072 KB |  92447 ±  1494 |   95249 ±  1134 | 1.03
Xeon X3430      @ 2.40GHz |  8192 KB | 111303 ±   936 |  127647 ±  1503 | 1.15
Core i7 920     @ 2.67GHz |  8192 KB | 123161 ± 35113 |  156068 ± 45355 | 1.27
Xeon X5650      @ 2.67GHz | 12288 KB | 106015 ±  5364 |  140335 ±  6739 | 1.32
Core i7 870     @ 2.93GHz |  8192 KB |  77986 ±   429 |  106040 ±  1043 | 1.36
Core i7-6700    @ 3.40GHz |  8192 KB |  47854 ±   573 |   66893 ±  1367 | 1.40
Core i3-4150    @ 3.50GHz |  3072 KB |  76162 ±   983 |  113265 ±   239 | 1.49
Xeon X5650      @ 2.67GHz | 12288 KB | 101384 ±   796 |  152720 ±  2440 | 1.51
Core i7-3770T   @ 2.50GHz |  8192 KB |  69551 ±  1961 |  128929 ±  2631 | 1.85

Die Ergebnisse sind ... gemischt!

1. Im Allgemeinen gibt es auf den meisten dieser Maschinen eine Art Beschleunigung, oder zumindest sind sie gleichwertig.
2. Die beiden Fälle, in denen das Array die Suche nach "intelligenten Strukturen" wirklich übertrifft, sind auf Computern mit viel Cache und nicht besonders ausgelastet: Der Xeon E5-1650 oben (15 MB Cache) ist eine Nacht-Build-Maschine, die derzeit recht untätig ist. Der Xeon E5-2697 (35 MB Cache) ist eine Maschine für Hochleistungsberechnungen, auch im Leerlauf. Es macht Sinn, dass das ursprüngliche Array vollständig in den riesigen Cache passt, sodass die kompakte Datenstruktur nur die Komplexität erhöht.
3. Auf der anderen Seite des "Leistungsspektrums" - aber wo das Array wieder etwas schneller ist, gibt es den bescheidenen Celeron, der mein NAS antreibt; Es hat so wenig Cache, dass weder das Array noch die "intelligente Struktur" überhaupt hineinpassen. Andere Computer mit ausreichend kleinem Cache arbeiten ähnlich.
4. Der Xeon X5650 muss mit einiger Vorsicht betrachtet werden - es handelt sich um virtuelle Maschinen auf einem ziemlich ausgelasteten Server mit zwei Sockets für virtuelle Maschinen. Es kann durchaus sein, dass es während des Tests, obwohl es nominell eine anständige Menge an Cache hat, mehrmals von völlig unabhängigen virtuellen Maschinen vorgezogen wird.

Eine andere Option könnte sein

• Überprüfen Sie, ob das Ergebnis 0, 1 oder 2 ist
• Wenn nicht, machen Sie eine regelmäßige Suche

Mit anderen Worten so etwas wie:

unsigned char lookup(int index) {
    int code = (bmap[index>>2]>>(2*(index&3)))&3;
    if (code != 3) return code;
    return full_array[index];
}

Dabei bmapwerden 2 Bits pro Element verwendet, wobei der Wert 3 "Sonstige" bedeutet.

Diese Struktur ist trivial zu aktualisieren, verbraucht 25% mehr Speicher, aber der große Teil wird nur in 5% der Fälle nachgeschlagen. Ob es eine gute Idee ist oder nicht, hängt natürlich wie üblich von vielen anderen Bedingungen ab. Die einzige Antwort ist also, mit der tatsächlichen Verwendung zu experimentieren.

Dies ist eher ein "langer Kommentar" als eine konkrete Antwort

Ich bezweifle, dass jemand Ihre Frage DIREKT beantworten kann (es sei denn, Ihre Daten sind etwas Bekanntes) (und mir ist nichts bekannt, das Ihrer Beschreibung entspricht, aber dann weiß ich nicht ALLES über alle Arten von Datenmustern für alle Arten von Anwendungsfällen). Spärliche Daten sind ein häufiges Problem beim Hochleistungsrechnen, aber es ist normalerweise "wir haben ein sehr großes Array, aber nur einige Werte sind ungleich Null".

Bei nicht bekannten Mustern wie dem, was ich für Ihr Muster halte, wird niemand direkt WISSEN, was besser ist, und es hängt von den Details ab: Wie zufällig ist der Direktzugriff - greift das System auf Cluster von Datenelementen zu oder ist es völlig zufällig wie von ein einheitlicher Zufallszahlengenerator. Sind die Tabellendaten völlig zufällig oder gibt es Sequenzen von 0 und dann Sequenzen von 1 mit einer Streuung anderer Werte? Die Lauflängencodierung würde gut funktionieren, wenn Sie einigermaßen lange Sequenzen von 0 und 1 haben, aber nicht funktionieren, wenn Sie ein "Schachbrett von 0/1" haben. Außerdem müssten Sie eine Tabelle mit "Startpunkten" führen, damit Sie sich relativ schnell an den entsprechenden Ort arbeiten können.

Ich weiß seit langer Zeit, dass einige große Datenbanken nur eine große Tabelle im RAM sind (in diesem Beispiel Teilnehmerdaten der Telefonzentrale), und eines der Probleme besteht darin, dass Caches und Seitentabellenoptimierungen im Prozessor ziemlich nutzlos sind. Der Anrufer ist so selten derselbe wie einer, der kürzlich jemanden angerufen hat, dass keine vorinstallierten Daten vorhanden sind, sondern nur rein zufällig. Große Seitentabellen sind die beste Optimierung für diese Art von Zugriff.

In vielen Fällen ist der Kompromiss zwischen "Geschwindigkeit und kleiner Größe" eines der Dinge, zwischen denen Sie beim Software-Engineering wählen müssen [bei anderen Engineering ist es nicht unbedingt ein so großer Kompromiss]. Daher ist "Verschwendung von Speicher für einfacheren Code" häufig die bevorzugte Wahl. In diesem Sinne ist die "einfache" Lösung wahrscheinlich schneller, aber wenn Sie den RAM "besser" nutzen, würde eine Optimierung der Tabellengröße eine ausreichende Leistung und eine gute Größenverbesserung bringen. Es gibt viele verschiedene Möglichkeiten, wie Sie dies erreichen können - wie in einem Kommentar vorgeschlagen, ein 2-Bit-Feld, in dem die zwei oder drei häufigsten Werte gespeichert sind, und dann ein alternatives Datenformat für die anderen Werte - eine Hash-Tabelle wäre meine erster Ansatz, aber eine Liste oder ein Binärbaum können auch funktionieren - wieder es hängt von den Mustern ab, wo Ihre "nicht 0, 1 oder 2" sind. Auch hier kommt es darauf an, wie die Werte in der Tabelle "verstreut" sind - befinden sie sich in Clustern oder sind sie eher gleichmäßig verteilt?

Ein Problem dabei ist jedoch, dass Sie die Daten immer noch aus dem RAM lesen. Sie geben dann mehr Code für die Verarbeitung der Daten aus, einschließlich Code, um mit dem "Dies ist kein allgemeiner Wert" fertig zu werden.

Das Problem bei den meisten gängigen Komprimierungsalgorithmen besteht darin, dass sie auf Entpackungssequenzen basieren, sodass Sie nicht zufällig darauf zugreifen können. Und der Aufwand, Ihre Big Data in Blöcke von beispielsweise 256 Einträgen gleichzeitig aufzuteilen und die 256 in ein uint8_t-Array zu dekomprimieren, die gewünschten Daten abzurufen und dann Ihre unkomprimierten Daten wegzuwerfen, ist höchst unwahrscheinlich Leistung - vorausgesetzt, das ist natürlich von Bedeutung.

Am Ende müssen Sie wahrscheinlich eine oder mehrere der Ideen in Kommentaren / Antworten implementieren, um zu testen, ob dies zur Lösung Ihres Problems beiträgt oder ob der Speicherbus immer noch der Hauptbeschränkungsfaktor ist.

Was ich in der Vergangenheit getan habe, ist eine Hashmap vor einem Bitset zu verwenden.

Dies halbiert den Speicherplatz im Vergleich zu Matteos Antwort, kann jedoch langsamer sein, wenn die Suche nach "Ausnahmen" langsam ist (dh es gibt viele Ausnahmen).

Oft ist "Cache jedoch König".

Wenn Ihre Daten kein Muster aufweisen, ist es unwahrscheinlich, dass eine sinnvolle Geschwindigkeits- oder Größenoptimierung vorliegt, und - vorausgesetzt, Sie zielen auf einen normalen Computer ab - 10 MB sind sowieso keine so große Sache.

Ihre Fragen enthalten zwei Annahmen:

1. Die Daten werden schlecht gespeichert, da Sie nicht alle Bits verwenden
2. Eine bessere Speicherung würde die Dinge schneller machen.

Ich denke, diese beiden Annahmen sind falsch. In den meisten Fällen besteht die geeignete Methode zum Speichern von Daten darin, die natürlichste Darstellung zu speichern. In Ihrem Fall ist dies das, für das Sie sich entschieden haben: ein Byte für eine Zahl zwischen 0 und 255. Jede andere Darstellung ist komplexer und daher - wenn alle anderen Dinge gleich sind - langsamer und fehleranfälliger. Um von diesem allgemeinen Prinzip abzulenken, benötigen Sie einen stärkeren Grund als möglicherweise sechs "verschwendete" Bits für 95% Ihrer Daten.

Für Ihre zweite Annahme gilt dies nur dann, wenn das Ändern der Größe des Arrays zu wesentlich weniger Cache-Fehlern führt. Ob dies passieren wird, kann nur durch Profilerstellung des Arbeitscodes endgültig bestimmt werden, aber ich denke, es ist höchst unwahrscheinlich, dass es einen wesentlichen Unterschied macht. Da Sie in beiden Fällen zufällig auf das Array zugreifen, hat der Prozessor Schwierigkeiten zu wissen, welche Datenbits zwischengespeichert und in beiden Fällen aufbewahrt werden sollen.

Wenn die Daten und Zugriffe gleichmäßig zufällig verteilt sind, hängt die Leistung wahrscheinlich davon ab, welcher Teil der Zugriffe einen Cache-Fehler auf äußerer Ebene vermeidet. Um dies zu optimieren, muss bekannt sein, welche Arraygröße zuverlässig im Cache untergebracht werden kann. Wenn Ihr Cache groß genug ist, um ein Byte pro fünf Zellen aufzunehmen, besteht der einfachste Ansatz darin, dass ein Byte die fünf codierten Werte der Basis drei im Bereich von 0 bis 2 enthält (es gibt also 243 Kombinationen von 5 Werten) fit in a byte), zusammen mit einem 10.000.000-Byte-Array, das abgefragt wird, wenn der Basis-3-Wert "2" anzeigt.

Wenn der Cache nicht so groß ist, aber ein Byte pro 8 Zellen aufnehmen könnte, wäre es nicht möglich, einen Byte-Wert zu verwenden, um aus allen 6.561 möglichen Kombinationen von acht Basis-3-Werten auszuwählen, aber da der einzige Effekt von Das Ändern einer 0 oder 1 in eine 2 würde zu einer ansonsten unnötigen Suche führen. Für die Korrektheit müssten nicht alle 6.561 unterstützt werden. Stattdessen könnte man sich auf die 256 "nützlichsten" Werte konzentrieren.

Insbesondere wenn 0 häufiger als 1 ist oder umgekehrt, kann ein guter Ansatz darin bestehen, 217 Werte zum Codieren der Kombinationen von 0 und 1 zu verwenden, die 5 oder weniger Einsen enthalten, 16 Werte zum Codieren von xxxx0000 bis xxxx1111, 16 zum Codieren von 0000xxxx bis 1111xxxx und eine für xxxxxxxx. Vier Werte würden für jede andere Verwendung übrig bleiben. Wenn die Daten wie beschrieben zufällig verteilt werden, würde eine geringfügige Mehrheit aller Abfragen Bytes treffen, die nur Nullen und Einsen enthalten (in ungefähr 2/3 aller Achtergruppen wären alle Bits Nullen und Einsen und ungefähr 7/8 von diese hätten sechs oder weniger 1 Bits); Die überwiegende Mehrheit derjenigen, die nicht in einem Byte landen würden, das vier x enthält, und eine 50% ige Chance hätten, auf einer Null oder einer Eins zu landen. Daher würde nur etwa eine von vier Abfragen eine Suche nach großen Arrays erfordern.

Wenn die Daten zufällig verteilt sind, der Cache jedoch nicht groß genug ist, um ein Byte pro acht Elemente zu verarbeiten, könnte versucht werden, diesen Ansatz bei jedem Byte zu verwenden, das mehr als acht Elemente verarbeitet, es sei denn, es besteht eine starke Tendenz zu 0 oder 1 Der Anteil der Werte, die verarbeitet werden können, ohne dass im großen Array nachgeschlagen werden muss, verringert sich mit zunehmender Anzahl der von jedem Byte verarbeiteten Werte.

Ich werde die Antwort von @ o11c ergänzen , da sein Wortlaut etwas verwirrend sein könnte. Wenn ich das letzte Bit und den CPU-Zyklus drücken muss, würde ich Folgendes tun.

Wir beginnen mit der Erstellung eines ausgeglichenen binären Suchbaums, der die 5% -Fälle "etwas anderes" enthält. Bei jeder Suche gehen Sie schnell durch den Baum: Sie haben 10000000 Elemente: 5% davon befinden sich im Baum. Daher enthält die Baumdatenstruktur 500000 Elemente. Wenn Sie dies in O (log (n)) Zeit gehen, erhalten Sie 19 Iterationen. Ich bin kein Experte in diesem Bereich, aber ich denke, es gibt einige speichereffiziente Implementierungen. Lassen Sie uns schätzen:

• Ausgeglichener Baum, damit die Teilbaumposition berechnet werden kann (Indizes müssen nicht in den Knoten des Baums gespeichert werden). Ebenso wird ein Heap (Datenstruktur) im linearen Speicher gespeichert.
• 1-Byte-Wert (2 bis 255)
• 3 Bytes für den Index (10000000 benötigt 23 Bits, was 3 Bytes entspricht)

Insgesamt 4 Bytes: 500000 * 4 = 1953 kB. Passt in den Cache!

Für alle anderen Fälle (0 oder 1) können Sie einen Bitvektor verwenden. Beachten Sie, dass Sie die 5% anderen Fälle für den wahlfreien Zugriff nicht auslassen können: 1,19 MB.

Die Kombination dieser beiden verwendet ungefähr 3.099 MB. Mit dieser Technik sparen Sie einen Faktor 3,08 Speicher.

Dies übertrifft jedoch nicht die Antwort von @Matteo Italia (das 2,76 MB verwendet), schade. Können wir etwas extra tun? Der speicherintensivste Teil sind die 3 Byte Index im Baum. Wenn wir dies auf 2 reduzieren können, würden wir 488 kB einsparen und die gesamte Speichernutzung wäre: 2,622 MB, was kleiner ist!

Wie machen wir das? Wir müssen die Indizierung auf 2 Bytes reduzieren. Wiederum benötigt 10000000 23 Bit. Wir müssen in der Lage sein, 7 Bits zu löschen. Wir können dies einfach tun, indem wir den Bereich von 10000000 Elementen in 2 ^ 7 (= 128) Regionen von 78125 Elementen aufteilen. Jetzt können wir für jede dieser Regionen einen ausgeglichenen Baum mit durchschnittlich 3906 Elementen erstellen. Die Auswahl des richtigen Baums erfolgt durch einfache Division des Zielindex durch 2 ^ 7 (oder eine Bitverschiebung)>> 7 ). Jetzt kann der zum Speichern erforderliche Index durch die verbleibenden 16 Bits dargestellt werden. Beachten Sie, dass für die Länge des Baums, der gespeichert werden muss, ein gewisser Overhead anfällt, der jedoch vernachlässigbar ist. Beachten Sie auch, dass dieser Aufteilungsmechanismus die erforderliche Anzahl von Iterationen reduziert, um den Baum zu durchlaufen. Dies reduziert sich jetzt auf 7 Iterationen weniger, da 7 Bits gelöscht wurden: Es sind nur noch 12 Iterationen übrig.

Beachten Sie, dass Sie den Vorgang theoretisch wiederholen könnten, um die nächsten 8 Bits abzuschneiden. Dazu müssten Sie jedoch 2 ^ 15 ausgeglichene Bäume mit durchschnittlich ~ 305 Elementen erstellen. Dies würde zu 2,143 MB führen, mit nur 4 Iterationen, um den Baum zu durchlaufen. Dies ist eine erhebliche Beschleunigung im Vergleich zu den 19 Iterationen, mit denen wir begonnen haben.

Als abschließende Schlussfolgerung: Dies übertrifft die 2-Bit-Vektorstrategie um ein kleines Stück Speicherbedarf, ist jedoch ein schwerer Kampf bei der Implementierung. Aber wenn es den Unterschied machen kann, ob der Cache angepasst wird oder nicht, ist es möglicherweise den Versuch wert.

Wenn Sie nur Lesevorgänge ausführen, ist es besser, einem einzelnen Index keinen Wert zuzuweisen, sondern einem Intervall von Indizes.

Beispielsweise:

[0, 15000] = 0
[15001, 15002] = 153
[15003, 26876] = 2
[25677, 31578] = 0
...

Dies kann mit einer Struktur erfolgen. Möglicherweise möchten Sie auch eine ähnliche Klasse definieren, wenn Sie einen OO-Ansatz bevorzugen.

class Interval{
  private:
    uint32_t start; // First element of interval
    uint32_t end; // Last element of interval
    uint8_t value; // Assigned value

  public:
    Interval(uint32_t start, uint32_t end, uint8_t value);
    bool isInInterval(uint32_t item); // Checks if item lies within interval
    uint8_t getValue(); // Returns the assigned value
}

Jetzt müssen Sie nur noch eine Liste von Intervallen durchlaufen und prüfen, ob Ihr Index in einem dieser Intervalle liegt, was im Durchschnitt viel weniger speicherintensiv sein kann, aber mehr CPU-Ressourcen kostet.

Interval intervals[INTERVAL_COUNT];
intervals[0] = Interval(0, 15000, 0);
intervals[1] = Interval(15001, 15002, 153);
intervals[2] = Interval(15003, 26876, 2);
intervals[3] = Interval(25677, 31578, 0);
...

uint8_t checkIntervals(uint32_t item)

    for(int i=0; i<INTERVAL_COUNT-1; i++)
    {
        if(intervals[i].isInInterval(item) == true)
        {
            return intervals[i].getValue();
        }
    }
    return DEFAULT_VALUE;
}

Wenn Sie die Intervalle nach absteigender Größe sortieren, erhöhen Sie die Wahrscheinlichkeit, dass das gesuchte Element frühzeitig gefunden wird, was Ihren durchschnittlichen Speicher- und CPU-Ressourcenverbrauch weiter verringert.

Sie können auch alle Intervalle mit einer Größe von 1 entfernen. Fügen Sie die entsprechenden Werte in eine Karte ein und überprüfen Sie sie nur, wenn das gesuchte Element nicht in den Intervallen gefunden wurde. Dies sollte auch die durchschnittliche Leistung etwas erhöhen.

Vor langer, langer Zeit kann ich mich nur erinnern ...

In der Universität hatten wir die Aufgabe, ein Ray-Tracer-Programm zu beschleunigen, das von einem Algorithmus immer wieder aus Puffer-Arrays gelesen werden muss. Ein Freund sagte mir, ich solle immer RAM-Reads verwenden, die ein Vielfaches von 4 Byte sind. Also habe ich das Array von einem Muster von [x1, y1, z1, x2, y2, z2, ..., xn, yn, zn] in ein Muster von [x1, y1, z1,0, x2, y2, z2 geändert , 0, ..., xn, yn, zn, 0]. Das heißt, ich füge nach jeder 3D-Koordinate ein leeres Feld hinzu. Nach einigen Leistungstests: Es war schneller. So lange Rede und Antwort: Lesen Sie mehrere von 4 Bytes aus Ihrem Array aus dem RAM und möglicherweise auch von der richtigen Startposition aus. Lesen Sie also einen kleinen Cluster, in dem sich der gesuchte Index befindet, und lesen Sie den gesuchten Index aus diesem kleinen Cluster in CPU. (In Ihrem Fall müssen Sie keine Füllfelder einfügen, aber das Konzept sollte klar sein.)

Vielleicht könnten auch andere Multiples der Schlüssel in neueren Systemen sein.

Ich weiß nicht, ob dies in Ihrem Fall funktioniert. Wenn es also nicht funktioniert: Entschuldigung. Wenn es funktioniert, würde ich mich über einige Testergebnisse freuen.

PS: Oh, und wenn es ein Zugriffsmuster oder in der Nähe befindliche Indizes gibt, können Sie den zwischengespeicherten Cluster wiederverwenden.

PPS: Es könnte sein, dass der Mehrfachfaktor eher 16 Byte oder so ähnlich war, es ist zu lange her, dass ich mich genau erinnern kann.

Wenn Sie dies betrachten, können Sie Ihre Daten aufteilen, zum Beispiel:

• ein Bitset, das indiziert wird und den Wert 0 darstellt (std :: vector wäre hier nützlich)
• Ein Bitset, das indiziert wird und den Wert 1 darstellt
• ein std :: vector für die Werte von 2, der die Indizes enthält, die sich auf diesen Wert beziehen
• eine Karte für die anderen Werte (oder std :: vector>)

In diesem Fall werden alle Werte bis zu einem bestimmten Index angezeigt, sodass Sie sogar eines der Bitsets entfernen können und den Wert so darstellen, wie er in den anderen fehlt.

Dies spart Ihnen etwas Speicherplatz für diesen Fall, würde jedoch den schlimmsten Fall verschlimmern. Sie benötigen auch mehr CPU-Leistung, um die Suche durchzuführen.

Achten Sie darauf zu messen!

Wie Mats in seiner Kommentar-Antwort erwähnt, ist es schwer zu sagen, was eigentlich die beste Lösung ist, ohne genau zu wissen, welche Art von Daten Sie haben (z. B. gibt es lange Läufe von Nullen usw.) und wie Ihr Zugriffsmuster aussieht wie (bedeutet "zufällig" "überall" oder nur "nicht streng linear" oder "jeder Wert genau einmal, nur zufällig" oder ...).

Es fallen jedoch zwei Mechanismen ein:

• Bit-Arrays; Wenn Sie nur zwei Werte hätten, könnten Sie Ihr Array trivial um den Faktor 8 komprimieren. Wenn Sie 4 Werte haben (oder "3 Werte + alles andere"), können Sie um den Faktor zwei komprimieren. Das ist möglicherweise nicht die Mühe wert und würde Benchmarks erfordern, insbesondere wenn Sie wirklich zufällige Zugriffsmuster haben, die Ihren Caches entkommen und daher die Zugriffszeit überhaupt nicht ändern.
• (index,value)oder (value,index)Tabellen. Das heißt, Sie haben eine sehr kleine Tabelle für den Fall 1%, vielleicht eine Tabelle für den Fall 5% (in der nur die Indizes gespeichert werden müssen, da alle den gleichen Wert haben) und ein großes komprimiertes Bit-Array für die letzten beiden Fälle. Und mit "Tabelle" meine ich etwas, das eine relativ schnelle Suche ermöglicht; dh vielleicht ein Hash, ein Binärbaum und so weiter, abhängig davon, was Sie zur Verfügung haben und Ihre tatsächlichen Bedürfnisse. Wenn diese Untertabellen in Ihre Caches der 1./2. Ebene passen, haben Sie möglicherweise Glück.

Ich bin mit C nicht sehr vertraut, aber in C ++ können Sie vorzeichenlose Zeichen verwenden , um eine Ganzzahl im Bereich von 0 bis 255 darzustellen.

Im Vergleich zu normalen int (wieder, ich komme aus Java und C ++ Welt) , in der 4 - Byte (32 Bit) erforderlich ist, ein unsigned char erfordert 1 Byte (8 Bit). Daher kann die Gesamtgröße des Arrays um 75% reduziert werden.

Sie haben alle Verteilungseigenschaften Ihres Arrays kurz beschrieben. werfen das Array .

Sie können das Array leicht durch eine zufällige Methode ersetzen, die dieselbe Wahrscheinlichkeitsausgabe wie das Array erzeugt.

Wenn Konsistenz wichtig ist (denselben Wert für denselben Zufallsindex erzeugen), sollten Sie einen Bloom-Filter und / oder eine Hash-Map verwenden , um Wiederholungstreffer zu verfolgen. Wenn Ihre Array-Zugriffe jedoch wirklich zufällig sind, ist dies völlig unnötig.