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

Этот вопрос пробудил мое любопытство, поэтому я провел несколько тестов, чтобы удовлетворить себя следующими результатами. Несколько общих замечаний:

• Применяются обычные предостережения о бенчмаркинге (не доверяйте моим цифрам, делайте свои собственные тесты с вашим конкретным вариантом использования и данными и т. Д.).
• Тесты проводились с использованием MSVS C ++ 2010 (оптимизация скорости, сборка релиза).
• Тесты проводились с использованием 10 миллионов циклов для повышения точности синхронизации.
• Имена генерировались путем случайной конкатенации 20 различных фрагментов строк в строки длиной от 4 до 65 символов.
• Имена включают только буквы, и некоторые тесты (trie) не учитывают регистр для простоты, хотя нет причин, по которым методы не могут быть расширены для включения других символов.
• Тесты пытаются соответствовать 99,975% -ому коэффициенту попадания, указанному в вопросе.

Базовое описание испытаний с соответствующими деталями:

• Строковая итерация — Просто перебирает имя функции для сравнения базового времени.
• карта — std::unordered_map<std::string, int>
• Задавать — std::unordered_set<std::string>
• BoostSet — boost::unordered_set<std::string>, v1.47.0
• CharMap — std::unordered_map<const char*, int>
• CharSet — std::unordered_set<const char*>
• FastMap — Просто std::unordered_map<> используя собственный алгоритм хеширования FNV-1a.
• FastSet — Просто std::unordered_set<> используя собственный алгоритм хеширования FNV-1a.
• CustomMap — Основная хэш-карта, которую я написал сам много лет назад.
• Trie — Стандартный файл, загруженный из Код Google.
• CustomTrie — Я написал сам.
• BinarySearch — С помощью std::binary_search() на сортированном std::vector<std::string>,
• SortArrayMap — Попытка использовать size_t VectorIndex[26][26][26][26][26] массив для индексации в отсортированный массив.
• PerfectMap — std::unordered_map<> используя идеальный хеш из Gperf.
• PerfectWordSet — С использованием Gperf is_word_set() функционировать напрямую.
• PerfectWordSetFunc — Такой же как PerfectWordSet но вызывается в функции вместо встроенного.
• PerfectWordSetThread — Такой же как PerfectWordSet но работа разбита на N потоков (стандартных оконных потоков). Синхронизация не используется, за исключением ожидания завершения потоков.

Результаты сортируются от самого медленного к быстрому (для большинства хитов ~ 99,975%):

• Trie — 9100 мс
• SortArrayMap — 6600 мс
• PerfectWordSetFunc — 4050 мс
• CustomTrie — 3470 мс
• BinarySearch — 3420 мс
• CustomMap — 2700 мс
• CharSet — 1300 мс
• CharMap — 1300 мс
• BoostSet — 1200 мс
• FastSet — 970 мс
• FastMap — 930 мс
• Оригинальный постер — 800 мс (по оценкам)
• Задавать — 730 мс
• карта — 690 мс
• PerfectMap — 650 мс
• PerfectWordSet — 500 мс
• PerfectWordSetThread (1) — 500 мс
• StringIteration — 350 мс
• PerfectWordSetThread (2) — 260 мс
• PerfectWordSetThread (4) — 150 мс
• PerfectWordSetThread (32) — 125 мс
• PerfectWordSetThread (8) — 120 мс
• PerfectWordSetThread (16) — 110 мс

Результаты сортируются от самого медленного до самого быстрого (в случае большинства промахов ~ 0,1% хитов):

• BinarySearch — ? (слишком долго)
• SortArrayMap — 8050 мс
• Trie — 3200 мс
• CustomMap — 1700 мс
• BoostSet — 920 мс
• CustomTrie — 850 мс
• FastMap — 590 мс
• FastSet — 580 мс
• CharSet — 550 мс
• CharMap — 550 мс
• StringIteration — 350 мс
• Задавать — 330 мс
• карта — 330 мс
• PerfectMap — 280 мс
• PerfectWordSet — 140 мс
• PerfectWordSetThread (1) — 130 мс
• PerfectWordSetThread (2) — 75 мс
• PerfectWordSetThread (4) — 45 мс
• PerfectWordSetThread (32) — 45 мс
• PerfectWordSetThread (8) — 40 мс
• PerfectWordSetThread (16) — 35 мс

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

