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

Ответ 1

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

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

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, некоторые некоторые новые 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 следует принять с некоторой осторожностью - они являются виртуальными машинами на довольно занятом сервере с двойной розеткой виртуальных машин; вполне возможно, что, хотя номинально он имеет приличный объем кэша, во время теста он несколько раз вытесняется полностью несвязанными виртуальными машинами.

Ответ 2

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

• проверьте, равен ли результат 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% случаев. Конечно, как обычно, если это хорошая идея или нет, зависит от многих других условий, поэтому единственный ответ - экспериментировать с реальным использованием.

Ответ 3

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

Если ваши данные не являются чем-то известным, я сомневаюсь, что кто-то может НАСТОЯЩИМ ответить на ваш вопрос (и я не знаю ничего, что соответствует вашему описанию, но тогда я не знаю ВСЕ о всех типах шаблонов данных для всех виды прецедентов). Редкие данные - общая проблема в высокопроизводительных вычислениях, но обычно это "у нас очень большой массив, но только некоторые значения отличны от нуля".

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

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

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

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

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

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

Ответ 4

То, что я делал в прошлом, это использовать хэш-карту перед битрейтом.

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

Часто, однако, "кеш - это король".

Ответ 5

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

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

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

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

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

Ответ 6

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

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

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

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

Ответ 7

Я добавлю к ответу @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 МБ.

Комбинация этих двух использует приблизительно 3,099 МБ. Используя эту технику, вы сэкономите 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-битную векторную стратегию крошечным битом использования памяти, но это целая борьба за реализацию. Но если это может повлиять на установку кеша или нет, возможно, стоит попробовать.

Ответ 8

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

Например:

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

Это можно сделать с помощью структуры. Вы также можете захотеть определить класс, подобный этому, если вам нравится подход 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
}

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

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. Поместите соответствующие значения в карту и проверьте их, только если элемент, который вы ищете, не найден в интервалах. Это также должно повысить среднюю производительность.

Ответ 9

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

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

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

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

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

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

Ответ 10

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

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

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

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

Не забудьте измерить!

Ответ 11

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

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

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

Ответ 12

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

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

Ответ 13

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

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

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