深拷贝与Python - 避免使用的技巧？

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语言写的，方法完全一样，效果很好，对于点数不超过100的情况，几乎是瞬间完成。所以我决定把它移植到Python上，因为我想用SqlAlchemy做一些其他的事情。

我最开始移植的时候没有使用深拷贝的语句，这导致结果有点“奇怪”，或者说部分不正确，因为有些点只是作为引用被复制（我想是这样？我觉得是这样）——但速度几乎和C版本一样快。

现在加上了深拷贝的调用，程序能正确完成任务了，但性能却大幅下降，现在需要几秒钟才能完成同样的工作。

这看起来是一个相当常见的任务，但我显然没有用Python的“正确方式”来做。我应该怎么做才能得到正确的结果，同时又不需要到处使用深拷贝呢？

编辑：
我找到了一个更简单、更快的解决方案，

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对象的距离属性。

这样比使用深拷贝快多了，虽然我承认我并不太明白为什么。我想这可能和Python的“sorted”背后高效的C实现有关？

Answer 1

我知道这并没有直接回答你的问题（而且我也知道这是个老问题），但因为有关于性能的讨论，看看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测试这两种方法，如果你为num_elements预先分配数组，性能会提高25%，即使是对于中等大小的值也是如此。

Answer 2

好的，先从简单的开始说：

1. deepcopy 一般比较慢，因为它需要做很多内部的管理工作，以合理的方式复制一些特殊情况，比如包含自身的对象。你可以看看这个 页面，或者查看一下你 Python 路径下的 copy.py 文件中的 deepcopy 源代码。

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