Любая оптимизация для произвольного доступа к очень большому массиву, когда значение в 95% случаев равно 0 или 1?

Есть ли возможная оптимизация для произвольного доступа к очень большому массиву (сейчас я использую uint8_tи спрашиваю, что лучше)

uint8_t MyArray[10000000];

когда значение в любой позиции в массиве равно

• 0 или 1 для 95% всех случаев,
• 2 в 4% случаев,
• от 3 до 255 в остальном 1% случаев?

Итак, есть ли что-нибудь лучше, чем uint8_t массив для этого? Необходимо как можно быстрее перебрать весь массив в случайном порядке, и это очень сильно сказывается на пропускной способности ОЗУ, поэтому, когда более нескольких потоков делают это одновременно для разных массивов, в настоящее время вся пропускная способность ОЗУ быстро насыщается.

Я спрашиваю, так как кажется очень неэффективным иметь такой большой массив (10 МБ), когда на самом деле известно, что почти все значения, кроме 5%, будут либо 0, либо 1. Итак, когда 95% всех значений в массиве на самом деле потребуется только 1 бит вместо 8, это уменьшит использование памяти почти на порядок. Похоже, что должно быть решение с более эффективным использованием памяти, которое значительно снизило бы требуемую для этого полосу пропускания RAM и, как результат, также было бы значительно быстрее для произвольного доступа.

На ум приходит простая возможность - сохранить сжатый массив из 2 битов на значение для общих случаев и разделенных 4 байта на значение (24 бит для исходного индекса элемента, 8 бит для фактического значения (idx << 8) | value)) отсортированный массив для другие.

