algorithm - 在向量中找到 K 最小的元素，其中 K 非常小

Question

我正在尝试使用 GPU 加速我的 Matlab 程序，但由于函数“knnsearch”不支持 GPU，我决定编写自己的暴力函数

(当然还有其他选择，比如编写 CUDA 内核，或者使用现有的库，但是设置它们必须花费一些时间，而且我在 windows 10 上，即使设置 matlab 来处理 mex 文件也很痛苦，错误不断出现......，所以我现在将坚持使用蛮力方法)。

即使这只是暴力搜索，我也看到了一些很大的改进(代码运行速度提高了 2 倍)。这是我的函数，以及分析结果(真的很短)该函数接受单个查询点，并在引用点中找到 K 个最近的邻居(所有点都存储在 gpuArray 中)。起初，我认为距离的计算会花费最多的时间，但是正如您在分析器结果中看到的那样，排序部分是最耗时的。

我想通过优化您在数组中找到最小 K 元素的部分来改进代码。请注意，K 非常小(K <= 50)，而数据点的数量非常大(>= 10000)。我知道有针对此特定任务量身定制的算法(例如堆排序，但您只需要堆构建部分)，但我不确定如何使用 GPU 来实现它们并且不会减慢速度。谁能帮我？非常感谢:)

Answer 1

knnsearch 在 MATLAB R2016b 的 GPU 上受支持。