对彼此一定距离内的坐标进行分组

Question

我编写了这段代码，它可以运行，但需要很长时间（~8 小时）才能完成执行。

想知道是否可以对其进行优化以加快执行速度。

目的是根据彼此之间的距离对大量项目 (x,y,z) 坐标进行分组。例如;

我想按照 x 方向 +-0.5、y 方向 +-0.5 和 z 方向 +-0.5 的距离对它们进行分组，那么下面数据的输出将是 [(0,3),(1),(2,4)...]。

        x     y     z
0  1000.1  20.2  93.1
1   647.7  91.7  87.7
2   941.2  44.3  50.6
3  1000.3  20.3  92.9
4   941.6  44.1  50.6
...

我所做的（以及有效的）如下所述。

它将 data_frame 的第一行与第二、第三、第四行进行比较，直到结束，对于每一行，如果距 x to x < +-0.5 and y to y < +-0.5 and z to z < +- 0.5 的距离，则将索引添加到一个列表，group。如果没有，则它比较下一行，直到到达循环结束。

每次循环完成后，匹配的索引（存储在group中）被添加到另一个列表，groups，作为一个集合，然后从原始列表中删除，a，然后比较下一个a[0]，依此类推。

groups = []   
group = [] 
data = [(x,y,z),(x,y,z),(etc)] # > 50,000 entries

data_frame = pd.DataFrame(data, columns=['x','y','z'])

a = list(i for i in range(len(data_frame)))

threshold = 0.5

for j in range(len(a) - 1) :
    if len(a) > 0:
        group.append(a[0])
        for ii in range(a[0], len(data_frame) - 1):
            if ((data_frame.loc[a[0],'x'] - data_frame.loc[ii,'x']) < threshold) and ((data_frame.loc[a[0],'y'] - data_frame.loc[ii,'y']) < threshold) and ((data_frame.loc[a[0],'z'] - data_frame.loc[ii,'z']) < threshold):
                group.append(ii)
            else:
                continue
        groups.append(set(group))
        for iii in group:
            if iii in a:
                a.remove(iii)
            else:
                continue
        group = []
    else:
        break

其中 return 是这样的，例如；

groups = [{0}, {1, 69}, {2, 70}, {3, 67}, {4}, {5}, {6}, {7, 9}, {8}, {10}, {11}, {12}, 13}, {14, 73}, {15}, {16}, {17, 21, 74}, {18, 20}, {19}, {22, 23}]

对这个问题做了很多修改，因为它不是很清楚。希望现在有意义。

下面是使用更好的逻辑 'O(NlogN)' 的尝试，它的速度要快得多，但 return 不是正确答案。对 x、y、z 使用了相同的 +-0.5。

编辑：

test_list = [(i,x,y,z), ... , (i,x,y,z)]

df3 = sorted(test_list,key=lambda x: x[1])

result = []
while df3:
    if len(df3) > 1:    ####added this because was crashing at the end of the loop
        a = df3.pop(0)
        alist=[a[0]]
        while ((abs(a[1] - df3[0][1]) < 0.5) and (abs(a[2] - df3[0][2]) < 0.5) and (abs(a[3] - df3[0][3]) < 0.5)):
            alist.append(df3.pop(0)[0])
            if df3:
                continue
            else:
                break
        result.append(alist)
    else:
        result.append(a[0])
        break

Answer 1

由于您将每个数据点与其他每个数据点进行比较，因此您的实现的最差时间复杂度为 O(N!)。更好的方法是先进行排序。

import random
df = [i for i in range(100)]
random.shuffle(df)
df2 = [(i,x) for i,x in enumerate(df)]
df3 = sorted(df2,key=lambda x: x[1])

df3
[(31, 0), (24, 1), (83, 2)......

假设现在您想要将 +5/-5 的数字分组到一个列表中。然后，您可以根据条件将数字切片到列表中。

result = []
while df3:
    a = df3.pop(0)
    alist=[a[0]]
    while a[1] + 5 >= df3[0][1]:
        alist.append(df3.pop(0)[0])
        if df3:
            continue
        else:
            break
    result.append(alist)

result
[[31, 24, 83, 58, 82, 35], [0, 65, 77, 41, 67, 56].......

排序需要 O(NlogN)，而分组基本上需要线性时间。所以这会比 N 快得多！

对彼此一定距离内的坐标进行分组

grouping coordinates within a distance to each other

list

nested-loops

python-3.x

pandas