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

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

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

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

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, создавая новые целые числа. Но это кажется расточительным занятием.

Я прав в своих мыслях? Что делает здесь deepcopy, чего list.copy и мелкое копирование не делают?

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


python-3.x python copy deep-copy
person cs95    schedule 31.01.2019    source источник
comment
Это действительно может быть расточительным, но это то, что делает deepcopy: он копирует все. Он не знает, что вы хотите только скопировать списки.   -  person chepner    schedule 31.01.2019
comment
Он не копирует все (он не копирует неизменяемые встроенные типы), но он все проверяет и поддерживает кеш всех увиденных объектов.   -  person juanpa.arrivillaga    schedule 31.01.2019
comment
Спасибо за комментарии, ребята. Пожалуйста, рассмотрите их как ответ. Казалось бы, мой единственный вариант - переключиться на одномерную реализацию и реализовать некоторую логику для преобразования двухмерных индексов в одномерные индексы при доступе к элементам списка в моем коде.   -  person cs95    schedule 31.01.2019
comment
Обратите внимание, вот исходный код: github.com/python/ cpython / blob / master / Lib / copy.py # L128   -  person juanpa.arrivillaga    schedule 31.01.2019
comment
Если вы точно знаете, как выглядит ваш список, вы, вероятно, можете реализовать свою собственную наивную операцию копирования, например: [sub.copy() for sub in nested_list]. Это будет намного быстрее   -  person juanpa.arrivillaga    schedule 31.01.2019
comment
@ juanpa.arrivillaga Великолепно, я не подумал об этом!   -  person cs95    schedule 31.01.2019
comment
Внедрение собственного копировального устройства также часто бывает безопаснее, чем глубокое копирование, из-за таких проблем, как глубокое копирование слишком глубокого копирования. Если ваш ввод - это список списков материалов, и вам нужен новый список новых списков того же материала, deepcopy скопирует их.   -  person user2357112 supports Monica    schedule 31.01.2019

Ответы (3)


arrow_upward
4
arrow_downward

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)
person user2357112 supports Monica    schedule 31.01.2019

arrow_upward
0
arrow_downward

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

Неглубокая копия: вы можете сфотографировать свою новую мебель и получить представление о том, как она выглядит на самом деле. Картину можно легко носить с собой.

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

person estack    schedule 31.01.2019
comment
Однако, с другой стороны, неглубокая копия - это ссылка на исходный объект. Если вы его измените, это также повлияет на исходный объект. Это неправда. a = []; import copy; b = copy.copy(a); a.append('foo'); print('b:',b,'a:',a). - person juanpa.arrivillaga; 31.01.2019

arrow_upward
0
arrow_downward

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

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

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

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

person Arran Duff    schedule 31.01.2019