python - 最近邻算法的优化

Question

背景:
前段时间问了一个问题here关于通过将每个点相互比较来查找一组数据中每个点的邻居的最有效方法。我试图通过根据坐标列表的 x 坐标将坐标列表分成单独的集合并将它们分组为重叠集合来优化该过程。然后在每个集合上使用邻居查找器“pairs_3”。然后这给了我一整套顶点之间的连接。下面的代码是我目前所拥有的代码片段:

def pairs_3(coordinates, vertex_spacing): #Function from previous question
    i=-1
    results_2 = []
    results_2 [:]= []
    for (xc, yc, zc) in enumerate(coordinates):
        for (xb, yb, zb) in enumerate(coordinates[ic:]):
            dx = xb - xc 
            if sqrt(dx**2) > a:
                    break
            dy = yb - yc
            dz = zb - zc

            if (sqrt(dx**2+dy**2+dz**2)) == vertex_spacing:
                i+=1
                results_2.append([(xc, yc, zc), (xb, yb, zb), width, dx, dy, dz, edge])
    return results_2

Coordinates_xyz=sorted(set(zip(Coord_x,Coord_y,Coord_z))) #Full 3D coordinate list
Coord_x_set=sorted(set(Coord_x))
numerical_width = Coord_x.count(Coord_x_set[1]) #gets number of columns
N=numerical_width
Col_subList = [Coordinates_xyz[n:n+2*N] for n in range(0,         len(Coordinates_xyz), N)] #Col_subList is a list of grouped data according to x coordinate. The data is always discrete, so this is possible.

new_p_2=[]
new_p_2[:]=[]
new_p_3=[]
new_p_3[:]=[]
#where a is vertex separation, a known value used to generate the data
for x in Col_subList:
   new_p_2.append(pairs_3(x, a))

for x in new_p_2:
    for y in x:
        new_p_3.append(y)

p_2=new_p_3
start=column(p_2,0) #Start Vertex
end=column(p_2, 1) #End Vertex
s_i=[] #Start Vertex Index
s_i[:]=[] 
c_i=[] #Connection Index
c_i[:]=[]
for i in start:
indices = [ind for ind, x in enumerate(Coordinates_xyz_final) if x == i]
for j in indices:
    s_i.append(j)

for i in xrange(len(start)):
c_i.append(i)
p_2 = zip(start, end, s_i, c_i) #Final form necessary for later calculations

问题:
有没有办法进一步/更好地优化这段代码？有没有什么方法可以进一步分解问题而不比函数本身的计算成本更高？

奖励问题:
有没有办法将“分而治之”有效地集成到函数本身中？即根据函数内的列将列表分成集合？

Answer 1

你要找的是R-Tree .如果你只是想把它作为解决问题的工具，我建议你选择现有的几个实现之一，谷歌出现了，例如https://pypi.python.org/pypi/Rtree/ .