Почему range () работает медленнее, чем умножение элементов, чтобы получить копии во вложенном списке?

Question

Чтобы скопировать вложенный список в существующий список, к сожалению, недостаточно просто умножить его, в противном случае создаются ссылки, а не независимые списки в списке, см. Этот пример:

x = [[1, 2, 3]] * 2
x[0] is x[1]  # will evaluate to True

Для достиженияваша цель, вы могли бы использовать функцию диапазона в понимании списка, например, увидеть это:

x = [[1, 2, 3] for _ in range(2)]
x[0] is x[1]  # will evaluate to False (wanted behaviour)

Это хороший способ умножения элементов в списке, не просто создавая ссылки, и это также объясняетсянесколько раз на разных сайтах.

Однако есть более эффективный способ копирования элементов списка.Этот код кажется мне немного быстрее (измеряется timeit через командную строку и с другим параметром n ∈ {1, 50, 100, 10000} для кода ниже и диапазона (n) в коде выше):

x = [[1, 2, 3] for _ in [0] * n]

Но мне интересно, почему этот код работает быстрее?Есть ли другие недостатки (большее потребление памяти или подобное)?

python -m timeit '[[1, 2, 3] for _ in range(1)]'
1000000 loops, best of 3: 0.243 usec per loop

python -m timeit '[[1, 2, 3] for _ in range(50)]'
100000 loops, best of 3: 3.79 usec per loop

python -m timeit '[[1, 2, 3] for _ in range(100)]'
100000 loops, best of 3: 7.39 usec per loop

python -m timeit '[[1, 2, 3] for _ in range(10000)]'
1000 loops, best of 3: 940 usec per loop

python -m timeit '[[1, 2, 3] for _ in [0] * 1]'
1000000 loops, best of 3: 0.242 usec per loop

python -m timeit '[[1, 2, 3] for _ in [0] * 50]'
100000 loops, best of 3: 3.77 usec per loop

python -m timeit '[[1, 2, 3] for _ in [0] * 100]'
100000 loops, best of 3: 7.3 usec per loop

python -m timeit '[[1, 2, 3] for _ in [0] * 10000]'
1000 loops, best of 3: 927 usec per loop


# difference will be greater for larger n

python -m timeit '[[1, 2, 3] for _ in range(1000000)]'
10 loops, best of 3: 144 msec per loop

python -m timeit '[[1, 2, 3] for _ in [0] * 1000000]'
10 loops, best of 3: 126 msec per loop

Answer 1

Это правильно;range, даже в Python 3, где он создает объект компактного диапазона, является более сложным, чем список, в классическом компромиссе между вычислениями и хранением.

Поскольку список становится слишком большим, чтобы поместиться в кэш (основной вопрос, если мы обеспокоены производительностью), объект диапазона сталкивается с другой проблемой: при создании каждого числа в диапазоне он уничтожается исоздает новые int объекты (первые 256 или около того менее затратны, потому что они интернированы, но их различие может все еще стоить несколько промахов кэша).Список будет продолжать ссылаться на тот же.

Хотя есть и более эффективные варианты;например, bytearray потребляет гораздо меньше памяти, чем список.Вероятно, лучшая функция для задачи скрыта в itertools: repeat.Как и объект диапазона, ему не требуется хранение для всех копий, но, как и в случае повторного списка, ему не нужно создавать отдельные объекты.Поэтому что-то вроде for _ in repeat(None, x) будет просто показывать те же несколько строк кэша (количество итераций и число ссылок для объекта).

В конце концов, основная причина, по которой люди придерживаются range, заключается в том, что именно это представлено наглядно (как в идиоме для фиксированного цикла подсчета, так и среди встроенных).

В других реализациях Python вполне возможно, что диапазон будет быстрее, чем повтор;это было бы потому, что сам счетчик уже содержит значение.Я ожидаю такого поведения от Cython или PyPy.