¿Alguna optimización para el acceso aleatorio en una matriz muy grande cuando el valor en el 95% de los casos es 0 o 1?

¿Hay alguna optimización posible para el acceso aleatorio en una matriz muy grande (actualmente uso uint8_t, y estoy preguntando qué es mejor)

uint8_t MyArray[10000000];

cuando el valor en cualquier posición de la matriz es

• 0 o 1 para el 95% de todos los casos,
• 2 en 4% de los casos,
• entre 3 y 255 en el otro 1% de los casos?

Entonces, ¿hay algo mejor que una uint8_tmatriz para usar para esto? Debería ser lo más rápido posible recorrer toda la matriz en un orden aleatorio, y esto es muy pesado en el ancho de banda de RAM, por lo que cuando hay más de unos pocos hilos haciendo eso al mismo tiempo para diferentes matrices, actualmente todo el ancho de banda de RAM se satura rápidamente

Pregunto, ya que se siente muy ineficiente tener una matriz tan grande (10 MB) cuando se sabe que casi todos los valores, excepto el 5%, serán 0 o 1. Entonces, cuando el 95% de todos los valores en la matriz solo necesitaría 1 bit en lugar de 8 bit, esto reduciría el uso de memoria en casi un orden de magnitud. Parece que tiene que haber una solución más eficiente en la memoria que reduzca en gran medida el ancho de banda de RAM requerido para esto, y como resultado también sea significativamente más rápido para el acceso aleatorio.

Una posibilidad simple que viene a la mente es mantener una matriz comprimida de 2 bits por valor para los casos comunes, y un byte separado de 4 bytes por valor (24 bits para el índice del elemento original, 8 bits para el valor real, entonces (idx << 8) | value)) matriz ordenada para el otros.

Cuando busca un valor, primero realiza una búsqueda en la matriz de 2bpp (O (1)); si encuentra 0, 1 o 2, es el valor que desea; si encuentra 3 significa que debe buscarlo en la matriz secundaria. Aquí realizará una búsqueda binaria para buscar el índice de su interés desplazado a la izquierda por 8 (O (log (n) con una pequeña n, ya que este debería ser el 1%), y extraer el valor del 4- byte cosita

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);
    }
}

Para una matriz como la que propuso, esto debería tomar 10000000/4 = 2500000 bytes para la primera matriz, más 10000000 * 1% * 4 B = 400000 bytes para la segunda matriz; por lo tanto, 2900000 bytes, es decir, menos de un tercio de la matriz original, y la porción más utilizada se mantiene unida en la memoria, lo que debería ser bueno para el almacenamiento en caché (incluso puede caber en L3).

Si necesita un direccionamiento de más de 24 bits, deberá modificar el "almacenamiento secundario"; Una forma trivial de extenderlo es tener una matriz de puntero de 256 elementos para cambiar los 8 bits superiores del índice y reenviar a una matriz ordenada indexada de 24 bits como se indicó anteriormente.

Punto de referencia rápido

#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;
}

(código y datos siempre actualizados en mi Bitbucket)

El código anterior llena una matriz de elementos de 10M con datos aleatorios distribuidos como OP especificado en su publicación, inicializa mi estructura de datos y luego:

• realiza una búsqueda aleatoria de elementos de 10M con mi estructura de datos
• hace lo mismo a través de la matriz original.

(tenga en cuenta que en caso de búsqueda secuencial, la matriz siempre gana en gran medida, ya que es la búsqueda más amigable para la caché que puede hacer)

Estos dos últimos bloques se repiten 50 veces y se cronometran; al final, la desviación media y estándar para cada tipo de búsqueda se calcula e imprime, junto con la aceleración (lookup_mean / array_mean).

Compilé el código anterior con g ++ 5.4.0 ( -O3 -static, más algunas advertencias) en Ubuntu 16.04, y lo ejecuté en algunas máquinas; la mayoría de ellos ejecutan Ubuntu 16.04, algunos algunos Linux más antiguos, otros algunos Linux más nuevos. No creo que el sistema operativo deba ser relevante en este caso.

            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

¡Los resultados son ... mixtos!

