С++ - эффективный контейнер для большого количества доступных для поиска данных?

Ответ 1

Если вы хотите найти что-то, что находится в стандартной библиотеке, вы можете использовать std::set со словом в качестве ключа. Это даст вам логарифмическое время поиска.

Так как ваш словарь предположительно статичен (т.е. создан один раз и не изменен), вы также можете использовать std::vector, сортировать его с помощью std::sort, а затем использовать std::binary_search для отсортированного вектора для поиска слова. Это также даст логарифмическое время поиска и, возможно, будет более эффективным по сравнению с set.

Если вы хотите реализовать свою собственную структуру данных, trie будет хорошим выбором.

Ответ 2

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

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

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

Ответ 3

A trie или дерево оснований будет давать вам время поиска и время вставки, которые являются линейными по длине строки, которую вы ищете.

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

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

Ответ 4

Я сделал некоторые профилирования и получил следующие результаты (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 миллионам). Победитель остается тем же.

Также обратите внимание, что для статических словарей vector выполняется лучше (хотя для инициализации требуется больше времени), чем 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);
   }
}

Ответ 5

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

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

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

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

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

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

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);
}

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