1

Всем добрый день. Помогите пожалуйста определится: какая структура данных в языке С++ наиболее оптимально подойдет для хранения большого количества десятизначных целых положительных чисел, если подразумевается только хранение этих чисел в выбранной структуре и поиск числа по значению. Важно , чтобы выбранная структура данных занимала как можно меньше объема памяти. Количество чисел 100'000'000'. Диапазон значений элемента - [0, 9 999 999 999].Добавление/удаление элемента не предусматривается.Заранее благодарен.

4
  • Обычный отсортированный массив?... Поиск O(log N), память N - минимальная, ни байта на служебные расходы :)
    – Harry
    1 сен 2020 в 12:33
  • "только хранение" - массив. быстро искать - отсортировать и бин поиском
    – Oh-Ben-Ben
    1 сен 2020 в 12:36
  • Большого количества - это сколько? И в каком диапазоне числа? Нужно ли уметь добавлять числа или достаточно начальной инициализации, а дальше только чтение?
    – EzikBro
    1 сен 2020 в 12:37
  • Диапазон чисел от 0 до 9 999 999 999. Количество 100 000 000. Добавлять/удалять/изменять элементы уметь не нужно.
    – arch1
    1 сен 2020 в 12:42

2 ответа 2

3

Если "Добавлять/удалять/изменять не нужно" - теоретически можно использовать идеальное хеширование, тогда к минимальному объему добавится максимально быстрый поиск... Но это достаточно сложный путь.

Так что, думаю, проще всего - обычный массив. Только вот для представления такого диапазона чисел нужно 34 бита, так что обычного 4-байтового числа не хватит. Если память критична - можно соорудить 5-байтовые числа, и занять примерно 477 мегабайт. Если же 763 мегабайта - некритично, то можно воспользоваться массивом 8-байтовых unsigned long long. Вариант с упаковкой битов от разных чисел, чтоб использовать только 405 мегабайт, не рассматриваем - можно, но слишком сложно, будет тормозить поиск.

Можно разбить на 4 массива, в которых хранить по 4 младших байта чисел, а номер массива от 0 до 3 - это старшие 2 бита. Получится неплохая экономия, до 382 мегабайт...

Конечно же, для применения бинарного поиска массив должен быть отсортирован.

Можно использовать array - он не добавляет накладных расходов на косвенное обращение.

3
  • А не получится ли переполнение стэка, если я буду использовать для такого количества элементов std::array?)
    – arch1
    1 сен 2020 в 13:08
  • 1
    А вы его хотите сделать в стеке? Ну, можно попросить соответствующий стек, или разместить в глобальной памяти, или создать динамический массив(ы). Понятно, что при обычных стандартных размерах стека толку не будет. Но это уже не зависит от самого типа. В принципе, можно использовать vector, но с явным указанием размера - чтоб он не выделил памяти больше, чем надо (ну, тут вы должны верить в корректность его реализации :))
    – Harry
    1 сен 2020 в 13:11
  • 2
    4 массива -- отличная идея. Если же известно, что маленьких чисел много, то для них можно дополнительно использовать битовый массив (один бит на число)
    – avp
    1 сен 2020 в 20:08
1

Если количество чисел заранее известно, то std::array. Если нет ― std::vector.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.