C++ - Эффективный контейнер для больших объемов доступных для поиска данных?

Если вектор отсортирован, вы можете использовать binary_search , чтобы проверить, существует ли данное слово в словаре.

Я провел некоторое профилирование и получил следующие результаты (MSVS 2008, / O2, сборка выпуска, запуск .exe отдельно).

РЕДАКТИРОВАТЬ - Теперь я понимаю, что на самом деле провалил свой первый тест, потому что я не разделил тест на сборку и поиск. Хотя "победителей" это не изменило, я провел несколько новых тестов. Итак, вот результаты, когда мы их разделим.

Во-первых, если плохих поисковых запросов почти нет (4 миллиона хороших поисковых попыток) .

[ RUN      ] Containers.DictionaryPrepare
[       OK ] Containers.DictionaryPrepare (234 ms)
[ RUN      ] Containers.VectorPrepare
[       OK ] Containers.VectorPrepare (704 ms)
[ RUN      ] Containers.SetPrepare
[       OK ] Containers.SetPrepare (593 ms)
[ RUN      ] Containers.MultisetPrepare
[       OK ] Containers.MultisetPrepare (578 ms)
[ RUN      ] Containers.UnorderedSetPrepare
[       OK ] Containers.UnorderedSetPrepare (266 ms)
[ RUN      ] Containers.UnorderedMultisetPrepare
[       OK ] Containers.UnorderedMultisetPrepare (375 ms)
[ RUN      ] Containers.VectorSearch
[       OK ] Containers.VectorSearch (4484 ms)
[ RUN      ] Containers.SetSearch
[       OK ] Containers.SetSearch (5469 ms)
[ RUN      ] Containers.MultisetSearch
[       OK ] Containers.MultisetSearch (5485 ms)
[ RUN      ] Containers.UnorderedSet
[       OK ] Containers.UnorderedSet (1078 ms)
[ RUN      ] Containers.UnorderedMultiset
[       OK ] Containers.UnorderedMultiset (1250 ms)
[----------] 11 tests from Containers (20516 ms total)

Это профилирование показывает, что вам следует использовать «обычные» варианты контейнера вместо «multi», и вам следует выбрать unordered_set . Это отлично подходит для создания времени и времени для поисковых операций.

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

Также обратите внимание, что для статических словарей вектор работает лучше (хотя для инициализации требуется больше времени), чем set , но что ж, это будет отстой, если вам нужно будет добавлять элементы.

[ RUN      ] Containers.DictionaryPrepare
[       OK ] Containers.DictionaryPrepare (235 ms)
[ RUN      ] Containers.VectorPrepare
[       OK ] Containers.VectorPrepare (718 ms)
[ RUN      ] Containers.SetPrepare
[       OK ] Containers.SetPrepare (578 ms)
[ RUN      ] Containers.MultisetPrepare
[       OK ] Containers.MultisetPrepare (579 ms)
[ RUN      ] Containers.UnorderedSetPrepare
[       OK ] Containers.UnorderedSetPrepare (265 ms)
[ RUN      ] Containers.UnorderedMultisetPrepare
[       OK ] Containers.UnorderedMultisetPrepare (375 ms)
[ RUN      ] Containers.VectorSearch
[       OK ] Containers.VectorSearch (3375 ms)
[ RUN      ] Containers.SetSearch
[       OK ] Containers.SetSearch (3656 ms)
[ RUN      ] Containers.MultisetSearch
[       OK ] Containers.MultisetSearch (3766 ms)
[ RUN      ] Containers.UnorderedSet
[       OK ] Containers.UnorderedSet (875 ms)
[ RUN      ] Containers.UnorderedMultiset
[       OK ] Containers.UnorderedMultiset (1016 ms)
[----------] 11 tests from Containers (15438 ms total)

Код проверки:

TEST(Containers, DictionaryPrepare) {
   EXPECT_FALSE(strings_initialized);
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      strings.push_back(generate_string());
   }
}

TEST(Containers, VectorPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      vec.push_back(strings[i]);
   }
   sort(vec.begin(), vec.end());
}

TEST(Containers, SetPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      set.insert(strings[i]);
   }
}

TEST(Containers, MultisetPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      multiset.insert(strings[i]);
   }
}

