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

Такие посты стоит начинать с рассказа почему не подходят стандартные контейнеры из std вроде дерева и хешмапа.

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

Возможно кто-то решал уже такую задачу, и поделится каким нибудь более интересным рецептом.

1000

map, unordered_map и не выделываться? :)

Дерево оказалось быстрее

логично, учитывая характер ключей.

Ну их я сравнил, правда не все варианты ключей. На длинных ключах растущих монотонно выигрывает map (по крайней мере на моей платформе). Сравнивал правда с boost::unordered_map. Выигрыш примерно в 10 раз. Возможно, переделав хэшфункцию можно изменить ситуацию, тут кстати недавно мерялись - вот чего я вспомнил :)

Возможно кто-то решал уже такую задачу, и поделится каким нибудь более интересным рецептом.

Какую задачу? Всё ещё не понятно чем не подходит std::

Подходит даже std::list с сортировкой после вставки, или каким нибудь std::make_heap вопрос в оптимальном варианте.

начала ключей совпадают

если сильно совпадают, то может помочь trie, тогда поиск и удаление будут выполняться за key_size действий(еще и обрубить префиксы можно)

насчёт того, есть ли готовое, хз, но скорее всего будет быстрее std::map

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

Хм, а сейчас поискал - нашёл, видимо тогда оно мне было не нужно :)

Подходит даже std::list с сортировкой после вставки

Очевидно, что такая схема не подходит из-за сложности вставки O(N^2), нужно хотя бы вставлять сразу при поиске за O(N).

... вопрос в оптимальном варианте.

Ну ты в самом деле не понимаешь что сам не знаешь чего хочешь? На 1к скорость зависит от реализации и железа так, что между вариантами будет полный рандом. Можно хорошо сделать хешмап и плохо мап, может быть даже тупой поиск по вектору будет сравним с ними и т.д.

Но, похоже оно даже алгоритмически тут будет не быстрее, в силу того что в худшем случае на 1к записей будет искаться за 10 операций, а key_size >= 15?

Другое дело, что операции сравнения тут разные выходят, хм.

Говоришь ты вещи с сомнительным уровнем полезности, но навёл ты меня на мысль :) Надо только проверить её будет, т.к. похоже, данные у меня и так уже почти сортированные приходят. Возможно есть походящий алгоритм сортировки, для почти отсортированных коллекций, где-то что-то я про это слышал.

1к записей будет искаться за 10 операций

ты учти еще, что(для std::map) каждая операция сравнения за key_size выполняется

Количество записей порядка 1000

У тебя что, микроконтроллер? Или очень нагруженный код, который постоянно вызывается? Обычно пишут код, а потом занимаются оптимизацией, если это необходимо. Если хочешь извращений с поиском, то погляди на красно-черные деревья, обычно на них map делают, но ИМХО 1000 записей в 95% случаев не так много, чтобы заморачиваться.

А размер записи какой?

Попытайтесь заюзать контейнер, который при каждой вставке/удалении не требует выделения/освобождения памяти. В принципе для стандартных контейнеров решается выбором аллокатора.

Есть они, есть. Смотря, какое именно тебе нужно. Поищи реп на гитхабе от CosminBoaca, Boost.Trie называется (этот вариант пока ещё не слишком готов для буста, но я этим занимаюсь потиху :) ). +Есть ещё другие реализации.

ИМХО, для начала стоит написать обычный код на unordered_map/map (как я вижу, ты уже потестил, что у тебя быстрее обычная мапа). И только если упирается в перфоманс, то уже начинать оптимизировать.

1) Попробуйте написать свою хеш-функцию и снова померяй. 2) Поиграйтесь с кастомными аллокаторами. 3) Поиграйтесь с другирми контейнерами (например, boost::container::flat_map). На худой

std::vector + заполнение и вставка через std::upper_bound?

Размер записи сопоставим с размером ключа.

код, который постоянно вызывается

Ключ приходит из вне, начала ключей совпадают (можно сделать что бы не совпадали, но не представляю как это может помочь)

Это может помочь реализовать эффективную кастомную хэш-функцию для хэш-таблицы. А быстрее обычного массива (на котором хэш-таблицы и основаны) ты вряд-ли чего-то придумаешь.

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

... похоже, данные у меня и так уже почти сортированные приходят. Возможно есть походящий алгоритм сортировки, для почти отсортированных коллекций, где-то что-то я про это слышал.

Есть, но а какой профит от алгоритмов сортировки? Если записей много больше чтений, то можно сортировать вектор перед чтением, но вроде это не твой случай. Потенциально такой подход может дать профит в усреднённой скорости с большими периодическими лагами.

Но в общем случае навряд ли найдёшь что-то лучше хешмапа. Если есть существенное кол-во чтений по несуществующим ключам, то ещё можно ускорить поиск блум фильтром.

Шанс, что ключа не будет в коллекции имеется, только не знаю как посчитать вероятность. Можно в принципе просто статистику попробовать будет собрать. Мысль интересная, только, я думаю подобные оптимизации как раз про большие наборы данных (как работает фильтр не имею ни малейшего представления).