python - 如何使用 scipy.weave 更改 python 代码？ (如何用代码做得更快？)

Question

在Python中: 我有 2 个数组:lon、lat(超过 500 000 点)。

     lon = numpy.array()
     lat = numpy.array()

     flag = True
     while flag:
        lon1 = lon[:-1]
        lon2 = lon[1:]
        lat1 = lat[:-1]
        lat2 = lat[1:]

        '''distance'''
        x = (lon2 - lon1)
        y = (lat2 - lat1)
        d = numpy.sqrt(x * x + y * y)

        min = numpy.min(d)
        if min < 0.015:
            j = numpy.where(d == min)[0][0]

            lon[j] = (lon[j] + lon[j + 1]) / 2
            lat[j] = (lat[j] + lat[j + 1]) / 2

            lon = numpy.delete(lon, j + 1)
            lat = numpy.delete(lat, j + 1)

        else:
            flag = False

这段代码运行速度非常慢!

1. 请提示，如何用代码做得更快？

2. 我知道有scipy.weave。请提示，如何使用scipy.weave更改代码？

   import scipy
   from scipy import weave
   
   codeC = """
   ???
   """
   scipy.weave.inline(codeC, ['lon', 'lat'], compiler='gcc')
   

谢谢。

更新:

    lon1 = lon[:-1]
    lon2 = lon[1:]
    lat1 = lat[:-1]
    lat2 = lat[1:]

    x = (lon2 - lon1)
    y = (lat2 - lat1)
    d = x * x + y * y

    while True and d.size > 1:

        j = np.argmin(d)
        if d[j] > min_radius:
            break

        lon[j] = (lon[j] + lon[j + 1]) / 2
        lat[j] = (lat[j] + lat[j + 1]) / 2

        '''lon = np.delete(lon, j + 1)
           lat = np.delete(lat, j + 1)
           d = np.delete(d, j)'''
        if j == (d.size - 1):
            lon = lon[:j + 1]
            lat = lat[:j + 1]
            d = d[:j]
        else:
            lon = np.hstack((lon[:j + 1], lon[j + 2:]))
            lat = np.hstack((lat[:j + 1], lat[j + 2:]))
            d = np.hstack((d[:j], d[j + 1:]))


        if j > 0:
            x = lon[j] - lon[j - 1]
            y = lat[j] - lat[j - 1]
            d[j - 1] = x * x + y * y
        if j < (d.size - 1):
            x = lon[j + 1] - lon[j]
            y = lat[j + 1] - lat[j]
            d[j] = x * x + y * y

@ilmiacs、@Jaime、@Luke，谢谢! 它的工作速度要快得多!

但是作为一个整体，代码在 500 个点的数组上运行很长时间...:(((

Answer 1

您将在循环中的每次迭代中重做整个昂贵的计算。一次迭代仅删除一个节点，然后在删除一个元素时复制整个数组并重新进行距离计算。然后你搜索下一个节点。

因此，您的代码不是最优的，因为它至少运行 O(N^2)。但是，对于您想要实现的目标，O(N log N) 或可能 O(N) 就足够了。

如果重新排列算法，没有 numpy 的简单 python 模块应该足够快。食谱:

1. 避免重新计算整个距离数组。删除一个节点时，只需重新计算两个值。
2. 避免复制。价格也很贵。

希望这有帮助。

编辑:

无需重新计算距离数组的示例实现如下:

lon = numpy.array()
lat = numpy.array()

lon1 = lon[:-1]
lon2 = lon[1:]
lat1 = lat[:-1]
lat2 = lat[1:]

'''distance'''
x = (lon2 - lon1)
y = (lat2 - lat1)
d = x * x + y * y

while True:
    min = numpy.min(d)
    if min < 0.015 * 0.015:
        j = numpy.where(d == min)[0][0]
    else:
        break

    lon[j] = (lon[j] + lon[j + 1]) / 2
    lat[j] = (lat[j] + lat[j + 1]) / 2

    lon = numpy.delete(lon, j + 1)  # <-- you spend most of the time here
    lat = numpy.delete(lat, j + 1)  # <-- and here

    d = numpy.delete(d, j)      # <-- and here

    x = lon[j]-lon[j-1]
    y = lat[j]-lat[j-1]
    d[j-1] = x * x + y * y
    x = lon[j+1]-lon[j]
    y = lat[j+1]-lat[j]
    d[j] = x * x + y * y

虽然这会给你带来提升，但由于大量的复制，你的复杂度仍然是O(N^2)。为了避免这种情况，您需要将数组存储在双向链表中。那么删除一个元素的时间复杂度为 O(1)，而不是 O(N)。使用链表，最糟糕的操作将是找到最小值。您可以通过引入 d 的排序版本来改进这一点，您还可以在其中跟踪 d 中的位置。不过，您需要跟踪更改。但最终你会得到一个O(N log N)的算法。

编辑2:

正如@Jaime 所指出的，比较平方距离也是没有必要的。我已经更正了上面的代码。

编辑3:

周末我更多地思考了算法，结果发现这是一个非常有趣的问题，思考起来很有趣。我想分享我的想法。

要让它工作O(N log N)没有我想象的那么简单。我建议保留一个列表 sorted_d 并管理它。每次删除链接时，我们都必须更新 sorted_d 中的两个条目。这意味着，我们必须在 sorted_d 中找到两个对应距离的新位置。在普通列表中，查找位置可以通过二分来完成，时间复杂度为 O(log N)。然而，据我了解，二分在链表中是不可行的，并且会变成O(N)。这就是问题。如果有人能证明我错了，并提出一种在 O(log N) 的排序链表中插入元素的方法，我会很高兴。我个人不这么认为。

但是，sorted_d 的链表还有一个替代方案。我们所需要的只是一棵 B 树或一棵 Patricia 树，它们使用 float 作为键。在这样的树中插入可以在(相当快)“O(log N)”中完成。但是，我不知道这样一棵树的任何标准实现。标准实现适用于字符串或整数。因此，如果我们有一个从 float 到整数的有序且无碰撞的映射，我们就可以实现它。这种映射一般不存在，但毫无疑问可以为任何特定数据集构建。毫无疑问，所讨论的数据集是特殊的:当然有一个上限和一个精度。

希望这有帮助。如果还有进一步的兴趣，我还可以提出我对这个问题的最佳数据结构的想法。