C ++ cadena :: encontrar complejidad

¿Por qué la string::find() implementada de c ++ string::find() no usa el algoritmo KMP (y no se ejecuta en O(N + M) ) y se ejecuta en O(N * M) ? ¿Eso está corregido en C ++ 0x? Si la complejidad del hallazgo actual no es O(N * M) , ¿qué es eso?

PD: lo siento, me refiero a string::find()

Entonces, ¿qué algoritmo se implementa en gcc? es ese KMP? si no, ¿por qué? Lo probé y el tiempo de ejecución muestra que se ejecuta en O(N * M)

¿Por qué la cadena implementada de c ++ :: substr () no utiliza el algoritmo KMP (y no se ejecuta en O (N + M)) y se ejecuta en O (N * M)?

Supongo que te refieres a find() , en lugar de substr() que no necesita buscar y debe ejecutarse en tiempo lineal (y solo porque tiene que copiar el resultado en una nueva cadena).

El estándar de C ++ no especifica los detalles de implementación, y solo especifica los requisitos de complejidad en algunos casos. Los únicos requisitos de complejidad en std::string operaciones std::string son que size() , max_size() , operator[] , swap() , c_str() y data() son todos de tiempo constante. La complejidad de cualquier otra cosa depende de las elecciones realizadas por quien implementó la biblioteca que está utilizando.

La razón más probable para elegir una búsqueda simple sobre algo como KMP es evitar el almacenamiento adicional. A menos que la cadena que se va a encontrar sea muy larga y la cadena de búsqueda contenga muchas coincidencias parciales, el tiempo necesario para asignarlo y liberarlo probablemente sea mucho mayor que el costo de la complejidad adicional.

¿Eso está corregido en c ++ 0x?

No, C ++ 11 no agrega ningún requisito de complejidad a std::string , y ciertamente no agrega ningún detalle de implementación obligatorio.

Si la complejidad del substr actual no es O (N * M), ¿qué es eso?

Esa es la complejidad del peor caso, cuando la cadena de búsqueda contiene muchas coincidencias parciales largas. Si los caracteres tienen una distribución razonablemente uniforme, entonces la complejidad promedio estaría más cerca de O(N) . Entonces, al elegir un algoritmo con una mejor complejidad en el peor de los casos, es posible que los casos más típicos sean mucho más lentos.

¿De dónde sacas la impresión de que std::string::substr() no usa un algoritmo lineal? De hecho, ni siquiera puedo imaginarme cómo implementar de una manera que tenga la complejidad que citaron. Además, no hay mucho algoritmo involucrado: ¿es posible que piense que esta función hace algo más de lo que lo hace? std::string::substr() solo crea una nueva cadena comenzando en su primer argumento y usando ya sea el número de caracteres especificado por el segundo parámetro o los caracteres hasta el final de la cadena.

Puede estar refiriéndose a std::string::find() que no tiene ningún requisito de complejidad o std::search() que de hecho tiene permitido hacer comparaciones O (n * m). Sin embargo, esto les da a los implementadores la libertad de elegir entre un algoritmo que tiene la mejor complejidad teórica vs. uno que no necesita memoria adicional. Dado que la asignación de cantidades arbitrarias de memoria generalmente no es deseable a menos que se solicite específicamente, parece una medida razonable.

FYI, la cadena :: find en gcc / libstdc ++ y llvm / libcxx fue muy lenta. Se ha mejorado significativamente en 20x en algunos casos. Es posible que desee verificar la nueva implementación:

GCC: PR66414 optimiza std :: string :: encuentra https://github.com/gcc-mirror/gcc/commit/fc7ebc4b8d9ad7e2891b7f72152e8a2b7543cd65

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

El estándar C ++ no dicta las características de rendimiento de substr (o muchas otras partes, incluido el find que probablemente se está refiriendo con una complejidad M*N ).

En general, dicta aspectos funcionales del lenguaje (con algunas excepciones como las funciones de sort no heredadas, por ejemplo).

Las implementaciones son incluso libres de implementar qsort como un tipo de burbuja (pero solo si quieren ser ridiculizados y posiblemente quiebren).

Por ejemplo, hay solo siete puntos (muy pequeños) en la sección 21.4.7.2 basic_string::find de C ++ 11, y ninguno de ellos especifica parámetros de rendimiento.

Echemos un vistazo al libro de CLRS. En la página 989 de la tercera edición tenemos el siguiente ejercicio:

Supongamos que el patrón P y el texto T son cadenas elegidas al azar de longitud myn, respectivamente, del alfabeto d-aria Σ d = {0; 1; …; d}, donde d> = 2. Demuestre que el número esperado de comparaciones carácter por carácter realizadas por el bucle implícito en la línea 4 del algoritmo ingenuo es enter image description here
sobre todas las ejecuciones de este ciclo. (Suponga que el algoritmo ingenuo deja de comparar caracteres para un turno dado una vez que encuentra un desajuste o coincide con el patrón completo.) Por lo tanto, para las cadenas elegidas al azar, el algoritmo ingenuo es bastante eficiente .

 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 

Prueba:

Para un solo turno, se espera que 1 + 1/d + ... + 1/d^{m-1} comparaciones 1 + 1/d + ... + 1/d^{m-1} . Ahora usa la fórmula de sum y multiplica por el número de cambios válidos, que es n - m + 1 . □

¿De dónde sacas tu información sobre la biblioteca C ++? Si quiere decir string::search y realmente no usa el algoritmo KMP, sugiero que es porque ese algoritmo no es generalmente más rápido que una simple búsqueda lineal debido a tener que construir una tabla de coincidencias parcial antes de que la búsqueda pueda proceder.