Dlaczego łańcuchy zaczynają wolniej niż w?

Question

Niespodziewanie, znajdę startswith jest wolniejszy niż in:

In [10]: s="ABCD"*10 

In [11]: %timeit s.startswith("XYZ") 
1000000 loops, best of 3: 307 ns per loop 

In [12]: %timeit "XYZ" in s 
10000000 loops, best of 3: 81.7 ns per loop 

Jak wszyscy wiemy, operacja in musi przeszukać cały ciąg i startswith musi tylko sprawdzić kilka pierwszych znaków, więc startswith powinien być bardziej wydajny .

Kiedy s jest wystarczająco duża, startswith jest szybsze:

In [13]: s="ABCD"*200 

In [14]: %timeit s.startswith("XYZ") 
1000000 loops, best of 3: 306 ns per loop 

In [15]: %timeit "XYZ" in s 
1000000 loops, best of 3: 666 ns per loop 

Więc wydaje się, że dzwoni startswith ma pewne obciążenie co sprawia, że ​​wolniej, gdy ciąg jest niewielka.

A potem próbowałem dowiedzieć się, jaki jest koszt połączenia startswith.

Najpierw użyłem zmiennej f do zmniejszenia kosztów eksploatacji kropka - jak wspomniano w tym answer - tutaj widzimy startswith jest jeszcze wolniej:

In [16]: f=s.startswith 

In [17]: %timeit f("XYZ") 
1000000 loops, best of 3: 270 ns per loop 

Ponadto testowałem kosztu puste wywołanie funkcji:

In [18]: def func(a): pass 

In [19]: %timeit func("XYZ") 
10000000 loops, best of 3: 106 ns per loop 

względu na koszty eksploatacji kropka i działanie połączenia czas startswith wynosi (270-106) = 164ns, ale tak in operacji es tylko 81,7ns. Wygląda na to, że nadal istnieją pewne koszty ogólne związane z startswith, co to jest?

Dodaj wynik testu między startswith i __contains__ jak sugeruje worku i LVC:

In [28]: %timeit s.startswith("XYZ") 
1000000 loops, best of 3: 314 ns per loop 

In [29]: %timeit s.__contains__("XYZ") 
1000000 loops, best of 3: 192 ns per loop 

Answer 1

Jak już wspomniano w komentarzach, jeśli korzystasz z s.__contains__("XYZ"), otrzymasz wynik bardziej podobny do s.startswith("XYZ"), ponieważ musi on przyjąć tę samą trasę: Wyszukiwanie członka na obiekcie ciągu, a następnie wywołanie funkcji. Zwykle jest to dość kosztowne (nie na tyle, że powinieneś się oczywiście martwić). Z drugiej strony, gdy wykonujesz "XYZ" in s, parser interpretuje operatora i może skrócić dostęp członka do __contains__ (lub raczej za jego implementacją, ponieważ sama __contains__ jest tylko jednym ze sposobów uzyskania dostępu do implementacji).

można zorientować się o tym patrząc na kod bajtowy:

>>> dis.dis('"XYZ" in s') 
    1   0 LOAD_CONST    0 ('XYZ') 
       3 LOAD_NAME    0 (s) 
       6 COMPARE_OP    6 (in) 
       9 RETURN_VALUE 
>>> dis.dis('s.__contains__("XYZ")') 
    1   0 LOAD_NAME    0 (s) 
       3 LOAD_ATTR    1 (__contains__) 
       6 LOAD_CONST    0 ('XYZ') 
       9 CALL_FUNCTION   1 (1 positional, 0 keyword pair) 
      12 RETURN_VALUE 

Więc porównując s.__contains__("XYZ") z s.startswith("XYZ") będzie produkować więcej podobny wynik, jednak za przykład ciąg s The startswith nadal będzie wolniejszy.

Aby to zrobić, możesz sprawdzić implementację obu.Interesujące, aby zobaczyć na contains implementation jest to, że jest statycznie wpisane, i po prostu zakłada, że ​​argument jest sam obiekt Unicode. Jest to dość efektywne.

Jednak jest to "dynamiczna" metoda Pythona, która wymaga implementacji do rzeczywistego przeanalizowania argumentów. startswith obsługuje również krotki jako argument, który sprawia, że ​​cały rozruch metody nieco wolniejszym: (skrócenie przeze mnie, z moich komentarzach):

static PyObject * unicode_startswith(PyObject *self, PyObject *args) 
{ 
    // argument parsing 
    PyObject *subobj; 
    PyObject *substring; 
    Py_ssize_t start = 0; 
    Py_ssize_t end = PY_SSIZE_T_MAX; 
    int result; 
    if (!stringlib_parse_args_finds("startswith", args, &subobj, &start, &end)) 
     return NULL; 

    // tuple handling 
    if (PyTuple_Check(subobj)) {} 

    // unicode conversion 
    substring = PyUnicode_FromObject(subobj); 
    if (substring == NULL) {} 

    // actual implementation 
    result = tailmatch(self, substring, start, end, -1); 
    Py_DECREF(substring); 
    if (result == -1) 
     return NULL; 
    return PyBool_FromLong(result); 
} 

to prawdopodobnie duży powód startswith jest wolniejszy dla ciągów, dla których contains jest szybki ze względu na swoją prostotę.

Answer 2

Jest to prawdopodobne, ponieważ str.startswith() nie więcej niż str.__contains__(), a także dlatego, że wierzę str.__contains__ pełni działa w C, natomiast str.startswith() ma do interakcji z typami Pythona. Jego sygnaturą jest str.startswith(prefix[, start[, end]]), gdzie prefiks może być krotką ciągów znaków do wypróbowania.