在 Julia 中加速 kNN 函数

Question

我决定将 Peter Harrington 的 机器学习实战 中的一些 Python 代码翻译成 Julia，从 kNN 算法开始。

在对他提供的数据集进行归一化后，我写了几个函数：find_kNN()、mass_kNN（一个为多个输入找到 kNN 的函数），以及一个将给定数据集随机分割成的函数选择训练和测试数据集，调用 mass_kNN()，并多次绘制结果精度。

然后我比较了 Julia 代码和等效的 Python 代码之间的运行次。（我在 Julia 中使用 Distances 来查找欧氏距离，并使用 Gadfly 来绘图，但是关闭绘图对时间影响不大。）

结果：

茱莉亚：
耗时：1.175523034 秒（分配 455531636 字节，47.54% gc 时间）

Python:
已用时间：0.9517326354980469 秒

我想知道是否有加速我的 Julia 代码的方法，或者它是否在这一点上尽可能快地运行ning（我的意思是如果我在使代码运行最快。）

Julia notebook
Python notebook
repo 同时使用笔记本和数据集

谢谢！..

编辑： 删除 convert() 语句并传递所有内容，因为 Real 将时间减慢到 2.29 秒。

Answer 1

所以首先，我删除了 plot_probs 的最后两行 - 我认为绘图并不是真正的基准测试，而且它在很大程度上超出了我（或你）的控制范围 - 可以尝试 PyPlot如果它是一个真正的因素。我也计时了几次plot_probs，看看第一次编译花了多少时间：

**********elapsed time: 1.071184218 seconds (473218720 bytes allocated, 26.36% gc time)
**********elapsed time: 0.658809962 seconds (452017744 bytes allocated, 40.29% gc time)
**********elapsed time: 0.660609145 seconds (452017680 bytes allocated, 40.45% gc time)

所以有一次0.3s的惩罚。继续实际的算法，我使用了内置的分析器（例如 @profile plot_probs(norm_array, 0.25, [1:3], 10, 3)），它显示所有时间（基本上）都花在这里：

~80%: [ push!(dist, euclidean(set_array[i,:][:], input_array)) for i in 1:size(set_array, 1) ]
~20%: [ d[i] = get(d, i, 0) + 1 for i in labels[sortperm(dist)][1:k] ]

像这样使用数组推导不是惯用的 Julia（或者 Python 就此而言）。第一个也很慢，因为所有切片都会生成许多数据副本。我不是 Distances.jl 的专家，但我认为您可以将其替换为

dist = Distances.colwise(Euclidean(), set_array', input_array)

d = Dict{Int,Int}()
for i in labels[sortperm(dist)][1:k]
    d[i] = get(d, i, 0) + 1
end

这给了我

**********elapsed time: 0.731732444 seconds (234734112 bytes allocated, 20.90% gc time)
**********elapsed time: 0.30319397 seconds (214057552 bytes allocated, 37.84% gc time)

通过在 mass_kNN 中进行一次转置可以提取更多性能，但这需要接触太多的地方，而这个 post 已经足够长了。尝试对其进行微优化导致我使用

dist=zeros(size(set_array, 1)
@inbounds for i in 1:size(set_array, 1)
    d = 0.0
    for j in 1:length(input_array)
        z = set_array[i,j] - input_array[j]
        d += z*z
    end
    dist[i] = sqrt(d)
end

它到达

**********elapsed time: 0.646256408 seconds (158869776 bytes allocated, 15.21% gc time)
**********elapsed time: 0.245293449 seconds (138817648 bytes allocated, 35.40% gc time)

所以花了大约一半的时间 - 但真的不值得，而且灵活性较低（例如，如果我想要 L1 怎么办）。其他代码审查点（我知道是主动提供的）：

我发现 Vector{Float64} 和 Matrix{Float64} 比 Array{Float64,1} 和 Array{Float64,2} 更容易看，而且不太可能混淆。
Float64[] 比 Array(Float64, 0)
Int64 可以写成 Int，因为它不需要是 64 位整数。

在 Julia 中加速 kNN 函数

Speeding up kNN function in Julia

python

pandas

dataframe

julia

knn