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

Question

Я ищу двоичную структуру данных (дерево, список), которая обеспечивает очень быстрый поиск. Я буду добавлять / удалять элементы только в начале / конце программы, все сразу. Так что он будет фиксированного размера, поэтому мне не важна скорость вставки / удаления. По сути, я ищу структуру, которая обеспечивает быстрый поиск и не использует много памяти.

Спасибо

Answer 1

Найдите неупорядоченный набор в библиотеке Boost C ++ здесь . В отличие от красно-черных деревьев, которые являются O (log n) для поиска, неупорядоченный набор основан на хэше и в среднем дает вам O (1) производительность поиска.

Answer 2

Один контейнер, который нельзя пропустить, это отсортированный std :: vector.

Это определенно выигрывает от потребления памяти, особенно если вы можете зарезервировать () правильное количество сразу.

Answer 3

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

Только с 50 элементами он начинает становиться достаточно маленьким, чтобы теоретическая производительность Big-O могла быть затенена или, по крайней мере, измерима под влиянием фиксированных временных затрат алгоритма или структуры.

Например, массив вектор с линейным поиском часто является самым быстрым с менее чем десятью элементами из-за его простой структуры и ограниченного объема памяти.

Я бы обернул контейнер и запустил на нем реальные данные со временем. Начните с вектора STL, перейдите к стандартной карте STL, обновитесь до unordered_map и, возможно, даже попробуйте плотный Google или sparse_hash_map: http://google -sparsehash.googlecode.com / SVN / багажник / док / performance.html

Answer 4

Самым быстрым, как правило, является три / три.Я реализовал один в 3–15 раз быстрее, чем std :: unordered_map, они обычно используют больше оперативной памяти, если только вы не используете большое количество элементов.

Answer 5

std::map и хэш-карта - хороший выбор. У них также есть конструкторы, облегчающие одноразовое строительство.

Хеш-карта помещает ключевые данные в функцию, которая возвращает индекс массива. Это может быть медленнее, чем std::map, но скажет только профилирование.

Мое предпочтение будет std::map, так как оно обычно реализуется как тип двоичного дерева.

Answer 6

Один эффективный (хотя и немного запутанный) алгоритм - Красно-Черное дерево .

Внутренне стандартная библиотека c ++ использует красно-черные деревья для реализации std::map - см. этот вопрос