python - 在 Julia 中加速 kNN 函数

Question

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

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

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

结果:

Julia :
耗时:1.175523034 秒(分配了 455531636 字节，47.54% gc 时间)

python :
耗时:0.9517326354980469 秒

我想知道是否有一种方法可以加快我的 Julia 代码的速度，或者它此时是否运行得尽可能快(我的意思是我在使代码运行最快方面是否犯了任何明显的错误。 )

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 中进行一次转置可以提取更多性能，但这需要接触太多地方，而这篇文章已经足够长了。尝试微优化它让我使用

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 位整数。