17

我有一个非常简单的 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 调用，该例程可以正常工作，但它已经招致了极大的性能损失，现在需要几秒钟才能完成相同的工作。

这似乎是一项很常见的工作，但我显然不是以 Python 的方式来做的。我应该怎么做才能得到正确的结果，但不必在任何地方都包含 deepcopy？

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

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 的“排序”？

4

2 回答 2

36

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

  1. deepcopy通常速度很慢，因为它必须做大量的内部簿记才能复制病理案例，比如以理智的方式包含自己的对象。例如，请参阅此页面，或查看 Python 路径中某处的 indeepcopy的源代码。copy.py

  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类默认情况下也是可变的。另一种方法是namedtuplefrom 类collections，它构造一个类似元组的对象，其字段也可以通过名称访问。例如，您可以这样做：

from collections import namedtuple
PointDistance = namedtuple("PointDistance", "point distance")

这将为您创建一个PointDistance具有两个命名字段的类：point和distance. 在您的主for循环中，您可以适当地分配这些。由于字段指向的点对象在循环point过程中不会被修改，并且是一个数字（根据定义，它是不可变的），因此这样做应该是安全的。但是，是的，一般来说，似乎简单地使用更快，因为它是用 C 实现的。你可能还对这个模块很幸运，它实现了一个由普通 Python 列表支持的堆数据结构，因此它可以让你轻松找到顶部元素无需对其他人进行排序。但是，由于也在 Python 中实现，因此很有可能fordistancesortedsortedheapqkheapqsorted除非你有很多点，否则效果会更好。

最后，我想补充一点，deepcopy到目前为止我从来没有使用过，所以我想在大多数情况下都有办法避免它。

于 2010-06-15T09:26:44.770 回答
6

我知道这并不能直接解决您的问题（而且我知道这是一个老问题），但是由于有一些关于性能的讨论，因此可能值得查看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.

于 2012-12-05T16:15:30.490 回答