Когда вы ищете значение, вы сначала выполняете поиск в массиве 2bpp (O (1)); если вы найдете 0, 1 или 2, это желаемое значение; если вы найдете 3, это означает, что вам нужно найти его во вторичном массиве. Здесь вы выполните двоичный поиск, чтобы найти интересующий вас индекс со смещением влево на 8 (O (log (n) с небольшим n, так как это должно быть 1%), и извлеките значение из 4- байтовая штука.

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

Для такого массива, как тот, который вы предложили, это должно занять 10000000/4 = 2500000 байтов для первого массива плюс 10000000 * 1% * 4 B = 400000 байтов для второго массива; следовательно, 2900000 байт, т.е. менее одной трети исходного массива, а наиболее часто используемая часть хранится вместе в памяти, что должно быть подходящим для кэширования (может даже соответствовать L3).

Если вам нужна более чем 24-битная адресация, вам придется настроить «вторичное хранилище»; тривиальный способ расширить его - иметь массив указателей из 256 элементов, чтобы переключить верхние 8 бит индекса и переадресовать его на 24-битный индексированный отсортированный массив, как указано выше.

Быстрый тест

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

(код и данные всегда обновляются в моем Bitbucket)

Приведенный выше код заполняет массив элементов из 10 миллионов случайных данных, распределенных как OP, указанный в их сообщении, инициализирует мою структуру данных, а затем:

• выполняет случайный поиск 10M элементов в моей структуре данных
• делает то же самое через исходный массив.

(обратите внимание, что в случае последовательного поиска массив всегда в значительной степени выигрывает, поскольку это наиболее удобный для кеша поиск, который вы можете сделать)

Эти последние два блока повторяются 50 раз и рассчитываются по времени; в конце вычисляются и печатаются среднее значение и стандартное отклонение для каждого типа поиска, а также ускорение (lookup_mean / array_mean).

Я скомпилировал приведенный выше код с g ++ 5.4.0 ( -O3 -staticплюс несколько предупреждений) в Ubuntu 16.04 и запустил его на некоторых машинах; большинство из них работают под управлением Ubuntu 16.04, некоторые из них работают под более старой версией Linux, некоторые под управлением более новой версии. Я не думаю, что ОС в данном случае должна быть актуальной.

            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

Результаты ... смешанные!

1. В общем, на большинстве этих машин есть какое-то ускорение или, по крайней мере, они находятся на одном уровне.
2. Два случая, когда массив действительно превосходит поиск по «умной структуре», - это машины с большим количеством кеша и не особо загруженные: Xeon E5-1650, описанный выше (15 МБ кеш-памяти), - это машина для ночной сборки, которая в настоящий момент довольно простаивает; Xeon E5-2697 (кэш 35 МБ) - это машина для высокопроизводительных вычислений, в том числе и в момент простоя. В этом есть смысл, исходный массив полностью умещается в их огромном кэше, поэтому компактная структура данных только добавляет сложности.
3. На противоположной стороне «спектра производительности» - но там, где снова массив немного быстрее, есть скромный Celeron, который питает мой NAS; у него так мало кеша, что ни массив, ни «умная структура» в него вообще не помещаются. Другие машины с достаточно маленьким кешем работают аналогично.
4. К Xeon X5650 нужно относиться с некоторой осторожностью - это виртуальные машины на довольно загруженном двухпроцессорном сервере виртуальных машин; вполне может быть, что, хотя номинально он имеет приличный объем кеша, во время теста он несколько раз вытесняется совершенно несвязанными виртуальными машинами.

Другой вариант мог быть

• проверьте результат 0, 1 или 2
• если нет, сделайте обычный поиск

Другими словами что-то вроде:

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

где bmapиспользуется 2 бита на элемент со значением 3, означающим «другое».

Эту структуру легко обновить, она использует на 25% больше памяти, но большая часть просматривается только в 5% случаев. Конечно, как обычно, хорошая идея или нет, зависит от множества других условий, поэтому единственный ответ - экспериментировать с реальным использованием.

Это скорее «длинный комментарий», чем конкретный ответ.

Если ваши данные не являются чем-то хорошо известным, я сомневаюсь, что кто-то может ПРЯМО ответить на ваш вопрос (и я не знаю ничего, что соответствует вашему описанию, но тогда я не знаю ВСЕ о всех видах шаблонов данных для всех виды вариантов использования). Редкие данные - обычная проблема в высокопроизводительных вычислениях, но обычно «у нас очень большой массив, но только некоторые значения не равны нулю».

Для малоизвестных шаблонов, таких как, как я думаю, ваш, никто не ЗНАЕТ напрямую, что лучше, и это зависит от деталей: насколько случайным является произвольный доступ - система обращается к кластерам элементов данных, или это полностью случайное, как из единый генератор случайных чисел. Являются ли данные таблицы полностью случайными, или есть последовательности из 0, а затем из 1 с разбросом других значений? Кодирование длины прогона будет работать хорошо, если у вас есть достаточно длинные последовательности из 0 и 1, но не будет работать, если у вас есть «шахматная доска 0/1». Кроме того, вам нужно будет вести таблицу «отправных точек», чтобы вы могли достаточно быстро добраться до нужного места.

Я давно знаю, что некоторые большие базы данных представляют собой просто большую таблицу в ОЗУ (данные абонентов телефонной станции в этом примере), и одна из проблем заключается в том, что кеширование и оптимизация таблиц страниц в процессоре довольно бесполезны. Вызывающий так редко бывает таким же, как тот, кто недавно кому-то звонил, что нет никаких предварительно загруженных данных, они просто случайны. Большие таблицы страниц - лучшая оптимизация для такого типа доступа.

Во многих случаях компромисс между «скоростью и малым размером» - это одна из тех вещей, которые вы должны выбрать в разработке программного обеспечения [в другой разработке это не обязательно такой уж большой компромисс]. Так что «трата памяти на более простой код» довольно часто является предпочтительным выбором. В этом смысле «простое» решение, скорее всего, лучше по скорости, но если у вас «лучшее» использование ОЗУ, то оптимизация по размеру таблицы даст вам достаточную производительность и хорошее улучшение по размеру. Есть много разных способов добиться этого - как предлагается в комментарии, двухбитное поле, в котором хранятся два или три наиболее распространенных значения, а затем некоторый альтернативный формат данных для других значений - хеш-таблица была бы моей первый подход, но список или двоичное дерево тоже могут работать - опять же, это зависит от того, где находятся ваши «не 0, 1 или 2». Опять же, это зависит от того, как значения «разбросаны» в таблице - в кластерах или в более равномерно распределенном шаблоне?

Но проблема в том, что вы все еще читаете данные из ОЗУ. Затем вы тратите больше кода на обработку данных, включая некоторый код, чтобы справиться с «это не общее значение».

Проблема с наиболее распространенными алгоритмами сжатия заключается в том, что они основаны на последовательностях распаковки, поэтому вы не можете получить к ним произвольный доступ. И накладные расходы, связанные с разделением ваших больших данных на куски, скажем, по 256 записей за раз, и распаковкой 256 в массив uint8_t, извлечением нужных данных и последующим выбросом несжатых данных, вряд ли принесут вам пользу. производительность - если, конечно, это важно.

В конце концов, вам, вероятно, придется реализовать одну или несколько идей в комментариях / ответах, чтобы проверить, поможет ли это решить вашу проблему или шина памяти по-прежнему является основным ограничивающим фактором.

В прошлом я использовал хэш-карту перед битовым набором .

Это уменьшает пространство вдвое по сравнению с ответом Маттео, но может быть медленнее, если поиск «исключения» выполняется медленно (т.е. есть много исключений).

Однако часто «кеш - это король».

Если в ваших данных нет шаблона, маловероятно, что есть какая-либо разумная оптимизация скорости или размера, и - если вы нацеливаетесь на обычный компьютер - 10 МБ в любом случае не так уж и много.

В ваших вопросах есть два предположения:

1. Данные плохо хранятся, потому что вы не используете все биты
2. Лучшее хранение ускорит работу.

Я считаю, что оба эти предположения неверны. В большинстве случаев наиболее подходящим способом хранения данных является наиболее естественное представление. В вашем случае это то, что вы выбрали: байт для числа от 0 до 255. Любое другое представление будет более сложным и, следовательно, при прочих равных условиях более медленным и более подверженным ошибкам. Чтобы отклониться от этого общего принципа, вам нужна более веская причина, чем потенциально шесть «потраченных впустую» битов на 95% ваших данных.

Для вашего второго предположения оно будет истинным тогда и только тогда, когда изменение размера массива приведет к существенно меньшему количеству промахов в кэше. Произойдет ли это, можно окончательно определить только путем профилирования рабочего кода, но я думаю, что это вряд ли существенно изменит ситуацию. Поскольку в любом случае вы будете обращаться к массиву случайным образом, процессору будет сложно определить, какие биты данных следует кэшировать и хранить в любом случае.

Если данные и доступы равномерно распределены случайным образом, производительность, вероятно, будет зависеть от того, какая доля обращений позволяет избежать промаха кэша внешнего уровня. Оптимизация этого потребует знания массива какого размера можно надежно разместить в кеше. Если ваш кеш достаточно велик, чтобы вместить один байт на каждые пять ячеек, простейший подход может заключаться в том, чтобы один байт содержал пять значений в кодировке base-three в диапазоне 0-2 (существует 243 комбинации из 5 значений, так что помещается в байт), а также массив из 10 000 000 байтов, который будет запрашиваться всякий раз, когда значение base-3 указывает на «2».

Если кеш не такой большой, но может вместить один байт на 8 ячеек, тогда было бы невозможно использовать одно байтовое значение для выбора из всех 6561 возможных комбинаций восьми значений с основанием 3, но поскольку единственный эффект изменение 0 или 1 на 2 привело бы к ненужному поиску, правильность не потребовала бы поддержки всех 6,561. Вместо этого можно сосредоточиться на 256 наиболее «полезных» значениях.

Особенно, если 0 встречается чаще, чем 1, или наоборот, хорошим подходом может быть использование 217 значений для кодирования комбинаций 0 и 1, содержащих 5 или меньше единиц, 16 значений для кодирования от xxxx0000 до xxxx1111, 16 для кодирования от 0000xxxx до 1111xxxx и один для xxxxxxxx. Четыре значения останутся для любого другого использования. Если данные распределены случайным образом, как описано, незначительное большинство всех запросов будут попадать в байты, содержащие только нули и единицы (примерно в 2/3 всех групп из восьми все биты будут нулями и единицами, а примерно 7/8 из у них будет шесть или меньше 1 бит); Подавляющее большинство тех, кто этого не сделал, попадут в байт, содержащий четыре x, и будут иметь 50% шанс попасть на ноль или единицу. Таким образом, только один из четырех запросов потребует поиска в большом массиве.

Если данные распределены случайным образом, но кеш недостаточно велик, чтобы обрабатывать один байт на восемь элементов, можно попробовать использовать этот подход с каждым байтом, обрабатывающим более восьми элементов, но если нет сильного смещения в сторону 0 или 1 , доля значений, которые могут быть обработаны без необходимости выполнять поиск в большом массиве, будет уменьшаться по мере увеличения числа, обрабатываемого каждым байтом.

Добавлю в @ o11c , так как его формулировка может немного запутать. Если мне нужно сжать последний бит и цикл процессора, я бы сделал следующее.

Мы начнем с построения сбалансированного двоичного дерева поиска, которое содержит 5% случаев «что-то еще». При каждом поиске вы быстро проходите дерево: у вас есть 10000000 элементов: 5% из которых находятся в дереве: следовательно, структура данных дерева содержит 500000 элементов. Пройдя это за время O (log (n)), вы получите 19 итераций. Я не эксперт в этом, но я предполагаю, что есть некоторые реализации, эффективно использующие память. Прикинем:

• Сбалансированное дерево, поэтому положение поддерева может быть вычислено (индексы не нужно хранить в узлах дерева). Точно так же куча (структура данных) хранится в линейной памяти.
• 1 байтовое значение (от 2 до 255)
• 3 байта для индекса (10000000 занимает 23 бита, что соответствует 3 байтам)

Итого, 4 байта: 500000 * 4 = 1953 кБ. Подходит к кешу!

Для всех остальных случаев (0 или 1) вы можете использовать битовый вектор. Обратите внимание, что вы не можете исключить 5% других случаев для произвольного доступа: 1,19 МБ.

Комбинация этих двух использует приблизительно 3099 МБ. Используя этот метод, вы сэкономите 3,08 раза памяти.

Однако это не превосходит ответ @Matteo Italia (который использует 2,76 МБ), к сожалению. Что мы можем сделать дополнительно? Наиболее потребляемая память часть - это 3 байта индекса в дереве. Если мы сможем уменьшить это число до 2, мы сэкономим 488 КБ, а общее использование памяти составит: 2,622 МБ, что меньше!

как нам это сделать? Нам нужно уменьшить индексирование до 2 байтов. Опять же, 10000000 занимает 23 бита. Нам нужно иметь возможность сбросить 7 бит. Мы можем просто сделать это, разделив диапазон из 10000000 элементов на 2 ^ 7 (= 128) областей по 78125 элементов. Теперь мы можем построить сбалансированное дерево для каждой из этих областей, в среднем из 3906 элементов. Выбор правильного дерева осуществляется простым делением целевого индекса на 2 ^ 7 (или битовым сдвигом>> 7 ). Теперь требуемый индекс для хранения может быть представлен оставшимися 16 битами. Обратите внимание, что есть некоторые накладные расходы на длину дерева, которое необходимо сохранить, но это незначительно. Также обратите внимание, что этот механизм разделения уменьшает необходимое количество итераций для обхода дерева, теперь это сокращается до 7 итераций, потому что мы потеряли 7 бит: осталось только 12 итераций.

Обратите внимание, что теоретически вы можете повторить процесс, чтобы отрезать следующие 8 бит, но для этого потребуется создать 2 ^ 15 сбалансированных деревьев со средним значением ~ 305 элементов. В результате получится 2,143 МБ, всего с 4 итерациями для обхода дерева, что является значительным ускорением по сравнению с 19 итерациями, с которых мы начали.

В качестве окончательного вывода: это превосходит стратегию 2-битных векторов небольшим количеством используемой памяти, но это целая борьба за реализацию. Но если это может иметь значение, подходит ли установка кеша или нет, возможно, стоит попробовать.

Если вы выполняете только операции чтения, было бы лучше присваивать значение не одному индексу, а интервалу индексов.

Например:

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

Это можно сделать с помощью struct. Вы также можете определить подобный класс, если вам нравится объектно-ориентированный подход.

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
}

