Эффективные способы дублирования массива / списка в Python

Примечание. Я разработчик Ruby, пытающийся найти свой путь в Python.

Когда я хотел выяснить, почему некоторые скрипты используют mylist[:] вместо list(mylist) для дублирования списков, я сделал быстрый тест различных методов дублирования range(10) (см. Код ниже).

EDIT: Я обновил тесты, чтобы использовать timeit Python, как предлагается ниже. Это делает невозможным прямое сравнение с Ruby, потому что timeit не учитывает цикл, пока работает Ruby's Benchmark , поэтому код Ruby используется только для справки .

Python 2.7.2

 Array duplicating. Tests run 50000000 times list(a) 18.7599430084 copy(a) 59.1787488461 a[:] 9.58828091621 a[0:len(a)] 14.9832749367 

Для справки я написал тот же скрипт в Ruby:

Ruby 1.9.2p0

 Array duplicating. Tests 50000000 times user system total real Array.new(a) 14.590000 0.030000 14.620000 ( 14.693033) Array[*a] 18.840000 0.060000 18.900000 ( 19.156352) a.take(a.size) 8.780000 0.020000 8.800000 ( 8.805700) a.clone 16.310000 0.040000 16.350000 ( 16.384711) a[0,a.size] 8.950000 0.020000 8.970000 ( 8.990514) 

Вопрос 1: что такое mylist[:] делает по-другому, что он на 25% быстрее, чем даже mylist[0:len(mylist)] . Копирует ли он в памяти напрямую или что?

Вопрос 2: изменить: обновленные тесты больше не показывают больших различий в Python и Ruby. было: Я реализовал тесты некоторым явно неэффективным способом, так что код Ruby намного быстрее, чем Python?

Теперь списки кодов:

Python:

 import timeit COUNT = 50000000 print "Array duplicating. Tests run", COUNT, "times" setup = 'a = range(10); import copy' print "list(a)\t\t", timeit.timeit(stmt='list(a)', setup=setup, number=COUNT) print "copy(a)\t\t", timeit.timeit(stmt='copy.copy(a)', setup=setup, number=COUNT) print "a[:]\t\t", timeit.timeit(stmt='a[:]', setup=setup, number=COUNT) print "a[0:len(a)]\t", timeit.timeit(stmt='a[0:len(a)]', setup=setup, number=COUNT) 

