Ответ 1
Хорошо, сначала простейшие:
-
deepcopyявляется медленным в целом, поскольку он должен делать много внутренних бухгалтерских операций, чтобы скопировать патологические случаи, такие как объекты, содержащие себя разумным способом. См., Например, эту страницу или посмотрите исходный кодdeepcopyвcopy.py, который находится где-то на вашем пути Python. -
sortedработает быстро, поскольку он реализован в C. Намного быстрее, чем эквивалентная сортировка в Python.
Теперь, еще кое-что о проверке поведения ссылок на Python, как вы просили в своем комментарии. В Python переменными являются ссылки. Когда вы говорите a=1, подумайте, что он имеет 1 как объект, существующий сам по себе, а a - это только тег, прикрепленный к нему. В некоторых других языках, таких как C, переменными являются контейнеры (не теги), а когда вы делаете a=1, вы фактически ставите 1 в a. Это не выполняется для Python, где переменными являются ссылки. Это имеет некоторые интересные последствия, которые вы, возможно, также наткнулись на:
>>> a = [] # construct a new list, attach a tag named "a" to it
>>> b = a # attach a tag named "b" to the object which is tagged by "a"
>>> a.append(1) # append 1 to the list tagged by "a"
>>> print b # print the list tagged by "b"
[1]
Это поведение видно из-за того, что списки являются изменяемыми объектами: вы можете изменить список после его создания, а модификация видна при доступе к списку через любую из переменных, которые ссылаются на него. Неизменяемыми эквивалентами списков являются кортежи:
>>> a = () # construct a new tuple, attach a tag named "a" to it
>>> b = a # now "b" refers to the same empty tuple as "a"
>>> a += (1, 2) # appending some elements to the tuple
>>> print b
()
Здесь a += (1, 2) создает новый кортеж из существующего кортежа, на который ссылается a, плюс еще один набор (1, 2), который строится "на лету", а a настраивается так, чтобы указывать на новый кортеж, хотя, конечно, b все еще относится к старому кортежу. То же самое происходит с простыми числовыми дополнениями, такими как a = a+2: в этом случае номер, на который первоначально указывал a, никак не мутировался, Python "конструирует" новое число и перемещает a, чтобы указать на новый номер, Итак, в двух словах: числа, строки и кортежи неизменяемы; списки, dicts и sets изменяемы. Пользовательские классы в общем случае изменяются, если вы не гарантируете явно, что внутреннее состояние не может быть мутировано. И там frozenset, что является неизменным множеством. Плюс много других конечно:)
Я не знаю, почему ваш исходный код не работал, но, вероятно, вы столкнулись с поведением, связанным с фрагментом кода, который я показал со списками, поскольку ваш класс PointDistance также изменен по умолчанию. Альтернативой может быть класс namedtuple из collections, который создает объект, подобный кортежу, полям которого также могут быть доступны имена. Например, вы могли бы сделать это:
from collections import namedtuple
PointDistance = namedtuple("PointDistance", "point distance")
Это создает класс PointDistance для вас, у которого есть два именованных поля: point и distance. В основном цикле for вы можете соответствующим образом назначить их. Поскольку точечные объекты, на которые указывают поля point, не будут изменяться в течение цикла for, а distance - это число (которое по определению является неизменным), вы должны быть в безопасности, делая это путь. Но да, в общем, кажется, что просто использовать sorted быстрее, поскольку sorted реализуется в C. Вам также может быть повезло с модулем heapq, который реализует структуру данных кучи, поддерживаемую обычным списком Python, поэтому он позволяет легко находить верхние элементы k, не сортируя остальные. Однако, поскольку heapq также реализован в Python, возможно, что sorted работает лучше, если у вас нет большого количества точек.
Наконец, я хотел бы добавить, что мне никогда не приходилось использовать deepcopy, поэтому я предполагаю, что есть способы избежать этого в большинстве случаев.