Rendimiento std :: strstr vs std :: string :: encontrar

Question

Duplicar posible:
C++ string::find complexity

Recientemente he descubierto, que la función std::string::find es un orden de magnitud más lento que la función std::strstr - en mi entorno con GCC 4.7 en Linux. La diferencia de rendimiento depende de la longitud de las cadenas y de la arquitectura del hardware.

Sin embargo, hay una razón simple para la diferencia: std::string::find básicamente llama a std::memcmp en un bucle - con complejidad de tiempo O(m * n). Por el contrario, std::strstr está altamente optimizado para la arquitectura de hardware (por ejemplo, con instrucciones SSE) y utiliza un algoritmo de coincidencia de cadenas más sofisticado (aparentemente Knuth-Morris-Pratt).

También me sorprendió no encontrar las complejidades de tiempo de estas dos funciones en los documentos de idioma (es decir, borradores N3290 y N1570). Solo he encontrado complejidades de tiempo para char_traits. Pero eso no ayuda, porque no hay función para la búsqueda de subcadenas en char_traits.

Supongo que std::strstr y memmem contienen optimizaciones similares con un rendimiento casi idéntico. Y hasta hace poco, asumí que std::string::find usa internamente el memmem.

Las preguntas son: ¿Hay alguna buena razón, ¿por qué std::string::find no utiliza std::memmem? ¿Y esto es diferente con otra implementación?

La pregunta no es: ¿Cuál es la mejor implementación de esta función? Es realmente difícil argumentar a favor de C++, si es más lento que C. No me importaría si ambas implementaciones fueran lentas. Es la diferencia de rendimiento lo que realmente duele.

Answer 1

Primero, ¿qué es memmem? No puedo encontrar esto en el estándar C++ ni en el estándar Posix (que contiene todas las funciones C estándar).

En segundo lugar, cualquier valor de medición dependerá de los datos reales. Usar KMP, por ejemplo, será una pesimista en muchos casos; probablemente la mayoría de los casos donde se usan las funciones miembro de std::string; el tiempo para configurar las tablas necesarias a menudo será más que el tiempo total del algoritmo directo. Cosas como O(m*n) no significan mucho cuando la longitud típica de la cuerda es corta.