Преобразование целочисленных идентификаторов в указатели - PullRequest
Новая
       15

Преобразование целочисленных идентификаторов в указатели

1 голос
/ 27 августа 2009

У меня есть значения идентификатора типа unsigned int. Мне нужно сопоставить идентификатор с указателем в постоянное время .

Распределение ключей:

ID будет иметь значение в диапазоне от 0 до uint_max. Большинство ключей будут сгруппированы в одну группу, но будут выбросы.

Реализация:

  • Я думал об использовании C ++ ext hash_map, но я слышал, что их производительность не слишком велика, когда ключи имеют большой потенциальный диапазон.

  • Я также подумал об использовании некоторой формы цепного поиска (эквивалентно рекурсивному делению диапазона на C-чаки). Если в диапазоне нет клавиш, этот диапазон будет указывать на NULL.

    N = ключевой диапазон

    Уровень 0 (делится на C = 16, поэтому 16 штук) = [0, N / 16), [N / 16, 2 * (N / 16)), ...

    Уровень 1 (делится на C = 16, поэтому 16 * 16 штук) = ...

У кого-нибудь еще есть идеи о том, как более эффективно реализовать это отображение?

Обновление:

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

Ответы [ 7 ]

11 голосов
/ 27 августа 2009

Использовать хэш-карту (unordered_map). Это дает ~ O (1) времени поиска. Вы «слышали», что это плохо, но пытались ли вы это проверить, определить, что это проблема? Если нет, используйте хэш-карту.

После того, как ваш код близок к завершению, профилируйте его и определите, является ли время поиска основной причиной замедления вашей программы. Скорее всего, это не будет.

3 голосов
/ 27 августа 2009

Если вам нужно решение на основе дерева, и ваши идентификаторы находятся в диапазоне {0..n-1}, вы можете использовать очень классную структуру данных под названием van Emde Boas tree . Это приведет ко всем операциям в O (log log n) и использует пространство O (n).

1 голос
/ 27 августа 2009

Сколько предметов должно быть на такой карте и как часто она меняется?

Если все значения помещаются в кэш процессора, тогда std::vector<std::pair<unsigned int,T*>> с предварительно отсортированными значениями и двоичным поиском может быть самым быстрым, несмотря на то, что доступ равен O (N).

1 голос
/ 27 августа 2009

Как предполагает GMan, unordered_map, вероятно, является хорошим решением. Если вас беспокоит большое количество коллизий в этой хэш-карте, используйте хеш-функцию, которая удалит кластеризацию ваших данных. Например, вы можете поменять местами байты.

Следует отметить, что вы, вероятно, потратите больше времени на отладку и проверку собственной структуры данных, чем на ту, у которой уже есть хорошая родословная.

1 голос
/ 27 августа 2009

Зарезервируйте для этого 4 ГБ ОЗУ и просто приведите свою указатель к указателю. Это определенно постоянное время.

1 голос
/ 27 августа 2009

Если ваши целочисленные значения имеют ширину 32 бита, вы можете использовать 64-битную платформу, выделить 32 гигабайта памяти (8 байт на 4 миллиарда указателей) и использовать плоский массив. Это будет как можно ближе к постоянному времени поиска.

1 голос
/ 27 августа 2009

Вы не получите постоянное время.

Я бы, наверное, использовал B + Tree

...