TEST(Containers, UnorderedSetPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      uo_set.insert(strings[i]);
   }
}

TEST(Containers, UnorderedMultisetPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      uo_multiset.insert(strings[i]);
   }
}

TEST(Containers, VectorSearch) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      std::binary_search(vec.begin(), vec.end(), strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      std::binary_search(vec.begin(), vec.end(), NONEXISTENT_ELEMENT);
   }
}

TEST(Containers, SetSearch) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      set.find(strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      set.find(NONEXISTENT_ELEMENT);
   }
}

TEST(Containers, MultisetSearch) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      multiset.find(strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      multiset.find(NONEXISTENT_ELEMENT);
   }
}

TEST(Containers, UnorderedSet) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      uo_set.find(strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      uo_set.find(NONEXISTENT_ELEMENT);
   }
}

TEST(Containers, UnorderedMultiset) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      uo_multiset.find(strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      uo_multiset.find(NONEXISTENT_ELEMENT);
   }
}

Я бы поддержал предложение Кена об использовании Trie, а также предположил, что вы могли бы значительно уменьшить размер дерева, сделав его более похожим на конечный автомат для общих префиксы и суффиксы. Например,
"нация",
"национальный",
"национализировать",
"национализировать",
«национализация»,
«разгосударствление»,
могут иметь общую структуру. Вы должны быть обеспокоены такими сомнительными словами, как
"национализация национализация"
Я использовал это много лет назад в программе коррекции орфографии.

A trie или radix tree даст вам время поиска и время вставки, которые линейны по длине искомой строки.

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

Эти решения, вероятно, излишни, если у вас их еще нет в вашей библиотеке.

Какова цель вашей структуры данных? Что вы хотите с ним делать?

• Проверить, есть ли в списке полное слово, например, «буря»?
• Найти все семибуквенные слова, начинающиеся и заканчивающиеся на «т»?
• Найти все семибуквенные слова, начинающиеся и заканчивающиеся на «т», которые можно составить из заданного набора букв?

Первый вопрос - это все, что вам нужно, если вы реализуете своего рода рефери для группы людей. игроки, то есть некоторая организация, которая проверяет предложенные слова по официальному словарю. Базовые структуры данных, такие как std :: map , std :: set , std :: vector , уже предложенные другими, сами по себе достаточны для этой цели.

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

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

std :: set является естественным для этого, потому что он требует почти нулевой работы помимо использования вектора. Тем не менее, я научу вас тому, чему вы обычно не учитесь, пока не станете профессионалом. Не оптимизируйте преждевременно. Я ставлю на современный компьютер, что поиск по линейному словарю в векторе строк размером 40К занимает 0,001 секунды.

В наборе это O (log n) и, вероятно, занимает 0,00001 секунды.

Все, что не входит в STL, - пустая трата времени. Не тратьте 10 долларов работы на задачу на 10 центов.

Используйте std :: tr1 :: unordered_set , и это даст вам постоянный поиск по времени. (Линейная длина строки, согласно другому моему ответу.)

Я предлагаю использовать длину слова и первые буквы в качестве первых двух элементов поиска. Пусть данные будут организованы для поддержки этого алгоритма.

Сначала определим контейнер для всех слов одинаковой длины:

typedef std::vector<std::string> Word_Container;

Эта структура данных должна быть отсортирована, чтобы можно было использовать бинарный поиск.

Далее будет создана индексная таблица. Таблица индексов будет иметь вид <длина слова, указатель на контейнер слова>:

typedef std::map<unsigned int, Word_Container *> Index_Table;

И, наконец, будет создан массив таблиц индексов, используя первую букву слова в качестве индекса:

Index_Table alpha_array[26]; // ASCII A - Z.

Алгоритм следующий:
Вычисляем индекс в alpha_array:
index = word[0] - 'A';

Используем индекс для получения связанной индексной таблицы:
Index_Table& table = alpha_array[index];

Используем длину слова как ключ для поиска таблицы, чтобы получить контейнер слова:
Word_Container * p_word_container = table[word. length()];

Поиск контейнера для точного слова:

bool found = false;
if (p_word_container)
{
    found = std::binary_search(p_word_container->begin(), p_word_container->end(), word);
}

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