Структура данных для поиска большого числа

Question

У меня есть требование сделать поиск на основе большого количества. Число может падать в диапазоне 1 - 2^32. На основании ввода мне нужно вернуть другую структуру данных. Мой вопрос заключается в том, какую структуру данных я должен использовать, чтобы эффективно ее удерживать?

Я бы использовал массив, дающий мне O (1) поиск, если бы цифры находились в диапазоне, скажем, от 1 до 5000. Но когда мой номер ввода становится большим, становится нереально использовать массив, поскольку требования к памяти будут быть огромным.

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

Любые подсказки кто-нибудь?

EDIT:

Это не имело бы смысл использовать массив, так как я могу иметь только 100 или 200 индексов в магазин.

Абхишек

Answer 1

unordered_map или карту, в зависимости от того, какой версии C++ вы используете.

http://www.cplusplus.com/reference/unordered_map/unordered_map/

http://www.cplusplus.com/reference/map/map/

---

Простое решение в C, учитывая вы заявили в большинстве 200 элементов просто массив структур с индексом и указателем данных (или два массива, один из индексов и один из указателей данных, где индекс [i] соответствует данным [i]). Линейно ищите массив, который ищет нужный вам индекс. С небольшим количеством элементов (200) это будет очень быстро.

Answer 2

Одна из возможностей - это Judy Array, который является редким ассоциативным массивом. Имеется C Implementation. У меня нет прямого опыта, хотя они выглядят интересными и могут стоить экспериментировать, если у вас есть время.

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

Существует много реализаций C. Быстрый поиск в Google оказался uthash, который кажется подходящим, особенно потому, что он позволяет использовать любой тип значения в качестве ключа (многие реализации предполагают строку в качестве ключа). В вашем случае вы хотите использовать целое число в качестве ключа.