Я полагаю, вы можете быть знакомы с таблица задержек что каждый программист должен знать. В вашем случае у вас есть 500 тысяч просмотров, выполняющихся за 40 мс, или 80 нс / поиск. При таком масштабе вы легко проиграете, если получите доступ к тому, чего еще нет в кеше L1 / L2. Это очень плохо, потому что у вас есть косвенный и, вероятно, нелокальный доступ к памяти для каждого символа. Принимая во внимание размер дерева в этом случае, я не мог придумать, как заставить все дерево поместиться в кэш для повышения производительности (хотя это может быть возможно). Я все еще думаю, что даже если бы вы сделали так, чтобы три полностью помещалось в кэш L2, вы проиграли бы со всей необходимой косвенностью.

std::unordered_ Контейнеры на самом деле очень хорошо справляются со своими задачами. На самом деле, пытаясь ускорить их, я на самом деле сделал их медленнее (в исследованиях под FastMap и FastSet).
То же самое с попыткой переключиться с std::string в const char * (примерно в два раза медленнее).

boost::unordered_set<> был в два раза медленнее, чем std::unordered_set<> и я не знаю, потому ли это, что я просто использовал встроенную хэш-функцию, использовал немного старую версию boost или что-то еще. Ты пытался std::unordered_set<> сам?

Используя gperf Вы можете легко создать идеальную хеш-функцию, если ваш набор строк известен во время компиляции. Вы также можете создать идеальный хеш во время выполнения, в зависимости от того, как часто новые строки добавляются на карту. Это дает вам увеличение скорости на 23% по сравнению со стандартной реализацией карты.

PerfectWordSetThread тесты просто используют идеальный хеш и разбивают работу на 1-32 потока. Эта проблема совершенно параллельна (по крайней мере, тест), поэтому вы получаете почти 5-кратное повышение производительности в случае с 16 потоками. Это дает только 6,3 мс / 500 тыс. Просмотров или 13 нс / поиск … всего 50 циклов на процессоре 4 ГГц.

StringIteration Дело действительно указывает на то, как трудно будет стать намного быстрее. Простая итерация найденной строки занимает 350 мс или 70% времени по сравнению со случаем отображения 500 мс. Даже если бы вы могли точно угадать каждую строку, вам все равно потребовалось бы это 350 мс (для 10 миллионов поисков), чтобы фактически сравнить и проверить соответствие.

Редактировать: Другая вещь, которая иллюстрирует, насколько трудны вещи, — это разница между PerfectWordSetFunc в 4050 мс и PerfectWordSet при 500 мс. Единственное различие между ними состоит в том, что один вызывается в функции, а другой — встроенный. Вызов его как функции снижает скорость в 8 раз. В базовом псевдокоде это просто:

bool IsInPerfectWordSet (string Match)
{
return in_word_set(Match);
}

//Inline benchmark: PerfectWordSet
for i = 1 to 10,000,000
{
if (in_word_set(SomeString)) ++MatchCount;
}

//Function call benchmark: PerfectWordSetFunc
for i = 1 to 10,000,000
{
if (IsInPerfectWordSet(SomeString)) ++MatchCount;
}

Это действительно подчеркивает разницу в производительности, которую может внести встроенный код / ​​функции. Вы также должны быть осторожны, чтобы убедиться, что вы измеряете в тесте. Иногда вы хотели бы включить накладные расходы вызова функции, а иногда нет.

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

Пара идей, на которые у меня нет знаний:

1. Оптимизация сборки с использованием SSE
2. Используйте графический процессор для дополнительной пропускной способности
3. Измените свой дизайн, чтобы вам не нужны быстрые поиски

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