Всем добрый день. Помогите пожалуйста определится: какая структура данных в языке С++ наиболее оптимально подойдет для хранения большого количества десятизначных целых положительных чисел, если подразумевается только хранение этих чисел в выбранной структуре и поиск числа по значению. Важно , чтобы выбранная структура данных занимала как можно меньше объема памяти. Количество чисел 100'000'000'. Диапазон значений элемента - [0, 9 999 999 999].Добавление/удаление элемента не предусматривается.Заранее благодарен.
-
Обычный отсортированный массив?... Поиск O(log N), память N - минимальная, ни байта на служебные расходы :)– Harry1 сен 2020 в 12:33
-
"только хранение" - массив. быстро искать - отсортировать и бин поиском– Oh-Ben-Ben1 сен 2020 в 12:36
-
Большого количества - это сколько? И в каком диапазоне числа? Нужно ли уметь добавлять числа или достаточно начальной инициализации, а дальше только чтение?– EzikBro1 сен 2020 в 12:37
-
Диапазон чисел от 0 до 9 999 999 999. Количество 100 000 000. Добавлять/удалять/изменять элементы уметь не нужно.– arch11 сен 2020 в 12:42
2 ответа
Если "Добавлять/удалять/изменять не нужно" - теоретически можно использовать идеальное хеширование, тогда к минимальному объему добавится максимально быстрый поиск... Но это достаточно сложный путь.
Так что, думаю, проще всего - обычный массив. Только вот для представления такого диапазона чисел нужно 34 бита, так что обычного 4-байтового числа не хватит. Если память критична - можно соорудить 5-байтовые числа, и занять примерно 477 мегабайт. Если же 763 мегабайта - некритично, то можно воспользоваться массивом 8-байтовых unsigned long long
. Вариант с упаковкой битов от разных чисел, чтоб использовать только 405 мегабайт, не рассматриваем - можно, но слишком сложно, будет тормозить поиск.
Можно разбить на 4 массива, в которых хранить по 4 младших байта чисел, а номер массива от 0 до 3 - это старшие 2 бита. Получится неплохая экономия, до 382 мегабайт...
Конечно же, для применения бинарного поиска массив должен быть отсортирован.
Можно использовать array
- он не добавляет накладных расходов на косвенное обращение.
-
А не получится ли переполнение стэка, если я буду использовать для такого количества элементов std::array?)– arch11 сен 2020 в 13:08
-
1А вы его хотите сделать в стеке? Ну, можно попросить соответствующий стек, или разместить в глобальной памяти, или создать динамический массив(ы). Понятно, что при обычных стандартных размерах стека толку не будет. Но это уже не зависит от самого типа. В принципе, можно использовать
vector
, но с явным указанием размера - чтоб он не выделил памяти больше, чем надо (ну, тут вы должны верить в корректность его реализации :))– Harry1 сен 2020 в 13:11 -
24 массива -- отличная идея. Если же известно, что маленьких чисел много, то для них можно дополнительно использовать битовый массив (один бит на число)– avp1 сен 2020 в 20:08
Если количество чисел заранее известно, то std::array
. Если нет ― std::vector
.