Самый быстрый способ поиска строки

Question

У меня есть 300 строк, которые нужно хранить и искать, и что большинство из них идентичны по характеру и длине. Например, у меня есть строки «ABC1», «ABC2», «ABC3» и т. Д. и другой набор, подобный sample1, sample2, sample3. Поэтому я немного смущен, как хранить их, как использовать массив или хеш-таблицу. Моя основная забота - время, которое я беру для поиска строки, когда мне нужно вытащить ее из хранилища. Если я использую массив, мне нужно будет провести сравнение строк по всему индексу для меня, чтобы достигнуть одного. Теперь, если я пойду и внедряю хэш-таблицу, мне придется позаботиться о столкновениях (очевидно) и что мне придется внедрить цепочку для хранения идентичных строк.

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

Answer 1

Это зависит от того, насколько меняются ваши данные. С этим я имею в виду, если у вас есть 300 индексных строк, которые ссылаются на другую строку, как часто эти 300 строк индекса меняются?

Вы можете использовать std :: map для быстрого поиска, но карта будет требовать больше ресурсов, когда она будет создана в первый раз (по сравнению с массивом, вектором или списком).

Я использую карты в основном для каких-то динамических таблиц поиска (например: ip to socket).

Так что в вашем случае это будет выглядеть следующим образом:

std::map<std::string, std::string> my_map; 
my_map["ABC1"] = "sample1"; 
my_map["ABC2"] = "sample2"; 

std::string looked_up = my_map["ABC1"]; 

Answer 2

Поскольку ключи короткие как правило, имеет общий префикс, который следует рассмотреть Radix структуру данных, такие как синтаксическое дерево Patricia троичного дерево поиска (Google этих , вы найдете множество примеров). Время для поиска этих структур имеет тенденцию быть O (1) по отношению к # элементам и O (n) по длине ключей. Остерегайтесь, однако, что длинные строки могут использовать много памяти.

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

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