Почему назначение slice быстрее, чем `list.insert`?

Вдохновленный этот хороший ответ,

Здесь контрольный показатель:

import timeit

def test1():
    a = [1,2,3]
    a.insert(0,1)

def test2():
    a = [1,2,3]
    a[0:0]=[1]

print (timeit.timeit('test1()','from __main__ import test1'))
print (timeit.timeit('test2()','from __main__ import test2'))

Для меня test2 работает слабее (~ 10%). Почему это так? Я ожидаю, что это будет медленнее, поскольку:

  • Назначение slice должно принимать итерации любой длины и поэтому должно быть более общим.
  • в назначении slice нам нужно создать новый список с правой стороны, чтобы заставить его работать.

Может кто-нибудь помочь мне понять это?

(используя python 2.7 на OS-X 10.5.8)

Ответы

Ответ 1

Ваш первый тестовый пример должен вызвать метод insert в списке a, тогда как все операции в test2 обрабатываются непосредственно в байтовом коде. Обратите внимание на CALL_FUNCTION при разборке test1 ниже. Функции вызова являются довольно дорогими в Python: конечно, достаточно дорого, чтобы учесть разницу в процентах от времени выполнения.

>>> import dis
>>> dis.dis(test1)
  2           0 LOAD_CONST               1 (1)
              3 LOAD_CONST               2 (2)
              6 LOAD_CONST               3 (3)
              9 BUILD_LIST               3
             12 STORE_FAST               0 (a)

  3          15 LOAD_FAST                0 (a)
             18 LOAD_ATTR                0 (insert)
             21 LOAD_CONST               4 (0)
             24 LOAD_CONST               1 (1)
             27 CALL_FUNCTION            2
             30 POP_TOP             
             31 LOAD_CONST               0 (None)
             34 RETURN_VALUE        
>>> dis.dis(test2)
  2           0 LOAD_CONST               1 (1)
              3 LOAD_CONST               2 (2)
              6 LOAD_CONST               3 (3)
              9 BUILD_LIST               3
             12 STORE_FAST               0 (a)

  3          15 LOAD_CONST               1 (1)
             18 BUILD_LIST               1
             21 LOAD_FAST                0 (a)
             24 LOAD_CONST               4 (0)
             27 LOAD_CONST               4 (0)
             30 STORE_SLICE+3       
             31 LOAD_CONST               0 (None)
             34 RETURN_VALUE

Плохая информация

Я разместил это первым, но после рассмотрения думаю, что это неверно. Разница, которую я здесь описываю, должна только иметь заметную разницу, когда есть много данных, которые нужно переместить, что здесь не так. И даже при большом количестве данных разница составляет всего пару процентов:

import timeit

def test1():
    a = range(10000000)
    a.insert(1,1)

def test2():
    a = range(10000000)
    a[1:1]=[1]

>>> timeit.timeit(test1, number=10)
6.008707046508789
>>> timeit.timeit(test2, number=10)
5.861173868179321

Метод list.insert реализуется функцией ins1 в listobject.c. Вы увидите, что он копирует ссылки на элементы для хвоста списка один за другим:

for (i = n; --i >= where; )
    items[i+1] = items[i];

С другой стороны, назначение slice реализуется функцией list_ass_slice, которая вызывает memmove:

memmove(&item[ihigh+d], &item[ihigh],
        (k - ihigh)*sizeof(PyObject *));

Итак, я думаю, что ответ на ваш вопрос заключается в том, что функция библиотеки C memmove лучше оптимизирована, чем простой цикл. См. здесь для реализации glibc memmove: я считаю, что при вызове из list_ass_slice он в конечном итоге заканчивает вызов _wordcopy_bwd_aligned, который вы видите, сильно оптимизирован вручную.