Производительность станд :: strstr vs. станд :: строка :: найти

Question

Можно создать дубликат:
C++ string::find complexity

Недавно я узнал, что функция std::string::find является порядок медленнее чем функция std::strstr - в моей среде с GCC 4.7 на Linux. Разница в производительности зависит от длины строк и от аппаратной архитектуры.

Однако есть веская причина для разницы: std::string::find в основном вызывает std::memcmp в цикле - с временной сложностью O(m * n). Напротив, std::strstr высоко оптимизирован для архитектуры оборудования (например, с инструкциями SSE) и использует более сложный алгоритм сопоставления строк (по-видимому, Knuth-Morris-Pratt).

Я также был удивлен, когда не нашел сложностей во времени этих двух функций в языковых документах (т. Е. Чертежах N3290 и N1570). Я только нашел временные сложности для char_traits. Но это не помогает, потому что нет функции для поиска подстроки в char_traits.

Я бы ожидал, что std::strstr и memmem содержат аналогичные оптимизации с почти одинаковой производительностью. И до недавнего времени я предполагал, что std::string::find использует memmem внутренне.

Вопросов: Есть ли хорошая причина, почему std::string::find не использует std::memmem? И отличается ли это от другой реализации?

Вопрос не в следующем: Какова наилучшая реализация этой функции? На C++ действительно сложно спорить, если он медленнее C. Я бы не имел значения, будут ли обе реализации медленными. Это разница в производительности, которая действительно болит.

Answer 1

Во-первых, что такое memmem? Я не могу найти это в стандарте C++, а также в стандарте Posix (который содержит все стандартные функции C).

Во-вторых, любые значения измерений будут зависеть от фактических данных. Использование КМП, например, будет пессимизировать во многих случаях; вероятно, в большинстве случаев, когда используются функции-члены от std::string; время для установки необходимых таблиц часто будет больше, чем общее время алгоритма прямого доступа. Такие вещи, как O(m*n) , не имеют большого значения, когда типичная длина строки коротка.