deepcopy和python - tips避免使用它吗？

Question

我有一个非常简单的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做一些其他的事情。

我第一次移植它时没有使用现在方法中的深度复制语句，这导致结果“奇怪”，或者部分不正确，因为一些点只是被复制为引用(我猜？我认为？) --但它仍然几乎和C版本一样快。

现在添加了深度复制调用，例程正确地完成了它的工作，但它已经招致了极端的性能损失，并且现在需要几秒钟来完成相同的工作。

这似乎是一项很普通的工作，但我显然不是用pythonic的方式来做。我应该如何做到这一点，以便我仍然获得正确的结果，而不是必须包括所有地方的深度拷贝？

编辑：

我偶然发现了一个更简单更快的解决方案，

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

所以基本上我只是复制了一份完整的输入，并添加了一个新的值-到参考点的距离。然后，我将'sorted‘应用于结果列表，指定排序关键字应该是PointDistance对象的distance属性。

这比使用深度拷贝快得多，尽管我承认我真的不明白为什么。我猜这归功于高效的C实现，python的“排序”？

Answer 1

好的，先说最简单的事情：

1. deepcopy通常很慢，因为它必须做大量的内部记账来复制病理情况，比如以正常的方式包含自身的对象。例如，查看this page，或者查看Python中某个地方的deepcopy的源代码path.
2. 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移动到指向新数字。因此，简而言之:数字、字符串和元组是不可变的；列表、字典和集合是可变的。用户定义的类通常是可变的，除非您显式确保不能改变内部状态。还有frozenset，它是一个不可变的集合。当然还有很多其他的:)

我不知道为什么你的原始代码不能工作，但可能你遇到了与我用列表显示的代码片段相关的行为，因为你的PointDistance类在默认情况下也是可变的。另一种选择是来自collections的namedtuple类，它构造了一个类似元组的对象，其字段也可以通过名称访问。例如，您可以这样做：

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，所以我猜在大多数情况下都有避免它的方法。

Answer 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)

如果您为num_elements的中值预分配数组，则这两种方法的简单timeit运行将显示25%的性能改进。