Хотя ответ Джона Скита дает хорошую экономию при небольших инвестициях, я думаю, вы можете добиться большего.Поскольку ваши числа довольно равномерно распределены, вы можете использовать интерполяционный поиск для более быстрого поиска (примерно O (log log N) вместо O (log N)).Для миллиона предметов вы, вероятно, можете запланировать около 4 сравнений вместо 20.
Если вы хотите проделать еще немного работы, чтобы снова сократить память (примерно) пополам, вы можете построить ее какдвухуровневая таблица поиска, в основном своего рода простая версия дерева.
Вы бы разбили свое (предположительно) 32-разрядное целое число на две 16-разрядные части,Вы использовали бы первые 16 битов в качестве индекса первого уровня таблицы поиска.На этом уровне у вас будет 65536 указателей, по одному на каждое возможное 16-битное значение для этой части вашего целого числа.Это приведет вас ко второму уровню таблицы.Для этой части мы выполнили бы бинарный или интерполяционный поиск между выбранным указателем и следующим повышением, т. Е. Всеми значениями второго уровня, которые имели такое же значение в первых 16 битах.
Однако, когда мы смотрим во вторую таблицу, мы уже знаем 16 битов значения - поэтому вместо сохранения всех 32 битов значения нам нужно только сохранить другие 16 битов значения.
Это означает, что вместо второго уровня, занимающего 4 мегабайта, мы сократили его до 2 мегабайт.Наряду с этим нам нужна таблица первого уровня, но она составляет всего 65536x4 = 256 Кбайт.
Это почти наверняка улучшит скорость по сравнению с бинарным поиском всего набора данных.В худшем случае (используя бинарный поиск для второго уровня) у нас может быть целых 17 сравнений (1 + log 2 65536).Среднее значение будет лучше, чем это, хотя - поскольку у нас есть только миллион элементов, в каждом «разделе» второго уровня может быть в среднем только 1_000_000 / 65536 = ~ 15 элементов, что дает примерно 1 + log 2 (16) = 5 сравнений.Использование интерполяционного поиска на втором уровне может немного уменьшить это, но когда вы только начинаете с 5 сравнений, у вас не остается много места для действительно существенных улучшений.Учитывая в среднем всего ~ 15 элементов на втором уровне, тип поиска, который вы используете, не будет иметь большого значения - даже линейный поиск будет довольно быстрым.
Конечно, если вы хотите, вы можете пойти еще дальше и использовать вместо этого четырехуровневую таблицу (по одному на каждый байт в целом числе).Однако может возникнуть вопрос, сможет ли это сэкономить вам достаточно денег, чтобы стоить того, что стоит.По крайней мере, сразу, я сразу догадываюсь, что вы проделали бы довольно много дополнительной работы для довольно минимальной экономии (простое хранение последних байтов миллиона целых чисел, очевидно, занимает 1 мегабайт, и три уровня таблицы, ведущие к этому, явноЗанимайте приличную сумму больше, так что вы удвоите количество уровней, чтобы сэкономить что-то наполовину мегабайт. Если вы находитесь в ситуации, когда сохранение немного больше будет иметь большое значение, пойти на это - но в противном случае,Я сомневаюсь, оправдывает ли возврат дополнительные инвестиции.