俺也搞不清楚怎么能这么慢，profiler的结果看不太懂，这两个函数地方花的时间比较久
还有消耗的时间就是在判断in 和notin上了
我感觉可能的问题是在搜neighbor cell的时候有重复，是否应该先对cell进行排序？
另一方面，存点对的时候用set类型？
破案了! 原因是搜索Neighbor Cell的时候有重复，所以有很多时间花在判断点对是否重复上面。
把neighbor cell改成forward cell以后，两个cell不会重复比较所以没有重复点对，因此不需要判断是否重复，这样修改以后程序速度起飞，是forloop的20倍！下面是修改后的代码：
# fied-radius nearest neighbor
#cell list algorithm
function FRNNMain(NumNod::Int64,Dim::Int64,A::Array{Float64,2},s::Float64)
PoiPair = Array{Tuple{Int64,Int64},1}(undef,1)
popfirst!(PoiPair)
Cell = PoiCell(A,NumNod,s)
for key in keys(Cell)
vaule = Cell[key]
InnerCellPair!(vaule,PoiPair,A,s)
LoopNeighbor!(key,Cell,PoiPair,A,s)
end
return PoiPair
end
function PoiCell(A::Matrix{Float64},NumNod::Int64,s::Float64)
Cell = Dict{Tuple{Int64,Int64},Array{Int64,1}}()
for i = 1:1:NumNod
x = fld(A[1,i],s)
y = fld(A[2,i],s)
z = (x,y)
if z ∉ keys(Cell)
Cell[z] = [i]
else
push!(Cell[z],i)
end
end
return Cell
end
function GetForwardCell(key::Tuple{Int64,Int64})
NeiCell = Array{Tuple{Int64,Int64}}(undef,4,1)
NeiCell[1] = (key[1]+1,key[2])
NeiCell[2] = (key[1],key[2]-1)
NeiCell[3] = (key[1]+1,key[2]-1)
NeiCell[4] = (key[1]+1,key[2]+1)
return NeiCell
end
function InnerCellPair!(value::Array{Int64},PoiPair::Array{Tuple{Int64,Int64},1},A::Matrix{Float64},s::Float64)
Len = length(value)
if Len >= 2
for i = 1:Len-1
for j = i+1:Len
AddorNot!(value[i],value[j],A,s,PoiPair)
end
end
end
return PoiPair
end
function LoopNeighbor!(key::Tuple{Int64,Int64},Cell::Dict{Tuple{Int64,Int64},Array{Int64,1}},PoiPair::Array{Tuple{Int64,Int64},1},A::Array{Float64,2},s::Float64)
NeiCell = Array{Tuple{Int64,Int64}}(undef,3,1)
NeiCell = GetForwardCell(key)
for i = 1:4
if NeiCell[i] ∈ keys(Cell)
FindPair!(Cell[key],Cell[NeiCell[i]],PoiPair,A,s)
end
end
return PoiPair
end
function FindPair!(value::Array{Int64},value1::Array{Int64},PoiPair::Array{Tuple{Int64,Int64},1},A::Array{Float64,2},s::Float64)
for P1 in value
for P2 in value1
AddorNot!(P1,P2,A,s,PoiPair)
end
end
return PoiPair
end
function Distance(Point1::Array{Float64,1},Point2::Array{Float64,1})
Dist = (Point1[1]-Point2[1])^2+(Point1[2]-Point2[2])^2::Float64
return Dist
end
function AddorNot!(P1::Int64,P2::Int64,A::Matrix{Float64},s::Float64,PoiPair::Array{Tuple{Int64,Int64},1})
Dist::Float64 = (A[1,P1]-A[1,P2])^2+(A[2,P1]-A[2,P2])^2
if Dist <= s*s
push!(PoiPair,(P1,P2))
end
return PoiPair
end
NumNod = 1000
Dim = 2
A = rand(Dim,NumNod)
s = 0.1;
a = FRNNMain(NumNod,Dim,A,s)
下面是运行结果
For Loop
0.123814 seconds (21 allocations: 33.001 MiB, 3.29% gc time)
0.122190 seconds (21 allocations: 33.001 MiB)
0.122234 seconds (21 allocations: 33.001 MiB)
0.127930 seconds (21 allocations: 33.001 MiB, 2.76% gc time)
0.122368 seconds (21 allocations: 33.001 MiB)
0.123387 seconds (21 allocations: 33.001 MiB)
0.126333 seconds (21 allocations: 33.001 MiB, 3.64% gc time)
0.124472 seconds (21 allocations: 33.001 MiB)
0.125733 seconds (21 allocations: 33.001 MiB)
0.126474 seconds (21 allocations: 33.001 MiB, 2.66% gc time)
Cell List
0.062398 seconds (932 allocations: 33.254 MiB, 12.83% gc time)
0.058075 seconds (932 allocations: 33.254 MiB, 7.76% gc time)
0.051575 seconds (933 allocations: 33.256 MiB)
0.059760 seconds (931 allocations: 33.252 MiB, 9.79% gc time)
0.054577 seconds (931 allocations: 33.252 MiB, 5.11% gc time)
0.052947 seconds (932 allocations: 33.254 MiB)
0.060222 seconds (931 allocations: 33.252 MiB, 8.65% gc time)
0.055781 seconds (931 allocations: 33.252 MiB, 5.34% gc time)
0.051754 seconds (931 allocations: 33.252 MiB)
0.058636 seconds (932 allocations: 33.254 MiB, 12.72% gc time)
直接起飞鸭！
4 个赞
这个for里面还可以优化。不确定GetNeighborCell是否被编译器优化了。