Производительность std::strstr и std::строка::найти [дубликат]

Здесь уже есть ответы на этот вопрос:

Закрыто 7 лет назад .

Возможный дубликат:
Строка C++::найти сложность

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

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

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

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

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

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

задан nosid 6 October 2018 в 09:17

0 ответов

Другие вопросы по тегам:

gcc stdstring strstr c++

Производительность std::strstr и std::строка::найти [дубликат]

0 ответов

Похожие вопросы: