function nds2(sols::Vector{T}) where T
n = length(sols)
d_m= zeros(Int, n)
i_d= falses(n,n) # BitArray
for p = 1:n-1, q = p+1:n
flag = sols[p] ≺ sols[q]
if flag ==-1
i_d[q,p]=true
# 这里写 [q,p] 是为了 qs=findall(i_d[:,i])快一些,
# 要是这里写 [p,q], 就得写 qs=findall(i_d[i,:]) 会更慢。
d_m[q]+=1
end
if flag == 1
i_d[p,q]=true
d_m[p]+=1
end
end
idx, fronts = 1, [findall(d_m .== 0)]
while length(fronts[idx]) ≠ 0
d_m[fronts[idx]] .-= 1
@simd for i in fronts[idx]
if any(i_d[:,i])
qs=findall(i_d[:,i])
d_m[qs] .-= 1
end
end
push!(fronts, findall(d_m .== 0)) # 这一段 while 还在看怎么改。
idx += 1
end
return fronts[1:end-1]
end
function nds3(sols::Vector{T}) where T
n = length(sols)
d_m= zeros(Int, n)
i_d= falses(n,n)
for p = 1:n-1, q = p+1:n
flag = sols[p] ≺ sols[q]
if flag ==-1
i_d[q,p]=true
d_m[q]+=1
end
if flag == 1
i_d[p,q]=true
d_m[p]+=1
end
end
fronts=zeros(Int,length(d_m), length(d_m))
idx=1
tmp=findall(d_m .== 0)
ll=length(tmp)
@simd for i in 1:ll
fronts[i,idx]=tmp[i]
end
while any(fronts[:,idx].>0)
d_m[fronts[1:ll,idx]].-=1
@simd for i in fronts[1:ll,idx]
if any(i_d[:,i])
qs=findall(i_d[:,i])
d_m[qs] .-= 1
end
end
idx += 1
tmp=findall(d_m .== 0)
ll=length(tmp)
@simd for i in 1:length(tmp)
fronts[i,idx]=tmp[i]
end
end
return fronts[:,1:idx-1]
end
其实我还想把第一个 for 循环改成这样的,改成这样之后速度能到5s多,但是结果不对。不知道我的理解是不是不太对,我感觉这里是顺序无关的啊。
5.185270 seconds (188.32 M allocations: 12.180 GiB, 57.94% gc time)
Threads.@threads for p = 1:n-1
for q = p+1:n
flag = sols[p] ≺ sols[q]
if flag ==-1
i_d[q,p]=true
d_m[q]+=1
end
if flag == 1
i_d[p,q]=true
d_m[p]+=1
end
end
end