Рубин:

 require 'benchmark' a = (0...10).to_a COUNT = 50_000_000 puts "Array duplicating. Tests #{COUNT} times" Benchmark.bm(16) do |x| x.report("Array.new(a)") {COUNT.times{ Array.new(a) }} x.report("Array[*a]") {COUNT.times{ Array[*a] }} x.report("a.take(a.size)") {COUNT.times{ a.take(a.size) }} x.report("a.clone") {COUNT.times{ a.clone }} x.report("a[0,a.size]"){COUNT.times{ a[0,a.size] }} end 

    2 Solutions collect form web for “Эффективные способы дублирования массива / списка в Python”

    Используйте модуль timeit в python для тестирования таймингов.

     from copy import * a=range(1000) def cop(): b=copy(a) def func1(): b=list(a) def slice(): b=a[:] def slice_len(): b=a[0:len(a)] if __name__=="__main__": import timeit print "copy(a)",timeit.timeit("cop()", setup="from __main__ import cop") print "list(a)",timeit.timeit("func1()", setup="from __main__ import func1") print "a[:]",timeit.timeit("slice()", setup="from __main__ import slice") print "a[0:len(a)]",timeit.timeit("slice_len()", setup="from __main__ import slice_len") 

    Результаты:

     copy(a) 3.98940896988 list(a) 2.54542589188 a[:] 1.96630120277 #winner a[0:len(a)] 10.5431251526 

    Разумеется, дополнительные шаги, связанные a[0:len(a)] являются причиной медленности.

    Вот сравнение байтового кода двух:

     In [19]: dis.dis(func1) 2 0 LOAD_GLOBAL 0 (range) 3 LOAD_CONST 1 (100000) 6 CALL_FUNCTION 1 9 STORE_FAST 0 (a) 3 12 LOAD_FAST 0 (a) 15 SLICE+0 16 STORE_FAST 1 (b) 19 LOAD_CONST 0 (None) 22 RETURN_VALUE In [20]: dis.dis(func2) 2 0 LOAD_GLOBAL 0 (range) 3 LOAD_CONST 1 (100000) 6 CALL_FUNCTION 1 9 STORE_FAST 0 (a) 3 12 LOAD_FAST 0 (a) #same up to here 15 LOAD_CONST 2 (0) #loads 0 18 LOAD_GLOBAL 1 (len) # loads the builtin len(), # so it might take some lookup time 21 LOAD_FAST 0 (a) 24 CALL_FUNCTION 1 27 SLICE+3 28 STORE_FAST 1 (b) 31 LOAD_CONST 0 (None) 34 RETURN_VALUE 

    Я не могу прокомментировать время рубина по сравнению с таймером python. Но я могу прокомментировать list против slice . Вот быстрая проверка байткода:

     >>> import dis >>> a = range(10) >>> def func(a): ... return a[:] ... >>> def func2(a): ... return list(a) ... >>> dis.dis(func) 2 0 LOAD_FAST 0 (a) 3 SLICE+0 4 RETURN_VALUE >>> dis.dis(func2) 2 0 LOAD_GLOBAL 0 (list) 3 LOAD_FAST 0 (a) 6 CALL_FUNCTION 1 9 RETURN_VALUE 

    Обратите внимание, что для list требуется LOAD_GLOBAL . Глянг-глобулы (и вызывающие функции) в python относительно медленны. Это объясняет, почему a[0:len(a)] также медленнее. Также помните, что list должен иметь возможность обрабатывать произвольные итераторы, тогда как нарезка – нет. Это означает, что list должен выделять новый список, вставлять элементы в этот список, когда он выполняет итерацию по списку и при необходимости изменяет размер. Здесь есть несколько вещей, которые являются дорогостоящими – при необходимости изменяя размер и итерируя (эффективно в python, а не в C). С помощью метода нарезки вы можете рассчитать размер памяти, который вам понадобится, поэтому возможно избежать изменения размера, и итерация может быть выполнена полностью на C (возможно, с memcpy или что-то еще.

    отказ от ответственности : я не разработчик python, поэтому я не знаю, как реализованы внутренние функции list() . Я просто размышляю о том, что знаю о спецификации.

    EDIT – Итак, я посмотрел на источник (с небольшим руководством от Martijn). Соответствующий код находится в listobject.c . list вызывает list_init который затем вызывает listextend в строке 799. Эта функция имеет некоторые проверки, чтобы увидеть, может ли она использовать ветвь быстрого доступа, если объект является списком или кортежем (строка 812). Наконец, тяжелый подъем выполняется с линии 834:

      src = PySequence_Fast_ITEMS(b); dest = self->ob_item + m; for (i = 0; i < n; i++) { PyObject *o = src[i]; Py_INCREF(o); dest[i] = o; } 

    Сравните это со list_subscript версией, которая, как мне кажется, определена в list_subscript (строка 2544). Это вызывает list_slice (строка 2570), где тяжелый подъем выполняется следующим циклом (строка 486):

      src = a->ob_item + ilow; dest = np->ob_item; for (i = 0; i < len; i++) { PyObject *v = src[i]; Py_INCREF(v); dest[i] = v; } 

    Это почти тот же код, поэтому неудивительно, что производительность почти одинакова для больших списков (где накладные расходы на мелкие вещи, такие как распаковка срезов, поиск глобальных переменных и т. Д., Становятся менее важными)


    Вот как я буду запускать тесты python (и результаты для моей системы Ubuntu):

     $ python -m timeit -s 'a=range(30)' 'list(a)' 1000000 loops, best of 3: 0.39 usec per loop $ python -m timeit -s 'a=range(30)' 'a[:]' 10000000 loops, best of 3: 0.183 usec per loop $ python -m timeit -s 'a=range(30)' 'a[0:len(a)]' 1000000 loops, best of 3: 0.254 usec per loop 
    Python - лучший язык программирования в мире.