1. En general, en la mayoría de estas máquinas hay algún tipo de aceleración, o al menos están a la par.
2. Los dos casos en los que la matriz realmente supera la búsqueda de "estructura inteligente" son en máquinas con mucho caché y no particularmente ocupadas: el Xeon E5-1650 anterior (15 MB de caché) es una máquina de construcción nocturna, en este momento bastante inactiva; Xeon E5-2697 (35 MB de caché) es una máquina para cálculos de alto rendimiento, también en un momento de inactividad. Tiene sentido, la matriz original encaja completamente en su enorme caché, por lo que la estructura de datos compacta solo agrega complejidad.
3. En el lado opuesto del "espectro de rendimiento", pero donde nuevamente la matriz es un poco más rápida, está el humilde Celeron que alimenta mi NAS; tiene tan poco caché que ni la matriz ni la "estructura inteligente" encajan en absoluto. Otras máquinas con caché lo suficientemente pequeña funcionan de manera similar.
4. El Xeon X5650 debe tomarse con precaución: son máquinas virtuales en un servidor de máquina virtual de doble socket bastante ocupado; bien puede ser que, aunque nominalmente tiene una cantidad decente de caché, durante el tiempo de la prueba es reemplazado por máquinas virtuales completamente independientes varias veces.

Otra opción podría ser

• comprobar si el resultado es 0, 1 o 2
• si no hacer una búsqueda regular

En otras palabras, algo como:

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

donde bmaputiliza 2 bits por elemento con el valor 3 que significa "otro".

Esta estructura es trivial de actualizar, usa un 25% más de memoria, pero la mayor parte se busca solo en el 5% de los casos. Por supuesto, como de costumbre, si es una buena idea o no depende de muchas otras condiciones, la única respuesta es experimentar con el uso real.

Esto es más un "comentario largo" que una respuesta concreta

A menos que sus datos sean algo bien conocido, dudo que alguien pueda responder DIRECTAMENTE a su pregunta (y no conozco nada que coincida con su descripción, pero no sé TODO sobre todo tipo de patrones de datos para todos tipos de casos de uso). La escasez de datos es un problema común en la informática de alto rendimiento, pero generalmente es "tenemos una matriz muy grande, pero solo algunos valores no son cero".

Para patrones poco conocidos como lo que creo que es el suyo, nadie SABERÁ directamente cuál es mejor, y depende de los detalles: qué tan aleatorio es el acceso aleatorio: si el sistema accede a grupos de elementos de datos, o es completamente aleatorio como de Un generador de números aleatorios uniforme. ¿Los datos de la tabla son completamente al azar, o hay secuencias de 0 y luego secuencias de 1, con una dispersión de otros valores? La codificación de longitud de ejecución funcionaría bien si tiene secuencias razonablemente largas de 0 y 1, pero no funcionará si tiene un "tablero de ajedrez de 0/1". Además, tendría que mantener una tabla de "puntos de partida" para poder llegar al lugar relevante de manera razonablemente rápida.

Sé desde hace mucho tiempo que algunas bases de datos grandes son solo una gran tabla en RAM (datos de suscriptores de intercambio telefónico en este ejemplo), y uno de los problemas es que las cachés y las optimizaciones de tablas de páginas en el procesador son bastante inútiles. La persona que llama rara vez es la misma que alguien llamó recientemente a alguien, que no hay datos precargados de ningún tipo, es puramente aleatorio. Las tablas de páginas grandes son la mejor optimización para ese tipo de acceso.

En muchos casos, comprometer entre "velocidad y tamaño pequeño" es una de esas cosas que debes elegir en ingeniería de software [en otra ingeniería no es necesariamente un gran compromiso]. Entonces, "desperdiciar memoria para un código más simple" es con frecuencia la opción preferida. En este sentido, es probable que la solución "simple" sea mejor para la velocidad, pero si tiene un "mejor" uso para la RAM, la optimización para el tamaño de la tabla le proporcionaría un rendimiento suficiente y una buena mejora en el tamaño. Hay muchas maneras diferentes de lograrlo: como se sugiere en un comentario, un campo de 2 bits donde se almacenan los dos o tres valores más comunes y luego un formato de datos alternativo para los otros valores: una tabla hash sería mi primer enfoque, pero una lista o árbol binario también puede funcionar; nuevamente, depende de los patrones de dónde están sus "no 0, 1 o 2". Una vez más, depende de cómo se "dispersen" los valores en la tabla: ¿están en grupos o son más un patrón distribuido uniformemente?

Pero un problema con eso es que todavía está leyendo los datos de la RAM. Luego está gastando más código procesando los datos, incluido algún código para hacer frente al "este no es un valor común".

El problema con los algoritmos de compresión más comunes es que se basan en secuencias de desempaquetado, por lo que no puede acceder al azar. Y la sobrecarga de dividir sus grandes datos en trozos de, digamos, 256 entradas a la vez, y descomprimir los 256 en una matriz uint8_t, obtener los datos que desea y luego desechar sus datos sin comprimir, es muy poco probable que le brinde buenos resultados. rendimiento, suponiendo que sea de cierta importancia, por supuesto.

