Эффективные способы дублировать массив / список в Python
Примечание: я разработчик Ruby и пытаюсь найти свой путь в Python.
Когда я хотел выяснить, почему некоторые скрипты используют mylist[:] вместо list(mylist) чтобы дублировать списки, я сделал быстрый тест различных методов для дублирования range(10) (см. код ниже).
РЕДАКТИРОВАТЬ: я обновил тесты, чтобы использовать Python timeit как предложено ниже. Это делает невозможным прямое сравнение с Ruby, потому что timeit не учитывает циклы, а Ruby 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 ответа
Использовать 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
Я не могу комментировать время рубина против времени питона. Но я могу прокомментировать 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 найти функцию list, Поиск глобальных (и вызывающих функций) в python относительно медленный. Это объясняет, почему a[0:len(a)] также медленнее. Также помните, что list должен уметь обрабатывать произвольные итераторы, а срезы - нет. Это означает, что list Нужно выделить новый список, упаковать элементы в этот список, поскольку он перебирает список, и при необходимости изменять его размер. Здесь есть несколько вещей, которые стоят дорого - изменение размера при необходимости и итерация (эффективно в python, а не в C). С помощью метода нарезки вы можете рассчитать размер памяти, который вам нужен, поэтому, возможно, сможете избежать изменения размера, и итерация может быть полностью выполнена в C (возможно, с memcpy или что-то.
Отказ от ответственности: я не разработчик Python, поэтому я не знаю, как внутренние list() реализованы наверняка. Я просто размышляю, основываясь на том, что я знаю о спецификации.
РЕДАКТИРОВАТЬ - Итак, я посмотрел на источник (с небольшим руководством от 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 (строка 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