使用八分之一搜索算法提高性能

Question

我正在做一个八进制搜索，以找到距离我的圆形点（o）最近的点（+）的n个数（例如8）。这将意味着我的点（+）减少到只有64（8每八分之一）。你知道吗

我做的第一件事是把我的区域分成八分之一，以我的点（o）为参考。你知道吗

数据=包含所有点（+）的（x，y，z）的数组 gdata=包含点（o）的（x，y）的数组

import tkinter as tk
from tkinter import filedialog
import pandas as pd
import numpy as np
from scipy.spatial.distance import cdist
from collections import defaultdict

root = tk.Tk()
root.withdraw()
file_path = filedialog.askopenfilename()
data = pd.read_excel(file_path)
data = np.array(data, dtype=np.float)
nrow, cols = data.shape

file_path1 = filedialog.askopenfilename()
gdata = pd.read_excel(file_path1)
gdata = np.array(gdata, dtype=np.float)

pwangle = np.zeros(nrow)

for j in range(nrow):
    delta_x = gdata[:,0]-data[:,0][j]
    delta_y = gdata[:,1]-data[:,1][j]
    if delta_x != 0:
        pwangle[j] = np.rad2deg(np.arctan(delta_y/delta_x))
    else:
        if delta_y > 0:
            pwangle[j] = 90
        elif delta_y < 0:
            pwangle[j] = 270
    if (delta_x < 0)&(delta_y > 0):
        pwangle[j] = 180 + pwangle[j]
    elif (delta_x < 0)&(delta_y < 0):
        pwangle[j] = 270 - pwangle[j]
    elif (delta_x > 0)&(delta_y < 0):
        pwangle[j] = 360 + pwangle[j]

vecangle = pwangle.ravel()
sortdata = defaultdict(list)
count = -1
get_anglesector = 45

N = 8
d = cdist(data[:,:2], gdata)
P = np.hstack((data, d)) 

for j in range(0, 360, get_anglesector):
    count += 1
    get_data = []
    for k, dummy_val in enumerate(vecangle):
        if j <= vecangle[k] < j + get_anglesector:
            get_data.append(P[k,::])
            sortdata[count] = np.array(get_data)

将数据分组到不同的八进制之后，我对每个八进制中的数据进行排序，以获得离点（o）最近的8个数据。你知道吗

for i, j in enumerate(sortdata):   
    octantsort = defaultdict(list)
    for i in range(8):
        octantsort[i] = np.array(sortdata[i][sortdata[i][:,3].argsort()[:N]])

有没有一种有效的方法来提高性能？你知道吗

这很好，但是当我有一个以上的“o”点（例如10000个“o”）并且我已经为每个点运行了上面的代码时，这将非常耗时。你知道吗

Answer 1

谢谢@user7138814，除了做一些小改动，你的代码速度更快

N=8  
delta = gdata - data[:,:2]
angles = np.arctan2(delta[:,1], delta[:,0])
bins = np.linspace(-np.pi, np.pi, 9)
bins[-1] = np.inf  # handle edge case
octantsort = []
for i in range(8):
    data_i = data[(bins[i] <= angles) & (angles < bins[i+1])]
    dist_order = np.argsort(cdist(data_i[:,:2], gdata), axis=0)
    [octantsort.append(data_i[dist_order[:N][j]]) for j in range(8)]
final = np.vstack(octantsort)

前一代码（问题代码）的执行时间：

    0.021449804306030273 seconds    

本帖代码执行时间：

   0.0015172958374023438 seconds    

Answer 2

如果您使用^{}而不是arctan，那么这项工作就容易多了。然后对速度进行矢量化，我们可以得到如下结果：

import numpy as np
from scipy.spatial.distance import cdist

delta = gdata - data[:,:2]
angles = np.arctan2(delta[:,1], delta[:,0])
bins = np.linspace(-np.pi, np.pi, 9)
bins[-1] = np.inf  # handle edge case
octantsort = []
for i in range(8):
    data_i = data[(bins[i] <= angles) & (angles < bins[i+1])]
    dist_order = np.argsort(cdist(data_i, gdata))
    octantsort.append(data_i[dist_order[:N]])