2

在 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 个点的数组上工作的时间很长......:(((

4

1 回答 1

5

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

因此，您的代码是次优的，因为它至少运行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)由于大量复制，您仍然是。为避免这种情况，您需要将数组存储在双向链表中。然后删除一个元素将是 of 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-tree 或 Patricia-tree，它使用浮点数作为键。在这样的树中插入可以（相当快）'O（log N）'完成。但是，我不知道这种树的任何标准实现。标准实现适用于字符串或整数。因此，如果我们有一个从浮点数到整数的有序且无冲突的映射，我们就可以实现它。这种映射一般不存在，但毫无疑问可以为任何特定数据集构建。毫无疑问，所讨论的数据集是特定的：肯定有一个上限和一个精度。

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

于 2013-01-11T14:37:03.917 回答