代码如下:
julia> function ≺(v₁::Vector{T}, v₂::Vector{T}) where T
v₁==v₂ && return 0
all(v₁.≤v₂) && return -1
all(v₂.≤v₁) && return 1
return 0
end
julia> function nds(sols::Vector{T}) where T
n = length(sols)
d_m, i_d = zeros(Int, n), [[] for _ in 1:n]
for p = 1:n-1, q = p+1:n
flag = sols[p] ≺ sols[q]
flag == -1 && (push!(i_d[p], q), d_m[q]+=1)
flag == 1 && (push!(i_d[q], p), d_m[p]+=1)
end
idx, fronts = 1, [findall(d_m .== 0)]
while length(fronts[idx]) ≠ 0
d_m[fronts[idx]] .-= 1
@simd for i in fronts[idx]
length(i_d[i])>0&&(d_m[i_d[i]] .-= 1)
end
push!(fronts, findall(d_m .== 0))
idx += 1
end
return fronts[1:end-1]
end
julia> sols = [rand(Float32, 3) for _ in 1:10000];
julia> @time nds(sols);
11.914778 seconds (242.02 M allocations: 12.337 GiB, 26.58% gc time)
# 大家平台可能跟我不一样,仅作参考
julia> versioninfo()
Julia Version 1.7.0-DEV.168
Commit dedf290c99 (2020-12-25 20:12 UTC)
Platform Info:
OS: Linux (x86_64-pc-linux-gnu)
CPU: Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-11.0.0 (ORCJIT, skylake)