Al final, probablemente tendrá que implementar una o algunas de las ideas en los comentarios / respuestas para probar, ver si ayuda a resolver su problema o si el bus de memoria sigue siendo el principal factor limitante.

Lo que he hecho en el pasado es usar un hashmap delante de un bitset.

Esto reduce a la mitad el espacio en comparación con la respuesta de Matteo, pero puede ser más lento si las búsquedas de "excepciones" son lentas (es decir, hay muchas excepciones).

A menudo, sin embargo, "el caché es el rey".

A menos que haya un patrón en sus datos, es poco probable que haya una velocidad razonable o una optimización del tamaño, y, suponiendo que esté apuntando a una computadora normal, 10 MB no es un gran problema de todos modos.

Hay dos supuestos en sus preguntas:

1. Los datos se almacenan mal porque no está utilizando todos los bits
2. Almacenarlo mejor haría las cosas más rápido.

Creo que ambos supuestos son falsos. En la mayoría de los casos, la forma adecuada de almacenar datos es almacenar la representación más natural. En su caso, este es el que ha elegido: un byte para un número entre 0 y 255. Cualquier otra representación será más compleja y, por lo tanto, todas las demás serán iguales, más lenta y más propensa a errores. Para desviarse de este principio general, necesita una razón más sólida que potencialmente seis bits "desperdiciados" en el 95% de sus datos.

Para su segunda suposición, será cierto si, y solo si, cambiar el tamaño de la matriz da como resultado sustancialmente menos errores de caché. Si esto sucederá solo se puede determinar definitivamente mediante el perfil del código de trabajo, pero creo que es muy poco probable que haga una diferencia sustancial. Debido a que accederá aleatoriamente a la matriz en cualquier caso, el procesador tendrá dificultades para saber qué bits de datos almacenar en caché y mantener en cualquier caso.

Si los datos y los accesos se distribuyen de manera uniforme al azar, el rendimiento probablemente dependerá de qué fracción de los accesos evite una pérdida de caché de nivel externo. La optimización requerirá saber qué tamaño de matriz se puede acomodar de manera confiable en la memoria caché. Si su caché es lo suficientemente grande como para acomodar un byte por cada cinco celdas, el enfoque más simple puede ser que un byte mantenga los cinco valores codificados en base tres en el rango 0-2 (hay 243 combinaciones de 5 valores, por lo que encaja en un byte), junto con una matriz de 10,000,000 de bytes que se consultará siempre que el valor de base 3 indique "2".

Si el caché no es tan grande, pero podría acomodar un byte por 8 celdas, entonces no sería posible usar un valor de byte para seleccionar entre las 6.561 combinaciones posibles de ocho valores de base 3, pero dado que el único efecto de cambiar un 0 o 1 a un 2 sería causar una búsqueda innecesaria, la corrección no requeriría el soporte de todas las 6.561. En cambio, uno podría centrarse en los 256 valores más "útiles".

Especialmente si 0 es más común que 1, o viceversa, un buen enfoque podría ser usar 217 valores para codificar las combinaciones de 0 y 1 que contienen 5 o menos 1's, 16 valores para codificar xxxx0000 a xxxx1111, 16 para codificar 0000xxxx a 1111xxxx, y uno para xxxxxxxx. Quedarían cuatro valores para cualquier otro uso que uno pueda encontrar. Si los datos se distribuyen aleatoriamente como se describe, una ligera mayoría de todas las consultas alcanzaría bytes que contenían solo ceros y unos (en aproximadamente 2/3 de todos los grupos de ocho, todos los bits serían ceros y unos, y aproximadamente 7/8 de esos tendrían seis o menos 1 bits); la gran mayoría de los que no lo hicieron aterrizarían en un byte que contenía cuatro x, y tendrían un 50% de posibilidades de aterrizar en un cero o uno. Por lo tanto, solo alrededor de una de cada cuatro consultas necesitaría una búsqueda de matriz grande.

Si los datos se distribuyen aleatoriamente pero el caché no es lo suficientemente grande como para manejar un byte por cada ocho elementos, se podría tratar de usar este enfoque con cada byte manejando más de ocho elementos, pero a menos que haya un sesgo fuerte hacia 0 o hacia 1 , la fracción de valores que se pueden manejar sin tener que buscar en la matriz grande se reducirá a medida que aumente el número manejado por cada byte.

