Подтвердить что ты не робот

Deepcopy и python - советы, чтобы избежать его использования?

У меня есть очень простая подпрограмма python, которая включает в себя циклирование через список из примерно 20 000 координат широты, долготы и вычисление расстояния каждой точки до контрольной точки.

def compute_nearest_points( lat, lon, nPoints=5 ):
    """Find the nearest N points, given the input coordinates."""

    points = session.query(PointIndex).all()
    oldNearest = []
    newNearest = []
    for n in xrange(nPoints):
        oldNearest.append(PointDistance(None,None,None,99999.0,99999.0))
        newNearest.append(obj2)

    #This is almost certainly an inappropriate use of deepcopy
    #  but how SHOULD I be doing this?!?!
    for point in points:
        distance = compute_spherical_law_of_cosines( lat, lon, point.avg_lat, point.avg_lon )
        k = 0
        for p in oldNearest:
            if distance < p.distance:
                newNearest[k] = PointDistance(
                    point.point, point.kana, point.english, point.avg_lat, point.avg_lon, distance=distance
                    )
                break
            else:
                newNearest[k] = deepcopy(oldNearest[k])
            k += 1
        for j in range(k,nPoints-1):
            newNearest[j+1] = deepcopy(oldNearest[j])
        oldNearest = deepcopy(newNearest)

    #We're done, now print the result
    for point in oldNearest:
        print point.station, point.english, point.distance

    return

Я изначально написал это на C, используя тот же подход, и он отлично работает там и в основном мгновен для nPoints <= 100. Поэтому я решил перенести его на python, потому что я хотел использовать SqlAlchemy для создания других вещей.

Сначала я портировал его без инструкций deepcopy, которые теперь пересиливают метод, и это привело к тому, что результаты были "нечетными" или частично некорректными, потому что некоторые из точек просто копировались как ссылки (я думаю, я думаю? ) - но это было все еще довольно быстро, как версия C.

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

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

EDIT:
Я попал в гораздо более простое и быстрое решение,

def compute_nearest_points2( lat, lon, nPoints=5 ):
    """Find the nearest N points, given the input coordinates."""

    points = session.query(PointIndex).all()
    nearest = []

    for point in points:
        distance = compute_spherical_law_of_cosines( lat, lon, point.avg_lat, point.avg_lon )
        nearest.append( 
            PointDistance(
                point.point, point.kana, point.english, point.avg_lat, point.avg_lon, distance=distance
                )
            )

    nearest_points = sorted(nearest, key=lambda point: point.distance)[:nPoints]     
    for item in nearest_points:
        print item.point, item.english, item.distance
    return

Итак, в основном я просто делаю полную копию ввода и добавляю новое значение - расстояние от контрольной точки. Затем я просто применил "отсортированный" к результирующему списку, указав, что ключ сортировки должен быть свойством расстояния объекта PointDistance.

Это намного быстрее, чем использование deepcopy, хотя, признаюсь, я действительно не понимаю, почему. Я полагаю, что до эффективных C-реализаций python "отсортирован"?

4b9b3361

ОТВЕТЫ

Ответ 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, поэтому я предполагаю, что есть способы избежать этого в большинстве случаев.

Ответ 2

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

array = [None] * num_elements
for i in range(num_elements):
    array[i] = True

против

array = []
for i in range(num_elements):
    array.append(True)

Простой timeit запуск этих двух методов показывает улучшение на 25%, если вы предварительно выделите массив для даже умеренных значений num_elements.