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

Question

У меня есть некоторый файл словаря, который выглядит следующим образом:

 UTM University of Tennessee at Martin
 UMD University of Maryland

Это аббревиатура из 3 букв, за которой следует определение, разделенное символами новой строки.Всего в файле 9282 определения.

Мои вопросы:

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

Заранее спасибо за вашу помощь./ Новый связанный вопрос: Если бы я не хотел, чтобы мое приложение зависело от внешнего текстового файла, каков был бы лучший способ сделать это?

Answer 1

std::map легко и является частью базового STL.Вероятно, это самый простой вариант.

Если скорость действительно очень важна , вы можете сравнить несколько параметров:

• использовать хеш-таблицу (tr1::hash_map или boost::unordered_map) для поиска O (1) (требуется хеш).
• с использованием std::map O (log n) поисков
• создать vector<string> (или vector<const char*>) с 26 ^ 3 элементами (при условии, что аббревиатуры представляют собой все буквыAZ), и преобразовать аббревиатуру в индекс.

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

Вы можете превратить const char *acronym; в индекс примерно так:

const char *vector_of_names[26*26*26];

// Input 3-letter acronym, outputs the associated name.
const char *getName(const char* acronym) {
  return vector_of_names[
      ((acronyms[0]-'A') * 26*26) +
      ((acronyms[1]-'A') * 26) +
       (acronyms[2]-'A')];
}

Answer 2

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

Answer 3

Если важна скорость, хеш-карта кажется лучшим выбором.В Boost :: Unordered есть один.В противном случае std :: map , скорее всего, тоже будет работать.

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

Answer 4

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

Вы можете использовать insert, чтобы вставить свои элементы, и operator[], чтобы получить к ним доступ.

См. эту ссылку для получения дополнительной информации.