在 matlab 中更快地查找行

Question

我有一个很长的项目 x、y、z 坐标列表 (200K-800K,3)，我需要搜索并找到离特定点最近的项目 - 这个最终列表始终位于至少 1 项，通常少于 10 项。

我尝试了一些简单的搜索方法来查找此列表，但我遇到了一些限制 - 这是我迄今为止最好的两种方法：

方法 1 - 查找索引

xInd = find(PositionsList(:,1) > (searchPoint(i,1) - searchRad) & PositionsList(:,1) < (searchPoint(i,1) + searchRad));
yInd = find(PositionsList(xInd,2) > (searchPoint(i,2) - searchRad) & PositionsList(xInd,2) < (searchPoint(i,2) + searchRad));
xyInd = xInd(yInd);
zInd = find(PositionsList(xyInd,3) > (searchPoint(i,3) - searchRad) & PositionsList(xyInd,3) < (searchPoint(i,3) + searchRad));
xyzInd = xyInd(zInd);

方法二——暴力距离搜索

neighbours = sqrt(sum(bsxfun(@minus,searchPoint(i,:),PositionsList).^2,2)) <= searchRad;
xyzInd = find(neighbours == 1);

方法 3 - 逻辑索引

xInd = PositionsList(:,1) > (searchPoint(i,1) - searchRad) & PositionsList(:,1) < (searchPoint(i,1) + searchRad);
newlist = PositionsList(xInd==1,:);
yzInd = newlist(:,2) > (searchPoint(i,2) - searchRad) & newlist(:,2) < (searchPoint(i,2) + searchRad)... 
    & newlist(:,3) > (searchPoint(i,3) - searchRad) & newlist(:,3) < (searchPoint(i,3) + searchRad);
xyzInd = newlist(yzInd==1,:);

对于我的数据，方法 1 更快 - 对于 20000 个粒子的小列表，它运行s 在大约 25 秒内，而方法 2 运行s 在大约 170 秒内，但方法 2 稍微多一点准确 - 它有可疑的邻居（搜索区域边缘的离群值）的频率要低得多。

我的代码调用此搜索数千次，因此我希望尽可能多地节省时间 - 它目前约占我运行时间的 85%。我读过 mex 实现可能要快得多，但我不熟悉 mex。我还尝试了第三种逻辑索引方法而不是查找，但它在 35 秒时速度较慢。

有人可以帮助加快搜索速度吗？也许是 mex 函数？

Answer 1

根据 obchardon 的建议，我查看了用于搜索的 k-d 树，发现以下内容，kd-tree for matlab，与我的数据进行文件交换，并开始使用我的数据进行测试。现在，我可以在 5 秒内完成对 500K 坐标的搜索，而我之前最好的 25s 搜索 20K 组坐标。巨大的进步。

唯一的缺点是它的顺序 returns 邻居似乎是随机的，这意味着我有一些轻微的 "caressing" 结果要做，但是为了节省时间，这更多比可接受的。

感谢您的宝贵建议！！

在 matlab 中更快地查找行

Faster finding of rows in matlab

search

matlab

mex

方法 1 - 查找索引

方法二——暴力距离搜索

方法 3 - 逻辑索引