> -- Сергей Губанов писал(а):
> Длина текста 100'000'000. Количество слов 10. Быстрее на 52%Длина текста 10'000'000. Количество слов 100. Быстрее на 52%Длина текста 1'000'000. Количество слов 1'000. Быстрее на 42%Длина текста 100'000. Количество слов 10'000. Быстрее на 13%Длина текста 10'000. Количество слов 100'000. Быстрее на 7%Длина текста 1'000. Количество слов 1'000'000. Быстрее на 6.9%При больших словарях (от 100 слов) целесообразно использовать другой алгоритм решения:
1. Отсортировать слова в словаре, например, с помощью быстрой сортировки (затраты времени ~ N*log(N), где N - количество слов в словаре);
2. Для каждого слова текста:
3. Найти вхождение в словаре, например, с помощью бинарного поиска (затраты времени ~ M*log(N), где M - количество слов в тексте);
Очевидно, что сортировка выполняется один раз, а каждый поиск даст экономию (при обычном сканировании словаря затраты времени в среднем составят ~ M*N/2).
Примечание: Во всех приведённых формулах "затраты времени" считаются пропорциональными количеству операций сравнения.