С++ string:: найти сложность

Ответ 1

Почему реализованная в С++ строка:: substr() не использует алгоритм KMP (и не работает в O (N + M)) и работает в O (N * M)?

Я предполагаю, что вы имеете в виду find(), а не substr(), который не нужно искать и должен выполняться в линейном времени (и только потому, что он должен скопировать результат в новую строку).

В стандарте С++ не указаны детали реализации, а в некоторых случаях задаются только требования к сложности. Единственными сложными требованиями к операциям std::string являются: size(), max_size(), operator[], swap(), c_str() и data() все постоянное время. Сложность любого другого зависит от выбора, сделанного тем, кто реализовал используемую вами библиотеку.

Наиболее вероятной причиной выбора простого поиска над чем-то вроде KMP является отсутствие необходимости в дополнительном хранилище. Если строка, которая будет найдена, очень длинная, и строка для поиска содержит много частичных совпадений, время, затраченное на выделение и освобождение, вероятно, будет намного больше, чем стоимость дополнительной сложности.

Исправлено ли в С++ 0x?

Нет, С++ 11 не добавляет требований сложности к std::string и, конечно же, не добавляет никаких обязательных деталей реализации.

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

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

Ответ 2

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

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

Ответ 3

FYI, Строка:: find в gcc/libstdС++ и llvm/libcxx была очень медленной. В некоторых случаях он значительно улучшился в 20 раз. Вы можете проверить новую реализацию:

GCC: PR66414 оптимизировать std::string:: найти https://github.com/gcc-mirror/gcc/commit/fc7ebc4b8d9ad7e2891b7f72152e8a2b7543cd65

LLVM: https://reviews.llvm.org/D27068

Ответ 4

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

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

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

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

Ответ 5

Посмотрите на книгу 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. □

Ответ 6

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

Ответ 7

Если вы собираетесь искать один и тот же шаблон в нескольких текстах. Алгоритм BoyerMoore является хорошим выбором, потому что таблицы шаблонов должны быть вычислены только один раз, но используются несколько раз при поиске нескольких текстов. Если вы собираетесь искать шаблон только один раз в одном тексте, то издержки на вычисление таблиц вместе с накладными расходами на выделение памяти замедляют вас слишком сильно, и std::string.find(....) побьет вас поскольку он не выделяет никакой памяти и не имеет накладных расходов. Boost имеет несколько алгоритмов поиска строк. Я обнаружил, что BM при поиске по одному шаблону в 1 тексте на порядок медленнее, чем std::string.find(). В моих случаях BoyerMoore редко был быстрее, чем std::string.find(), даже при поиске нескольких текстов с одинаковым шаблоном. Вот ссылка на BoyerMoore BoyerMoore