Копирование перемешанного range(10**6)списка десять раз занимает у меня около 0,18 секунды: (это пять запусков)
0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451
Копирование не перемешанного списка десять раз занимает около 0,05 секунды:
0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184
Вот мой тестовый код:
from timeit import timeit
import random
a = range(10**6)
random.shuffle(a) # Remove this for the second test.
a = list(a) # Just an attempt to "normalize" the list.
for _ in range(5):
print timeit(lambda: list(a), number=10)
Я также пробовал копировать a[:], результаты были похожи (т.е. большая разница в скорости)
Почему большая разница в скорости? Я знаю и понимаю разницу в скорости в знаменитом " Почему быстрее обрабатывать отсортированный массив, чем несортированный?" пример, но здесь у моей обработки нет решений. Это просто слепое копирование ссылок внутри списка, не так ли?
Я использую Python 2.7.12 в Windows 10.
Изменить: пробовал Python 3.5.2, результаты были почти такими же (перетасовывались последовательно около 0,17 секунды, не перемешивались последовательно около 0,05 секунды). Вот код для этого:
a = list(range(10**6))
random.shuffle(a)
a = list(a)
for _ in range(5):
print(timeit(lambda: list(a), number=10))
источник
0.25на каждой итерации каждого из тестов. Так что на моей платформе порядок имеет значение.Ответы:
Интересно то, что это зависит от порядка, в котором целые числа создаются впервые . Например, вместо
shuffleсоздания случайной последовательности сrandom.randint:from timeit import timeit import random a = [random.randint(0, 10**6) for _ in range(10**6)] for _ in range(5): print(timeit(lambda: list(a), number=10))Это так же быстро, как копирование вашего
list(range(10**6))(первый и быстрый пример).Однако, когда вы перемешиваете - тогда ваши целые числа больше не находятся в том порядке, в котором они были впервые созданы, вот что делает его медленным.
Быстрое интермеццо:
Py_INCREFinlist_slice), поэтому Python действительно нужно перейти туда, где находится объект. Он не может просто скопировать ссылку.Итак, когда вы копируете свой список, вы получаете каждый элемент этого списка и помещаете его «как есть» в новый список. Когда ваш следующий элемент был создан вскоре после текущего, есть хороший шанс (без гарантии!), Что он будет сохранен рядом с ним в куче.
Предположим, что всякий раз, когда ваш компьютер загружает элемент в кеш, он также загружает
xследующие элементы в памяти (расположение кеша). Тогда ваш компьютер сможет увеличить счетчик ссылок дляx+1элементов в одном кэше!С перетасованной последовательностью он по-прежнему загружает следующие элементы в памяти, но это не те, которые находятся в списке. Таким образом, он не может выполнять приращение счетчика ссылок без «реального» поиска следующего элемента.
TL; DR: Фактическая скорость зависит от того, что произошло перед копированием: в каком порядке были созданы эти элементы и в каком порядке они находятся в списке.
Вы можете убедиться в этом, посмотрев на
id:a = list(range(10**6, 10**6+100)) for item in a: print(id(item))Просто чтобы показать небольшой отрывок:
1496489995888 1496489995920 # +32 1496489995952 # +32 1496489995984 # +32 1496489996016 # +32 1496489996048 # +32 1496489996080 # +32 1496489996112 1496489996144 1496489996176 1496489996208 1496489996240 1496507297840 1496507297872 1496507297904 1496507297936 1496507297968 1496507298000 1496507298032 1496507298064 1496507298096 1496507298128 1496507298160 1496507298192Так что эти объекты действительно находятся «рядом друг с другом в куче». С
shuffleними нет:import random a = list(range(10**6, 100+10**6)) random.shuffle(a) last = None for item in a: if last is not None: print('diff', id(item) - id(last)) last = itemЭто показывает, что они не совсем рядом друг с другом в памяти:
diff 736 diff -64 diff -17291008 diff -128 diff 288 diff -224 diff 17292032 diff -1312 diff 1088 diff -17292384 diff 17291072 diff 608 diff -17290848 diff 17289856 diff 928 diff -672 diff 864 diff -17290816 diff -128 diff -96 diff 17291552 diff -192 diff 96 diff -17291904 diff 17291680 diff -1152 diff 896 diff -17290528 diff 17290816 diff -992 diff 448Важная заметка:
Я сам этого не придумал. Большую часть информации можно найти в блоге Рики Стюарта .
Этот ответ основан на «официальной» реализации Python на CPython. Детали в других реализациях (Jython, PyPy, IronPython, ...) могут отличаться. Спасибо @ JörgWMittag за указание на это .
источник
list_sliceа в строке 453 вы можете увидетьPy_INCREF(v);вызов, который необходим для доступа к объекту, размещенному в куче.a = [0] * 10**7( вместо 10 ** 6, потому что это было слишком нестабильно), что даже быстрее, чем использованиеa = range(10**7)(примерно в 1,25 раза). Очевидно, потому что это даже лучше для кеширования.[0,1,2,3]*((10**6) // 4)так быстро, какa = [0] * 10**6. Однако с целыми числами от 0 до 255 возникает еще один факт: они интернированы, поэтому с ними порядок создания (внутри вашего скрипта) больше не важен - потому что они создаются при запуске python.Когда вы перетасовываете элементы списка, они имеют худшее местоположение ссылки, что приводит к ухудшению производительности кеша.
Вы можете подумать, что при копировании списка просто копируются ссылки, а не объекты, поэтому их расположение в куче не имеет значения. Тем не менее, копирование по-прежнему требует доступа к каждому объекту, чтобы изменить счетчик ссылок.
источник
Как объяснили другие, это не просто копирование ссылок, но также увеличивает счетчик ссылок внутри объектов, и, таким образом, к объектам осуществляется доступ, и кеш играет роль.
Здесь я просто хочу добавить больше экспериментов. Не так много о перетасованном и не перетасованном (где доступ к одному элементу может пропустить кеш, но получить следующие элементы в кеш, чтобы они попали). Но о повторяющихся элементах, когда последующие обращения к тому же элементу могут попасть в кеш, потому что элемент все еще находится в кеше.
Тестирование нормального диапазона:
>>> from timeit import timeit >>> a = range(10**7) >>> [timeit(lambda: list(a), number=100) for _ in range(3)] [5.1915339142808925, 5.1436351868889645, 5.18055115701749]Список того же размера, но с одним и тем же элементом, повторяющимся снова и снова, быстрее, потому что он все время попадает в кеш:
>>> a = [0] * 10**7 >>> [timeit(lambda: list(a), number=100) for _ in range(3)] [4.125743135926939, 4.128927210087596, 4.0941229388550795]И неважно, какой это номер:
>>> a = [1234567] * 10**7 >>> [timeit(lambda: list(a), number=100) for _ in range(3)] [4.124106479141709, 4.156590225249886, 4.219242600790949]Интересно, что это становится еще быстрее, когда я вместо этого повторяю те же два или четыре элемента:
>>> a = [0, 1] * (10**7 / 2) >>> [timeit(lambda: list(a), number=100) for _ in range(3)] [3.130586101607932, 3.1001001764957294, 3.1318465707127814] >>> a = [0, 1, 2, 3] * (10**7 / 4) >>> [timeit(lambda: list(a), number=100) for _ in range(3)] [3.096105435911994, 3.127148431279352, 3.132872673690855]Думаю, что-то не нравится, что один и тот же счетчик постоянно увеличивается. Может быть, какое-то срывание конвейера, потому что каждое увеличение должно ждать результата предыдущего увеличения, но это дикая догадка.
Во всяком случае, пробуя это для еще большего количества повторяющихся элементов:
from timeit import timeit for e in range(26): n = 2**e a = range(n) * (2**25 / n) times = [timeit(lambda: list(a), number=20) for _ in range(3)] print '%8d ' % n, ' '.join('%.3f' % t for t in times), ' => ', sum(times) / 3Результат (первый столбец - это количество различных элементов, для каждого я тестирую три раза, а затем беру среднее значение):
1 2.871 2.828 2.835 => 2.84446732686 2 2.144 2.097 2.157 => 2.13275338734 4 2.129 2.297 2.247 => 2.22436720645 8 2.151 2.174 2.170 => 2.16477771575 16 2.164 2.159 2.167 => 2.16328197911 32 2.102 2.117 2.154 => 2.12437970598 64 2.145 2.133 2.126 => 2.13462250728 128 2.135 2.122 2.137 => 2.13145065221 256 2.136 2.124 2.140 => 2.13336283943 512 2.140 2.188 2.179 => 2.1688431668 1024 2.162 2.158 2.167 => 2.16208440826 2048 2.207 2.176 2.213 => 2.19829998424 4096 2.180 2.196 2.202 => 2.19291917834 8192 2.173 2.215 2.188 => 2.19207065277 16384 2.258 2.232 2.249 => 2.24609975704 32768 2.262 2.251 2.274 => 2.26239771771 65536 2.298 2.264 2.246 => 2.26917420394 131072 2.285 2.266 2.313 => 2.28767871168 262144 2.351 2.333 2.366 => 2.35030805124 524288 2.932 2.816 2.834 => 2.86047313113 1048576 3.312 3.343 3.326 => 3.32721167007 2097152 3.461 3.451 3.547 => 3.48622758473 4194304 3.479 3.503 3.547 => 3.50964316455 8388608 3.733 3.496 3.532 => 3.58716466865 16777216 3.583 3.522 3.569 => 3.55790996695 33554432 3.550 3.556 3.512 => 3.53952594744Таким образом, с примерно 2,8 секунды для одного (повторяющегося) элемента оно снижается до примерно 2,2 секунды для 2, 4, 8, 16, ... различных элементов и остается на уровне примерно 2,2 секунды до сотен тысяч. Я думаю, это использует мой кеш L2 (4 × 256 КБ, у меня i7-6700 ).
Затем за несколько шагов время увеличивается до 3,5 секунд. Я думаю, что здесь используется комбинация моего кэша L2 и моего кеша L3 (8 МБ), пока он также не «исчерпан».
В конце концов, он остается около 3,5 секунд, я думаю, потому что мои кеши больше не помогают с повторяющимися элементами.
источник
Перед перемешиванием, когда они размещены в куче, смежные объекты индекса являются смежными в памяти, и частота попаданий в память высока при доступе; после перемешивания объект соседнего индекса нового списка отсутствует в памяти. Соседний, процент попаданий очень низкий.
источник