Теперь вам просто нужно перебрать список интервалов и проверить, находится ли ваш индекс в одном из них, что в среднем может потребовать гораздо меньше памяти, но требует больше ресурсов ЦП.

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

Если вы упорядочиваете интервалы по убыванию размера, вы увеличиваете вероятность того, что искомый элемент будет найден раньше, что еще больше снизит ваше среднее использование памяти и ресурсов процессора.

Вы также можете удалить все интервалы размером 1. Поместите соответствующие значения на карту и проверяйте их, только если искомый элемент не был найден в интервалах. Это также должно немного повысить среднюю производительность.

Давным-давно, я могу вспомнить ...

В университете нам поставили задачу ускорить программу трассировки лучей, которая должна многократно читать по алгоритму из буферных массивов. Друг посоветовал мне всегда использовать операции чтения из ОЗУ, кратные 4 байтам. Итак, я изменил массив с шаблона [x1, y1, z1, x2, y2, z2, ..., xn, yn, zn] на образец [x1, y1, z1,0, x2, y2, z2 , 0, ..., хп, уп, гп, 0]. Означает, что я добавляю пустое поле после каждой трехмерной координаты. После некоторого тестирования производительности: это было быстрее. Короче говоря: считайте несколько из 4 байтов из вашего массива из ОЗУ и, возможно, также из правильной начальной позиции, поэтому вы читаете небольшой кластер, в котором находится искомый индекс, и читаете искомый индекс из этого небольшого кластера в процессоре. (В вашем случае вам не нужно будет вставлять поля для заполнения, но концепция должна быть понятной)

