Любая оптимизация для произвольного доступа на очень большом массиве, когда значение в 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 бит, это уменьшит использование памяти почти на порядок.
Такое ощущение, что должно быть более эффективное решение для памяти, которое значительно уменьшило бы требуемую для этого пропускную способность ОЗУ и, как следствие, значительно ускорило бы произвольный доступ.
Решение
Простая возможность, которая приходит на ум, — это сохранить сжатый массив из 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)
Приведенный выше код заполняет массив элементов 10M случайными данными, распределенными как 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
Результаты … смешанные!
- Вообще, на большинстве этих машин есть какое-то ускорение, или, по крайней мере, они на одном уровне.
- Два случая, когда массив действительно превосходит поиск «умной структуры», находятся на машинах с большим количеством кеша и не особенно загруженными: Xeon E5-1650 выше (кеш 15 МБ) — это машина ночной сборки, в настоящий момент довольно простаивающая; Xeon E5-2697 (кэш-память 35 МБ) — это машина для высокопроизводительных вычислений, в том числе и в свободное время. Это имеет смысл, оригинальный массив полностью помещается в их огромный кэш, поэтому компактная структура данных только добавляет сложности.
- На противоположной стороне «спектра производительности» — но там, где снова массив немного быстрее, есть скромный Celeron, который питает мой NAS; у него так мало кеша, что ни массив, ни «умная структура» не помещаются в нем вообще. Другие машины с достаточно маленьким кешем работают аналогично.
- К 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». Кроме того, вам придется вести таблицу «начальных точек», чтобы вы могли довольно быстро добраться до нужного места.
Я давно знаю, что некоторые большие базы данных — это просто большие таблицы в оперативной памяти (данные абонентов телефонной станции в этом примере), и одна из проблем заключается в том, что кеширование и оптимизация таблиц страниц в процессоре довольно бесполезны. Вызывающая сторона настолько редко совпадает с той, которая недавно вызывала кого-то, что никаких предварительно загруженных данных нет, это просто случайные данные. Большие таблицы страниц — лучшая оптимизация для этого типа доступа.
Во многих случаях компромисс между «скоростью и малым размером» — это одна из тех вещей, которые вам приходится выбирать между разработчиками программного обеспечения [в других разработках это не обязательно является компромиссом]. Таким образом, «тратить память на более простой код» часто является предпочтительным выбором. В этом смысле «простое» решение, скорее всего, лучше по скорости, но если у вас «лучше» использовать оперативную память, то оптимизация по размеру таблицы даст вам достаточную производительность и хорошее улучшение по размеру. Есть много разных способов достижения этого — как предложено в комментарии, 2-битное поле, в котором хранятся два или три наиболее распространенных значения, а затем некоторый альтернативный формат данных для других значений — хеш-таблица будет моей Первый подход, но список или двоичное дерево может работать тоже — опять же, это зависит от того, где находятся ваши «не 0, 1 или 2». Опять же, это зависит от того, как значения «разбросаны» по таблице — они в кластерах или это скорее равномерно распределенный шаблон?
Но проблема в том, что вы все еще читаете данные из оперативной памяти. Затем вы тратите больше кода на обработку данных, включая некоторый код, чтобы справиться с «это не обычное значение».
Проблема большинства распространенных алгоритмов сжатия заключается в том, что они основаны на распаковке последовательностей, поэтому вы не можете получить к ним произвольный доступ. Слишком маловероятно, что издержки разделения ваших больших данных на куски, скажем, 256 записей за раз, и распаковки 256 в массив uint8_t, выборки нужных вам данных и отбрасывания несжатых данных, вряд ли дадут вам производительность — при условии, что это имеет какое-то значение, конечно.
В конце вам, вероятно, придется реализовать одну или несколько идей в комментариях / ответах, чтобы проверить, поможет ли это решить вашу проблему или шина памяти все еще является основным ограничивающим фактором.
В прошлом я использовал хэш-карту в фронт из набора.
Это вдвое меньше места по сравнению с ответом Маттео, но может быть медленнее, если поиск «исключений» идет медленно (то есть существует много исключений).
Часто, однако, «кеш — король».
Если в ваших данных нет закономерностей, маловероятно, что будет какая-либо ощутимая оптимизация скорости или размера, и — если вы нацелены на обычный компьютер — 10 МБ в любом случае не так уж и много.
В ваших вопросах есть два предположения:
- Данные плохо хранятся, потому что вы не используете все биты
- Хранение этого лучше сделало бы вещи быстрее.
Я думаю, что оба эти предположения неверны. В большинстве случаев подходящим способом хранения данных является хранение наиболее естественного представления. В вашем случае это тот, который вы выбрали: байт для числа от 0 до 255. Любое другое представление будет более сложным и, следовательно, при прочих равных условиях, будет медленнее и подвержено ошибкам. Чтобы отклониться от этого общего принципа, вам нужна более веская причина, чем потенциально шесть «потраченных впустую» битов на 95% ваших данных.
По вашему второму предположению, это будет верно, если и только если изменение размера массива приведет к существенно меньшему количеству пропусков кэша. То, произойдет ли это, может быть определено только путем профилирования рабочего кода, но я думаю, что это вряд ли будет иметь существенное значение. Поскольку в любом случае вы будете получать произвольный доступ к массиву, процессору будет сложно узнать, какие биты данных следует кэшировать и сохранить в любом случае.
Если данные и доступы равномерно распределены случайным образом, производительность, вероятно, будет зависеть от того, какая часть доступа избегает пропадания кэша внешнего уровня. Оптимизация, которая потребует знания, какой размер массива может быть надежно размещен в кеше. Если ваш кэш достаточно большой, чтобы вместить один байт на каждые пять ячеек, самый простой подход может состоять в том, чтобы один байт содержал пять закодированных базовых трех значений в диапазоне 0-2 (имеется 243 комбинации из 5 значений, так что помещается в байт) вместе с массивом из 10 000 000 байтов, который будет запрашиваться всякий раз, когда значение base-3 указывает «2».
Если кэш не такой большой, но может вместить один байт на 8 ячеек, то будет невозможно использовать одно байтовое значение для выбора среди всех 6 561 возможных комбинаций восьми значений base-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 доля значений, которые могут быть обработаны без необходимости поиска в большом массиве, будет уменьшаться по мере увеличения числа, обрабатываемого каждым байтом.
Я добавлю к @ 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
...
Это можно сделать с помощью структуры. Вы также можете определить класс, подобный этому, если вам нравится ОО-подход.
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. Поместите соответствующие значения в карту и проверяйте их, только если искомый элемент не был найден в интервалах. Это также должно немного повысить среднюю производительность.