python - endswith - startswith java

¿Por qué comienza con más lento que rebanar

Question

¿Por qué la implementación de startwith más lenta que slicing?

In [1]: x = ''foobar''

In [2]: y = ''foo''

In [3]: %timeit x.startswith(y)
1000000 loops, best of 3: 321 ns per loop

In [4]: %timeit x[:3] == y
10000000 loops, best of 3: 164 ns per loop

Sorprendentemente, incluso incluyendo el cálculo de la longitud, el corte sigue siendo significativamente más rápido:

In [5]: %timeit x[:len(y)] == y
1000000 loops, best of 3: 251 ns per loop

Nota: la primera parte de este comportamiento se menciona en Python for Data Analysis (Capítulo 3), pero no se ofrece ninguna explicación.

.

Si es útil: aquí está el código C para startswith ; y aquí está la salida de dis.dis :

In [6]: import dis

In [7]: dis_it = lambda x: dis.dis(compile(x, ''<none>'', ''eval''))

In [8]: dis_it(''x[:3]==y'')
  1           0 LOAD_NAME                0 (x)
              3 LOAD_CONST               0 (3)
              6 SLICE+2             
              7 LOAD_NAME                1 (y)
             10 COMPARE_OP               2 (==)
             13 RETURN_VALUE        

In [9]: dis_it(''x.startswith(y)'')
  1           0 LOAD_NAME                0 (x)
              3 LOAD_ATTR                1 (startswith)
              6 LOAD_NAME                2 (y)
              9 CALL_FUNCTION            1
             12 RETURN_VALUE 

Answer 1

La comparación no es justa ya que solo está midiendo el caso donde startswith devuelve True .

>>> x = ''foobar''
>>> y = ''fool''
>>> %timeit x.startswith(y)
1000000 loops, best of 3: 221 ns per loop
>>> %timeit x[:3] == y  # note: length mismatch
10000000 loops, best of 3: 122 ns per loop
>>> %timeit x[:4] == y
10000000 loops, best of 3: 158 ns per loop
>>> %timeit x[:len(y)] == y
1000000 loops, best of 3: 210 ns per loop
>>> sw = x.startswith
>>> %timeit sw(y)
10000000 loops, best of 3: 176 ns per loop

Además, para cadenas mucho más largas, el startswith es mucho más rápido:

>>> import random
>>> import string
>>> x = ''%030x'' % random.randrange(256**10000)
>>> len(x)
20000
>>> y = r[:4000]
>>> %timeit x.startswith(y)
1000000 loops, best of 3: 211 ns per loop
>>> %timeit x[:len(y)] == y
1000000 loops, best of 3: 469 ns per loop
>>> sw = x.startswith
>>> %timeit sw(y)
10000000 loops, best of 3: 168 ns per loop

Esto sigue siendo cierto cuando no hay coincidencia.

# change last character of y
>>> y = y[:-1] + chr((ord(y[-1]) + 1) % 256)
>>> %timeit x.startswith(y)
1000000 loops, best of 3: 210 ns per loop
>>> %timeit x[:len(y)] == y
1000000 loops, best of 3: 470 ns per loop
>>> %timeit sw(y)
10000000 loops, best of 3: 168 ns per loop
# change first character of y
>>> y = chr((ord(y[0]) + 1) % 256) + y[1:]
>>> %timeit x.startswith(y)
1000000 loops, best of 3: 210 ns per loop
>>> %timeit x[:len(y)] == y
1000000 loops, best of 3: 442 ns per loop
>>> %timeit sw(y)
10000000 loops, best of 3: 168 ns per loop

Por lo tanto, startswith es probablemente más lento para cadenas cortas porque está optimizado para largas.

(Truco para obtener secuencias aleatorias de esta respuesta ).

Answer 2

Llamar a una función es bastante caro. No sé, sin embargo, si este es el caso también para las funciones incorporadas escritas en C.

Tenga en cuenta, sin embargo, que el corte puede implicar una llamada de función también dependiendo del objeto que se utiliza.

Answer 3

Para citar startwith , startswith más startswith que podrías pensar:

str.startswith(prefix[, start[, end]])

Devuelve True si la cadena comienza con el prefijo; de lo contrario, devuelve False . prefijo también puede ser una tupla de prefijos para buscar. Con inicio opcional, la cadena de prueba comienza en esa posición. Con un final opcional, deja de comparar la secuencia en esa posición.

Answer 4

startswith es más complejo que cortar ...

2924 result = _string_tailmatch(self,
2925 PyTuple_GET_ITEM(subobj, i),
2926 start, end, -1);

Este no es un ciclo simple de comparación de caracteres para la aguja en el inicio del pajar que está sucediendo. Estamos viendo un bucle for que itera a través de un vector / tuple (subobj) y llama a otra función ( _string_tailmatch ). Las llamadas a múltiples funciones tienen sobrecarga con respecto a la pila, verificaciones de cordura de argumento, etc.

startswith es una función de biblioteca mientras que el corte parece estar integrado en el lenguaje.

2919 if (!stringlib_parse_args_finds("startswith", args, &subobj, &start, &end))
2920 return NULL;

Answer 5

Algunas de las diferencias de rendimiento se pueden explicar teniendo en cuenta el tiempo que lleva . operador para hacer su cosa:

>>> x = ''foobar''
>>> y = ''foo''
>>> sw = x.startswith
>>> %timeit x.startswith(y)
1000000 loops, best of 3: 316 ns per loop
>>> %timeit sw(y)
1000000 loops, best of 3: 267 ns per loop
>>> %timeit x[:3] == y
10000000 loops, best of 3: 151 ns per loop

Otra parte de la diferencia puede explicarse por el hecho de que el startswith es una función , e incluso las llamadas a la función no operativa tardan un poco:

>>> def f():
...     pass
... 
>>> %timeit f()
10000000 loops, best of 3: 105 ns per loop

Esto no explica por completo la diferencia, ya que la versión que utiliza slicing y len llama a una función y es aún más rápida (en comparación con sw(y) anterior - 267 ns):

>>> %timeit x[:len(y)] == y
1000000 loops, best of 3: 213 ns per loop

Mi única conjetura aquí es que quizás Python optimiza el tiempo de búsqueda para las funciones incorporadas, o que las llamadas len están muy optimizadas (lo cual es probablemente cierto). Podría ser posible probar eso con un func len personalizado. O posiblemente sea aquí donde LastCoder las diferencias identificadas por LastCoder . Tenga en cuenta también los resultados de larsmans , que indican que el startswith es realmente más rápido para cadenas más largas. Toda la línea de razonamiento anterior se aplica solo a aquellos casos en los que los gastos generales de los que estoy hablando realmente importan.