Возможно также, что другие мультипликаторы могут быть ключевыми в новых системах.

Я не знаю, сработает ли это в вашем случае, поэтому, если это не сработает: извините. Если это сработает, я был бы рад услышать о некоторых результатах тестов.

PS: Да, и если есть какой-либо шаблон доступа или соседние индексы доступа, вы можете повторно использовать кэшированный кластер.

PPS: Возможно, множественный фактор был больше похож на 16 байтов или что-то в этом роде, это было слишком давно, я точно помню.

Глядя на это, вы можете разделить свои данные, например:

• битовый набор, который индексируется и представляет значение 0 (здесь может быть полезен std :: vector)
• битовый набор, который индексируется и представляет значение 1
• std :: vector для значений 2, содержащий индексы, которые относятся к этому значению
• карта для других значений (или std :: vector>)

В этом случае все значения появляются до указанного индекса, поэтому вы даже можете удалить один из битовых наборов и представить значение как отсутствующее в других.

Это сэкономит вам немного памяти на этот случай, но сделает худший случай хуже. Вам также понадобится больше мощности процессора для выполнения поиска.

Обязательно измерьте!

Как и упоминает Матс в своем комментарии-ответе, трудно сказать, что на самом деле является лучшим решением, не зная конкретно какие данные у вас есть (например, есть ли длинные прогоны 0 и т. Д.), И как выглядит ваш шаблон доступа как (означает ли «случайный» «повсюду», или просто «не строго линейно», или «каждое значение ровно один раз, только случайное» или ...).

