Почему глубокая копия намного медленнее, чем мелкая, для списков одинакового размера?

Question

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

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

Воспроизвести моипроблема, запустите следующий код:

import numpy as np

np.random.seed(0)
lst1 = np.random.randint(100, size=1000 * 1000).tolist()
lst2 = np.random.randint(100, size=(1000, 1000)).tolist()

Теперь, синхронизируя приведенные ниже утверждения, вы должны увидеть моменты, похожие на мои.

%timeit copy.copy(lst1)
%timeit lst1.copy()
%timeit copy.deepcopy(lst2)

5 ms ± 49.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
5.47 ms ± 551 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
1.61 s ± 112 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Оба lst1 и lst2 имеютмиллион элементов, но надежное копирование первого в 200 раз быстрее, чем вложенный список с таким же количеством элементов.Я подумал, что это связано с тем фактом, что создание глубоких копий вложенных списков может потребовать некоторой рекурсивной реализации, которая будет медленной, поэтому я попытался

%timeit copy.deepcopy(lst1)
1.43 s ± 90.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

И время все еще показывает значительное замедление.Я проверил документы , но объяснений было мало.Однако по времени я подозреваю, что deepcopy копирует также каждый int , создавая новые целые числа.Но это похоже на расточительство.

Правильно ли я здесь думаю?Что делает здесь глубокая копия, а list.copy и мелкая копия этого не делают?

Я видел, что deepcopy () очень медленно , но, похоже, вопрос требует альтернативы, а необъяснение (мне не было понятно).

Answer 1

В программировании глубокая копия эквивалентна физической копии чего-либо.Это фактическая копия оригинального объекта.В большинстве инструментов программирования вы можете поэкспериментировать с ним, изменить его, не затрагивая исходный объект.Однако, с другой стороны, мелкая копия - это ссылка на исходный объект.Если вы измените его, это также повлияет на исходный объект.Короче говоря, поскольку глубокая копия является действительной копией исходного объекта, она тяжелее мелкой копии, которая просто указывает на исходный объект.

Мелкая копия: Вы можете иметь изображение (и) своегоновая мебель, и получить представление о том, как это действительно выглядит.Вы можете легко носить с собой фотографию.

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

Answer 2

https://docs.python.org/2/library/copy.html

Разница между мелким и глубоким копированием относится только к составным объектам (объектам, которые содержат другие объекты, например списки или экземпляры классов):

1. Мелкоеcopy создает новый составной объект, а затем (насколько это возможно) вставляет в него ссылки на объекты, найденные в оригинале.
2. Глубокая копия создает новый составной объект, а затем рекурсивно вставляет в него копииобъекты, найденные в оригинале

Таким образом, мелкая копия создаст новый список и заполнит его ссылкой на каждый элемент в оригинальном списке.Поскольку каждый элемент в исходном списке сам по себе является списком, гораздо быстрее просто сохранить ссылку на него, чем создать новую копию.Deepcopy делает некоторые умные вещи в том, как копирует каждый элемент, чтобы избежать ошибок.Но, в сущности, вам не нужно понимать это, чтобы знать, почему одна мелководная копия быстрее, чем глубокая. ....

Answer 3

deepcopy не копирует целые числа.В любом случае, это невозможно.

deepcopy медленный, потому что он должен обрабатывать всю сложность глубокой копии, даже если это оказывается ненужным.Это включает в себя отправку в соответствующий копир для каждого найденного объекта, даже если для копира получается , в основном просто lambda x: x.Это включает в себя поддержание меморандума и отслеживание каждого скопированного объекта для обработки дублированных ссылок на одни и те же объекты, даже если их нет.Это включает в себя специальную обработку копирования для структур данных, таких как списки и dicts , так что это не приводит к бесконечной рекурсии при попытке скопировать структуру данных с рекурсивными ссылками.

Все это должно быть сделано независимо от того, окупается ли оно.Все это дорого.

Кроме того, deepcopy - это чистый Python.Это не помогаетСравнивая deepcopy с pickle.loads(pickle.dumps(whatever)), который выполняет очень похожую работу, pickle выигрывает легко благодаря реализации C.(В Python 2 замените pickle на cPickle.) pickle все еще сильно проигрывает реализации, которая использует преимущества известной структуры ввода, хотя:

In [15]: x = [[0]*1000 for i in range(1000)]

In [16]: %timeit copy.deepcopy(x)
1.05 s ± 5.14 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [17]: %timeit pickle.loads(pickle.dumps(x))
78 ms ± 4.03 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [18]: %timeit [l[:] for l in x]
4.56 ms ± 108 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)