Agregaré a la respuesta de @ o11c , ya que su redacción puede ser un poco confusa. Si necesito exprimir el último bit y el ciclo de la CPU, haría lo siguiente.

Comenzaremos construyendo un árbol de búsqueda binario balanceado que contiene el 5% de los casos de "algo más". Para cada búsqueda, recorre el árbol rápidamente: tiene 10000000 elementos: el 5% de los cuales está en el árbol: por lo tanto, la estructura de datos del árbol contiene 500000 elementos. Caminar esto en tiempo O (log (n)), te da 19 iteraciones. No soy un experto en esto, pero supongo que hay algunas implementaciones de uso eficiente de la memoria. Vamos a adivinar:

• Árbol equilibrado, por lo que se puede calcular la posición del subárbol (no es necesario almacenar los índices en los nodos del árbol). De la misma manera, un montón (estructura de datos) se almacena en la memoria lineal.
• Valor de 1 byte (2 a 255)
• 3 bytes para el índice (10000000 toma 23 bits, que se ajusta a 3 bytes)

Totalización, 4 bytes: 500000 * 4 = 1953 kB. Se adapta al caché!

Para todos los demás casos (0 o 1), puede usar un vector de bits. Tenga en cuenta que no puede omitir el 5% de los demás casos de acceso aleatorio: 1.19 MB.

La combinación de estos dos usa aproximadamente 3,099 MB. Con esta técnica, ahorrará un factor 3.08 de memoria.

Sin embargo, esto no supera la respuesta de @Matteo Italia (que usa 2.76 MB), una pena. ¿Hay algo que podamos hacer extra? La parte que consume más memoria son los 3 bytes de índice en el árbol. Si podemos reducir esto a 2, ahorraríamos 488 kB y el uso total de memoria sería: 2.622 MB, ¡que es más pequeño!

Cómo hacemos esto? Tenemos que reducir la indexación a 2 bytes. De nuevo, 10000000 toma 23 bits. Necesitamos poder soltar 7 bits. Simplemente podemos hacer esto dividiendo el rango de 10000000 elementos en 2 ^ 7 (= 128) regiones de 78125 elementos. Ahora podemos construir un árbol equilibrado para cada una de estas regiones, con 3906 elementos en promedio. La elección del árbol correcto se realiza mediante una simple división del índice objetivo por 2 ^ 7 (o un desplazamiento de bits >> 7). Ahora el índice requerido para almacenar puede ser representado por los 16 bits restantes. Tenga en cuenta que hay algo de sobrecarga para la longitud del árbol que debe almacenarse, pero esto es insignificante. También tenga en cuenta que este mecanismo de división reduce el número requerido de iteraciones para recorrer el árbol, esto ahora se reduce a 7 iteraciones menos, ya que soltamos 7 bits: solo quedan 12 iteraciones.

Tenga en cuenta que en teoría podría repetir el proceso para cortar los siguientes 8 bits, pero esto requeriría que cree 2 ^ 15 árboles equilibrados, con ~ 305 elementos en promedio. Esto daría como resultado 2.143 MB, con solo 4 iteraciones para recorrer el árbol, lo que es una aceleración considerable, en comparación con las 19 iteraciones con las que comenzamos.

Como conclusión final: esto supera la estrategia de vector de 2 bits por un pequeño uso de memoria, pero es una lucha completa para implementar. Pero si puede marcar la diferencia entre ajustar el caché o no, puede valer la pena intentarlo.

Si solo realiza operaciones de lectura, sería mejor no asignar un valor a un solo índice sino a un intervalo de índices.

Por ejemplo:

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

Esto se puede hacer con una estructura. También es posible que desee definir una clase similar a esta si desea un enfoque OO.

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
}

Ahora solo tiene que iterar a través de una lista de intervalos y verificar si su índice se encuentra dentro de uno de ellos, lo que puede requerir mucho menos memoria en promedio, pero cuesta más recursos de CPU.

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;
}

Si ordena los intervalos por tamaño descendente, aumenta la probabilidad de que el artículo que está buscando se encuentre temprano, lo que disminuye aún más su uso promedio de memoria y recursos de CPU.

También puede eliminar todos los intervalos con un tamaño de 1. Coloque los valores correspondientes en un mapa y verifíquelos solo si el elemento que está buscando no se encontró en los intervalos. Esto también debería aumentar un poco el rendimiento promedio.

Hace mucho, mucho tiempo, solo puedo recordar ...