При этом на ум приходят два механизма:

• Битовые массивы; то есть, если бы у вас было только два значения, вы могли бы тривиально сжать ваш массив в 8 раз; если у вас 4 значения (или «3 значения + все остальное»), вы можете сжать их в два раза. Это может просто не стоить хлопот и потребовать тестов, особенно если у вас действительно есть шаблоны произвольного доступа, которые избегают ваших кешей и, следовательно, вообще не изменяют время доступа.
• (index,value)или (value,index)таблицы. То есть, есть одна очень маленькая таблица для случая 1%, может быть одна таблица для случая 5% (в которой должны храниться только индексы, поскольку все они имеют одинаковое значение) и большой сжатый битовый массив для последних двух случаев. Под «таблицей» я подразумеваю то, что позволяет относительно быстрый поиск; то есть, возможно, хэш, двоичное дерево и так далее, в зависимости от того, что у вас есть, и ваших реальных потребностей. Если эти подтаблицы помещаются в ваши кеши 1-го / 2-го уровня, вам может повезти.

Я не очень знаком с C, но в C ++ вы можете использовать unsigned char для представления целого числа в диапазоне от 0 до 255.

По сравнению с обычным int (опять же, я из мира Java и C ++ ), в котором требуется 4 байта (32 бита), для unsigned char требуется 1 байт (8 бит). поэтому это может уменьшить общий размер массива на 75%.

Вы кратко описали все характеристики распределения вашего массива; бросить массив .

Вы можете легко заменить массив рандомизированным методом, который дает такой же вероятностный результат, как и массив.

Если согласованность имеет значение (получение одного и того же значения для одного и того же случайного индекса), рассмотрите возможность использования фильтра Блума и / или хэш-карты для отслеживания повторных совпадений. Однако, если доступ к вашему массиву действительно случайный, в этом нет необходимости.