¿Cuál es la gran O de la siguiente if statement ?
if "pl" in "apple": ...
¿Cuál es la O grande general de cómo Python determina si la cadena “pl” se encuentra en la cadena “Apple”?
o cualquier otra subcadena en búsqueda de cadenas.
¿Es esta la forma más eficiente de probar si una subcadena está en una cadena? ¿Utiliza el mismo algoritmo que .find() ?
En Python 3.4.2 parece que están recurriendo a la misma función, pero no obstante, puede haber diferencias en el tiempo. Por ejemplo, se s.find primero buscar el método de búsqueda de la cadena y tal.
El algoritmo utilizado es una mezcla entre Boyer-More y Horspool.
La complejidad del tiempo es O (N) en promedio, O (NM) en el peor de los casos (N es la longitud de la cadena más larga, M, la cadena más corta que busca).
El mismo algoritmo se usa para str.index() , str.find() , str.__contains__() (el operador in ) y str.replace() ; es una simplificación de Boyer-Moore con ideas tomadas de los algoritmos de Boyer-Moore-Horspool y Sunday .
Consulte la publicación original de discusión de stringlib , así como el código fuente de fastsearch.h ; el algoritmo base no ha cambiado desde la introducción en Python 2.5 (aparte de algunas optimizaciones de bajo nivel y correcciones de caso de esquina ).
La publicación incluye un esquema del código Python del algoritmo:
def find(s, p): # find first occurrence of p in s n = len(s) m = len(p) skip = delta1(p)[p[m-1]] i = 0 while i <= nm: if s[i+m-1] == p[m-1]: # (boyer-moore) # potential match if s[i:i+m-1] == p[:m-1]: return i if s[i+m] not in p: i = i + m + 1 # (sunday) else: i = i + skip # (horspool) else: # skip if s[i+m] not in p: i = i + m + 1 # (sunday) else: i = i + 1 return -1 # not found
así como comparaciones de velocidad.
Puedes usar timeit y probarlo tú mismo:
maroun@DQHCPY1:~$ python -m timeit 's = "apple";s.find("pl")' 10000000 loops, best of 3: 0.125 usec per loop maroun@DQHCPY1:~$ python -m timeit 's = "apple";"pl" in s' 10000000 loops, best of 3: 0.0371 usec per loop
El uso in es realmente más rápido (0.0371 usec comparado con 0.125 usec).
Para la implementación real, puede mirar el código en sí .
Creo que la mejor manera de averiguarlo es mirar la fuente. Esto parece que implementaría __contains__ :
static int bytes_contains(PyObject *self, PyObject *arg) { Py_ssize_t ival = PyNumber_AsSsize_t(arg, PyExc_ValueError); if (ival == -1 && PyErr_Occurred()) { Py_buffer varg; Py_ssize_t pos; PyErr_Clear(); if (PyObject_GetBuffer(arg, &varg, PyBUF_SIMPLE) != 0) return -1; pos = stringlib_find(PyBytes_AS_STRING(self), Py_SIZE(self), varg.buf, varg.len, 0); PyBuffer_Release(&varg); return pos >= 0; } if (ival < 0 || ival >= 256) { PyErr_SetString(PyExc_ValueError, "byte must be in range(0, 256)"); return -1; } return memchr(PyBytes_AS_STRING(self), (int) ival, Py_SIZE(self)) != NULL; }
en términos de stringlib_find() , que usa fastsearch() .