Список Python против массива: причина неожиданной разницы в производительности - PullRequest
Новая
       28

Список Python против массива: причина неожиданной разницы в производительности

0 голосов
/ 03 мая 2018

Я сейчас изучаю алгоритмы и структуры данных.

Я подумал, что проведу быстрый timeit.timeit тест для итерации по списку из 2 ** 30 случайных целых чисел в list() по сравнению с тем же для формата array.array.

Я ожидал, что массив закончится первым, поскольку одним из немногих приглушенных преимуществ, которые я видел в других публикациях с массивом Python, является производительность. (У меня изначально было ошибочное впечатление, что список был реализован как связанный список: спасибо за исправление, Дункан)

Конечно, массив должен быть по крайней мере таким же быстрым, как список? 

import os
import array
l = list(os.urandom(2**30))
a = array.array('I', l)

def test_list():
 for i in l:
  pass

def test_array():
 for i in a:
  pass

>>> timeit.timeit(test_array, number=5)
50.08525877200009
>>> timeit.timeit(test_list, number=5)
37.00491460799958

Вот информация о моей платформе: Python 3.6.5, [GCC 7.3.0] в Linux x86_64 (Intel i5 4660)

1 Ответ

0 голосов
/ 03 мая 2018

Сначала вы инициализируете l в список из 2 ** 30 значений Python int.

Во-вторых, вы инициализируете a из списка, чтобы создать список из 2 ** 30 целых чисел C.

test_list перебирает список значений Python int. В этом процессе никакие объекты Python не создаются и не уничтожаются, просто счетчик ссылок для каждого из них увеличивается, а затем уменьшается.

test_array перебирает список целых чисел C, создавая новый Python int для каждого элемента, а затем уничтожает его снова. Вот почему массив медленнее: он создает и уничтожает 2 ** 30 объектов Python.

Внутренне список Python - это просто массив указателей на содержащиеся в нем объекты. Это означает, что итерация по списку является такой же простой и быстрой, как итерация по массиву. Тип array здесь будет использовать меньше памяти в целом (или это было бы, если бы вы не держали список), так как целые числа C намного меньше, чем объекты Python, но каждый доступ к массиву должен преобразовывать значение C в объект Python, и хотя создание объекта сильно оптимизировано, это все же занимает больше времени, чем просто получение другой ссылки на существующий объект.

...