C ++ строка :: найти сложность

Question

Почему реализованный в C ++ string::find() не использует алгоритм KMP (и не работает в O(N + M)) и работает в O(N * M)? Это исправлено в C ++ 0x? Если сложность текущей находки не O(N * M), что это?

PS: Извините, я имею в виду string::find()

так какой алгоритм реализован в gcc? это КМП? если нет, то почему? Я проверил это, и время выполнения показывает, что оно работает в O(N * M)

Answer 1

Почему реализованная в C ++ функция 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 и, конечно, не добавляет никаких обязательных подробностей реализации.

Если сложность текущего substr не O (N * M), что это?

Это сложность наихудшего случая, когда искомая строка содержитмного длинных частичных совпадений.Если символы имеют достаточно равномерное распределение, то средняя сложность будет ближе к O(N).Поэтому, выбирая алгоритм с лучшей сложностью в худшем случае, вы можете сделать более типичные случаи намного медленнее.

Answer 2

Откуда у вас впечатление, что std::string::substr() не использует линейный алгоритм?На самом деле, я даже не представляю, как реализовать это так, как вы сказали.Кроме того, здесь не так много задействованного алгоритма: возможно ли, что вы думаете, что эта функция делает что-то еще, чем делает?std::string::substr() просто создает новую строку, начиная с первого аргумента и используя либо количество символов, указанное вторым параметром, либо символы до конца строки.

Возможно, вы ссылаетесь на std::string::find()который не имеет каких-либо требований к сложности или std::search(), что действительно позволяет делать O (n * m) сравнений.Тем не менее, это дает разработчикам свободу выбора между алгоритмом, который имеет лучшую теоретическую сложность, и алгоритмом, который не требует дополнительной памяти.Поскольку выделение произвольных объемов памяти, как правило, нежелательно, если это не требуется, это кажется разумным.

Answer 3

FYI, Строка :: 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

Answer 4

Давайте посмотрим в книгу CLRS.На странице 989 третьего издания у нас есть следующее упражнение:

Предположим, что шаблон P и текст T являются случайно выбранными строками длиной m и n соответственно из алфавита-* 1004.* 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.□

Answer 5

Стандарт C ++ не определяет характеристики производительности substr (или многих других частей, включая find, на который вы, скорее всего, ссылаетесь со сложностью M*N).

В основном это диктует функциональные аспекты языка (за некоторыми исключениями, например, например, не унаследованные функции sort).

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

Например, в разделе 21.4.7.2 basic_string::find C ++ 11 есть только семь (очень маленьких) подпунктов, и нет из них задают параметры производительности.

Answer 6

Где вы получаете информацию о библиотеке C ++?Если вы имеете в виду string::search и он действительно не использует алгоритм KMP, то я полагаю, что это потому, что этот алгоритм обычно не быстрее простого линейного поиска из-за необходимости построения таблицы частичных соответствий, прежде чем поиск может быть продолжен.