Соответствующая структура данных для более быстрого процесса поиска (размер данных: около 200 000 строковых значений)

У меня есть большой набор данных около 200 000 значений, все они являются строками. Какую структуру данных я должен использовать, чтобы процесс поиска и извлечения был быстрым. Вставка выполняется один раз, поэтому даже если вставка будет медленной, это не будет иметь большого значения.

Hash Map может быть одним из решений, но каковы другие варианты? Спасибо

Изменить: некоторые указатели 1. Я ищу точные совпадения, а не частичные. 2. Я должен сделать это на PHP. 3. Можно ли каким-то образом хранить такое количество данных в кеше в виде дерева или в другом формате?


php data-structures large-data-volumes
person Elvis    schedule 14.09.2011    source источник
comment
Можете ли вы точно указать, как вам нужно искать и извлекать? Я думаю, что ответ Raze2dust имел особое значение для поиска. Вам просто нужно искать точные совпадения? Или нужно найти ближайший?   -  person Ed Staub    schedule 14.09.2011
comment
@Ed: я ищу точные совпадения, а не частичные   -  person Elvis    schedule 15.09.2011

Ответы (5)


arrow_upward
1
arrow_downward

Вам действительно следует подумать об отказе от использования карт или хеш-словарей, если все, что вам нужно, это поиск строк. При их использовании ваши гарантии сложности для N элементов при поиске строки размера M составляют O (M x log (N)) или, что лучше всего амортизируется для хэша, O (M) с большим постоянным множителем. Гораздо эффективнее использовать ациклический детерминированный конечный автомат (ADFA) для базового поиска или Trie, если есть необходимость связать данные. Они будут проходить структуру данных по одному символу за раз, давая O (M) с очень небольшой сложностью множителя.

По сути, вам нужна структура данных, которая анализирует вашу строку по мере ее использования структурой данных, а не такую, которая должна выполнять полное сравнение строк в каждом узле поиска. Общие порядки сложности, которые вы видите для красно-черных деревьев, предполагают сравнение O (1), что неверно для строк. Строки - это O(M), и это распространяется на все используемые сравнения.

person ex0du5    schedule 14.09.2011
comment
Как хэш-словарь имеет время поиска O (log N)? - person Gabe; 15.09.2011
comment
Я заявил, что не использую ни карты, ни хэш-словари, и указал сложность первого и амортизированную сложность последнего. - person ex0du5; 15.09.2011

arrow_upward
1
arrow_downward

Возможно, структура данных trie.

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

person Juraj Blaho    schedule 15.09.2011

arrow_upward
0
arrow_downward

В этом случае используйте TreeMap. Поиск и извлечение будут O (log n). В случае HashMap поиск может быть O (n) в худшем случае, но поиск - O (1).

Для значений 200000 это, вероятно, не будет иметь большого значения, если только вы не работаете с аппаратными ограничениями. Я использовал HashMaps с 2 миллионами строк, и они все еще были достаточно быстрыми. YMMV.

person Hari Menon    schedule 14.09.2011
comment
Никогда не внедрял HASH, думаю, сейчас самое время поработать над этим :) - person Elvis; 14.09.2011
comment
имейте в виду, что я использовал Java Hashmaps. TreeMap в Java также является реализацией красно-черных деревьев. - person Hari Menon; 14.09.2011

arrow_upward
0
arrow_downward

Вы можете использовать деревья B+, если хотите, чтобы ваш поиск был минимальным за счет времени вставки.

Вы также можете попробовать нажать ведро и выполнить поиск.

person MduSenthil    schedule 14.09.2011
comment
Спасибо за ответ попробую реализовать ваше решение - person Elvis; 14.09.2011

arrow_upward
0
arrow_downward

Используйте хэш-карту. Предполагая реализацию, подобную Java, и нормальную частоту коллизий, поиск составляет O (m) - основная стоимость заключается в вычислении хэш-кода, а затем в одном сравнении строк. Это трудно победить.

Для любой реализации дерева/дерева учитывайте трудно поддающиеся количественной оценке затраты на дополнительные остановки конвейера, вызванные дополнительными выборками нелокализованных данных. Единственная причина его использования (в частности, trie) — возможно экономия памяти. Память экономится только при длинных строках. С короткими строками экономия памяти из-за уменьшенного хранения символов более чем компенсируется всеми дополнительными указателями/индексами.

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

Я не занимаюсь PHP - здесь могут быть языковые характеристики, которые искажают ответ.

person Ed Staub    schedule 15.09.2011
comment
Вы сталкивались с проблемами несогласованности кеша на практике? По мере того, как набор данных становится больше, коллизии становятся потенциально более дорогостоящими, и коллизии должны проходить нелокальные списки. С другой стороны, ациклические графы (ADFA, также известные как DAWG) могут быть реализованы таким образом, что конечные структуры располагаются в когерентных наборах кэша, так что у вас обычно есть в среднем 3 или 4 нелокальные выборки (с прогнозирующим ветвлением процессора, захватывающим первые 1 или 2 ). По моему опыту, ADFA немного быстрее в среднем, чем хэш, и на несколько порядков быстрее в худшем случае для наборов данных примерно указанного размера или больше. - person ex0du5; 16.09.2011
comment
Спасибо. Нет, не слышал, но ОП сказал (вставка один раз), что это только для чтения (и не сказал, что он многопоточный, если на то пошло, но давайте предположим), поэтому я не вижу как будет применяться несогласованность кеша - можете ли вы объяснить? Если оно доступно только для чтения, изменяет ли это вашу рекомендацию? Кроме того, я не могу представить 3 или 4 нелокальные выборки для 200 000 строк — сколько узлов вы представляете для выборки? Вы действительно думаете о реализации PHP, которая является рентабельной и выполнимой (во время разработки) для OP? - person Ed Staub; 16.09.2011
comment
Думаю, я имел в виду промахи устаревшего кеша, требующие доступа к шине памяти в целом, а не только устаревание, требующее восстановления согласованности. Извините за плохой вопрос. Я знаю, что наивная реализация просто выделяет узлы и может проходить новую страницу кеша для каждого символа, но я редко вижу, чтобы это имело место даже с этим наивным кодом. Часто вставка один раз имеет тенденцию упорядочивать листовые группы на одной странице только с помощью системного распределителя, поэтому, когда вы находитесь на 4-м или 5-м узле в глубину, вы остаетесь локальным. Множественная вставка также имеет тенденцию оставаться локальной за счет поиска соответствия шаблону вставки. - person ex0du5; 16.09.2011
comment
С другой стороны, я обычно видел хорошие хеш-алгоритмы с хорошей энтропией, низким уровнем коллизий и т. д., занимающие от 50 до 100 тактов процессора. Коллизии обычно вызывают нелокальный доступ, просматривая список коллизий. Мой опыт показывает, что использование ADFA обычно занимает 1/5 времени, а всплески хэша заставляют ADFA работать в 1/100 раза или лучше (с использованием словарей письменных языков и деревьев лингвистической грамматики - мое единственное знакомство). - person ex0du5; 16.09.2011
comment
Еще раз спасибо. Немного сложно поверить в цифру 5x/100x... но вы явно работали в этой области намного больше меня! - person Ed Staub; 16.09.2011