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

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

16 голосов
/ 28 апреля 2010

Я внедряю текстовую версию Scrabble для проекта College.

Мой словарь довольно большой, весит около 400.000 слов (std::string).

Поиск действительного слова будет большим отрывом с точки зрения эффективности, если я выберу vector<string> (O (n)). Есть ли хорошие альтернативы? Имейте в виду, я поступил в первый год. Ничего не сложного!

Спасибо за ваше время!

Francisco

Ответы [ 9 ]

23 голосов
/ 28 апреля 2010

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

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

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

9 голосов
/ 28 апреля 2010

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

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

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

6 голосов
/ 28 апреля 2010

Я провел некоторое профилирование и получил следующие результаты (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);
   }
}
6 голосов
/ 28 апреля 2010

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

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

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

3 голосов
/ 28 апреля 2010

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

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

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

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

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

2 голосов
/ 29 апреля 2010

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

2 голосов
/ 28 апреля 2010

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

2 голосов
/ 28 апреля 2010

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

1 голос
/ 28 апреля 2010

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

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

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

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

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

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

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

...