En la universidad tenemos la tarea de acelerar un programa de trazado de rayos, que tiene que leerse por algoritmo una y otra vez desde las matrices de almacenamiento intermedio. Un amigo me dijo que siempre usara lecturas de RAM que son múltiplos de 4 Bytes. Así que cambié la matriz de un patrón de [x1, y1, z1, x2, y2, z2, ..., xn, yn, zn] a un patrón de [x1, y1, z1,0, x2, y2, z2 , 0, ..., xn, yn, zn, 0]. Significa que agrego un campo vacío después de cada coordenada 3D. Después de algunas pruebas de rendimiento: fue más rápido. En resumen: lea múltiples de 4 Bytes de su matriz de RAM, y tal vez también desde la posición inicial correcta, por lo que lee un pequeño clúster donde está el índice buscado y lee el índice buscado de este pequeño clúster en la CPU. (En su caso, no necesitará insertar campos de relleno, pero el concepto debe ser claro)

Quizás también otros múltiplos podrían ser la clave en los sistemas más nuevos.

No sé si esto funcionará en su caso, así que si no funciona: lo siento. Si funciona, me alegraría saber sobre algunos resultados de las pruebas.

PD: Ah, y si hay algún patrón de acceso o índices de acceso cercanos, puede reutilizar el clúster almacenado en caché.

PPS: Podría ser que el factor múltiple se parecía más a 16 Bytes o algo así, hace mucho tiempo, que puedo recordar exactamente.

Mirando esto, podría dividir sus datos, por ejemplo:

• un conjunto de bits que se indexa y representa el valor 0 (std :: vector sería útil aquí)
• un conjunto de bits que se indexa y representa el valor 1
• un std :: vector para los valores de 2, que contiene los índices que se refieren a este valor
• un mapa para los otros valores (o std :: vector>)

En este caso, todos los valores aparecen hasta un índice dado, por lo que incluso podría eliminar uno de los conjuntos de bits y representa el valor como falta en los otros.

Esto le ahorrará algo de memoria para este caso, aunque empeoraría el peor de los casos. También necesitará más potencia de CPU para realizar las búsquedas.

¡Asegúrate de medir!

Al igual que Mats menciona en su comentario-respuesta, es difícil decir cuál es la mejor solución sin saber específicamente qué tipo de datos tiene (por ejemplo, si hay largos períodos de 0, etc.) y qué aspecto tiene su patrón de acceso. me gusta ("aleatorio" significa "en todo el lugar" o simplemente "no estrictamente en forma completamente lineal" o "cada valor exactamente una vez, simplemente aleatorio" o ...).

Dicho esto, hay dos mecanismos que vienen a la mente:

• Matrices de bits; es decir, si solo tuviera dos valores, podría comprimir trivialmente su matriz por un factor de 8; Si tiene 4 valores (o "3 valores + todo lo demás") puede comprimir por un factor de dos. Lo cual podría no valer la pena y necesitaría puntos de referencia, especialmente si tiene patrones de acceso realmente aleatorios que escapan de sus cachés y, por lo tanto, no cambian el tiempo de acceso.
• (index,value)o (value,index)mesas. Es decir, tener una tabla muy pequeña para el caso del 1%, tal vez una tabla para el caso del 5% (que solo necesita almacenar los índices, ya que todos tienen el mismo valor), y una gran matriz de bits comprimidos para los dos casos finales. Y con "tabla" quiero decir algo que permite una búsqueda relativamente rápida; es decir, quizás un hash, un árbol binario, etc., según lo que tenga disponible y sus necesidades reales. Si estas subtablas se ajustan a sus cachés de primer / segundo nivel, es posible que tenga suerte.

No estoy muy familiarizado con C, pero en C ++ puede usar caracteres sin signo para representar un número entero en el rango de 0 a 255.

En comparación con int normal (de nuevo, vengo del mundo Java y C ++ ) en el que se requieren 4 bytes (32 bits), un carácter sin signo requiere 1 byte (8 bits). por lo que podría reducir el tamaño total de la matriz en un 75%.

Usted ha descrito sucintamente todas las características de distribución de su matriz; tirar la matriz .

Puede reemplazar fácilmente la matriz con un método aleatorio que produce la misma salida probabilística que la matriz.

Si la consistencia es importante (produce el mismo valor para el mismo índice aleatorio), considere usar un filtro de floración y / o un mapa hash para rastrear los golpes repetidos. Sin embargo, si los accesos de tu matriz son realmente aleatorios, esto es totalmente innecesario.