Почему реализованный в С++ string::find() не использует алгоритм KMP (и не запускается в O(N + M)) и запускается в O(N * M)? Это исправлено в C++0x? Если сложность текущей находки не O(N * M), то что это?
так какой алгоритм реализован в gcc? это КМП? если нет, то почему? Я проверил это, и время работы показывает, что оно работает в O(N * M)
Почему реализованная в С++ string::substr() не использует алгоритм KMP (и не работает за O(N + M)) и работает за O(N * M)?
Я предполагаю, что вы имеете в виду find(), а не substr(), который не нуждается в поиске и должен выполняться за линейное время (и только потому, что он должен копировать результат в новую строку).
Стандарт C++ не определяет деталей реализации, а лишь в некоторых случаях указывает требования к сложности. Единственные требования сложности к операциям std::string заключаются в том, что size(), max_size(), operator[], swap(), c_str() и data() все являются постоянным временем. Сложность всего остального зависит от выбора, сделанного тем, кто реализовал библиотеку, которую вы используете.
Наиболее вероятная причина выбора простого поиска, а не чего-то вроде KMP, заключается в том, чтобы избежать необходимости в дополнительном хранилище. Если искомая строка не очень длинная и строка для поиска не содержит много частичных совпадений, время, необходимое для выделения и освобождения, вероятно, будет намного больше, чем стоимость дополнительной сложности.
Это исправлено в c++0x?
Нет, C++11 не добавляет никаких требований к сложности std::string и уж точно не добавляет каких-либо обязательных деталей реализации.
Если сложность текущей подстроки не O(N * M), что это?
Это наихудшая сложность, когда искомая строка содержит много длинных частичных совпадений. Если символы имеют достаточно равномерное распределение, то средняя сложность будет ближе к O(N). Таким образом, выбрав алгоритм с лучшей сложностью для наихудшего случая, вы вполне можете сделать более типичные случаи намного медленнее.
O(N * M) для малых N и KMP для больших N. Также требуется O(N) памяти, поэтому общий порядок памяти не меняется.
- person Farzam; 15.01.2012
M и N. Надежная оценка того, какой алгоритм будет быстрее, будет столь же сложной, как и выполнение самого поиска, и я не думаю, что усложнение алгоритма ненадежной оценкой принесет кому-либо пользу. Но, конечно, я не изучал это так много, как те, кто реализовывал библиотеки, поэтому я не могу точно комментировать, почему, по крайней мере, некоторые из них выбрали простую реализацию, помимо уже сделанных мной наблюдений.
- person Mike Seymour; 15.01.2012
std::search(), и лучше потратить время на улучшение других алгоритмов (мне кажется, что я говорю как PJ!), 3. для ожидаемых вариантов использования O (n * m), по-видимому, имеет лучшую или, по крайней мере, приемлемую производительность. Правда, я не реализовал KMP для проверки.
- person Dietmar Kühl; 15.01.2012
std::search(): в то время как std::search() поддерживается на прямых итераторах, поиск KMP довольно активно использует массивы, и я пока не вижу, как избежать продвижения итераторов (ну , вариант, который у меня сейчас есть, даже не пытайтесь: он требует итераторов произвольного доступа), хотя я думаю, что результирующая сложность все равно должна быть линейной (однако я не совсем убедился в этом).
- person Dietmar Kühl; 16.01.2012
К вашему сведению, string::find в gcc/libstdc++ и llvm/libcxx работал очень медленно. Я значительно улучшил их обоих (в некоторых случаях примерно в 20 раз). Возможно, вы захотите проверить новую реализацию:
GCC: PR66414 оптимизировать std::string::find https://github.com/gcc-mirror/gcc/commit/fc7ebc4b8d9ad7e2891b7f72152e8a2b7543cd65
LLVM: https://reviews.llvm.org/D27068
Новый алгоритм проще и использует оптимизированные вручную функции сборки memchr и memcmp.
Откуда у вас такое впечатление, что std::string::substr() не использует линейный алгоритм? На самом деле, я даже не могу представить, как реализовать такую сложность, которую вы указали. Кроме того, здесь не так много алгоритма: возможно ли, что вы думаете, что эта функция делает что-то еще, чем она? std::string::substr() просто создает новую строку, начиная с ее первого аргумента и используя либо количество символов, указанное вторым параметром, либо символы до конца строки.
Возможно, вы имеете в виду std::string::find(), у которого нет требований к сложности, или std::search(), которому действительно разрешено выполнять O(n * m) сравнений. Однако это дает разработчикам свободу выбора между алгоритмом с наибольшей теоретической сложностью и алгоритмом, который не требует дополнительной памяти. Поскольку выделение произвольных объемов памяти, как правило, нежелательно, если это специально не запрошено, это кажется разумным.
Стандарт С++ не диктует характеристики производительности substr (или многих других частей, включая find, на которую вы, скорее всего, ссылаетесь со сложностью M*N).
В основном он диктует функциональные аспекты языка (за некоторыми исключениями, такими как, например, неустаревшие функции sort).
Реализации могут даже свободно реализовывать qsort как пузырьковую сортировку (но только если они хотят, чтобы их высмеяли и, возможно, разорили).
Например, в разделе 21.4.7.2 basic_string::find C++11 всего семь (очень маленьких) подпунктов, и ни один из них не определяет параметры производительности.
qsort(), но std::sort() требуется для сложности O(n * ln(n)) в С++ 2011. В C++2003 разрешалось иметь сложность O(n * n) для quicksort быть жизнеспособным выбором для алгоритма, но было показано, что вы можете получить аналогичную нормальную производительность с помощью introsort как вы получили бы для быстрой сортировки, имея наихудшую сложность O (n * ln (n)). Разработчик может использовать другой алгоритм с такой же сложностью в худшем случае.
- person Dietmar Kühl; 15.01.2012
qsort не имеет таких требований, он чисто функциональный, такой же, как и в C. Что еще более важно, хотя некоторые части C++ имеют такие требования, substr и find не являются частью этого подмножества. Но вы подняли хороший вопрос о неустаревшей сортировке, поэтому я добавил это к ответу.
- person paxdiablo; 15.01.2012
Давайте заглянем в книгу CLRS. На странице 989 третьего издания у нас есть следующее упражнение:
Предположим, что шаблон P и текст T представляют собой случайно выбранные строки длины m и n соответственно из d-ичного алфавита Ʃd = {0; 1; ...; d}, где d >= 2. Покажите, что ожидаемое количество посимвольных сравнений, выполняемых неявным циклом в строке 4 наивного алгоритма, составляет
более все выполнения этого цикла. (Предположим, что наивный алгоритм прекращает сравнение символов для заданного сдвига, как только обнаруживает несоответствие или совпадает со всем шаблоном.) Таким образом, для случайно выбранных строк наивный алгоритм достаточно эффективен.
NAIVE-STRING-MATCHER(T,P)
1 n = T:length
2 m = P:length
3 for s = 0 to n - m
4 if P[1..m] == T[s+1..s+m]
5 print “Pattern occurs with shift” s
Доказательство:
Ожидается, что за одну смену мы выполним 1 + 1/d + ... + 1/d^{m-1} сравнений. Теперь используйте формулу суммирования и умножьте на количество допустимых смен, то есть n - m + 1. □
Откуда вы берете информацию о библиотеке C++? Если вы действительно имеете в виду string::search и он действительно не использует алгоритм KMP, то я предполагаю, что это потому, что этот алгоритм обычно не быстрее, чем простой линейный поиск, из-за необходимости построить таблицу частичного соответствия, прежде чем поиск может быть продолжен.
Если вы собираетесь искать один и тот же шаблон в нескольких текстах. Алгоритм Бойера-Мура является хорошим выбором, поскольку таблицы шаблонов нужно вычислить только один раз, но они используются несколько раз при поиске нескольких текстов. Однако, если вы собираетесь искать шаблон только один раз в 1 тексте, накладные расходы на вычисление таблиц вместе с накладными расходами на выделение памяти слишком сильно замедлят вас, и std::string.find(....) превзойдет вас. так как он не выделяет никакой памяти и не имеет накладных расходов. Boost имеет несколько алгоритмов поиска строк. Я обнаружил, что BM был на порядок медленнее в случае поиска по одному шаблону в 1 тексте, чем std::string.find(). В моих случаях BoyerMoore редко был быстрее, чем std::string.find(), даже при поиске нескольких текстов с одним и тем же шаблоном. Вот ссылка на BoyerMoore Бойер Мур
string::find, см. мой пост: stackoverflow.com/questions/19506571/ - person Peter Lee schedule 25.10.2013(std::string(n-1,'a')+"b"+std::string(n,'a')).find(std::string(n,'a'))равно O(n^2) или хуже. Например. для n = 1 миллион на моем компьютере это занимает 21 секунду, но должно быть мгновенным (возможно, несколько миллисекунд). - person Don Hatch schedule 12.04.2020