algorithm - 在两个向量中寻找最接近的值

Question

假设我有两个已排序的 float 向量 - 我们称它们为 A 和 B。是否有一种聪明的方法来选择 A 的元素和 B 的元素，使得这些元素在所有对中的值最接近？现在我正在用两个循环强制执行它，但似乎应该有更好的方法。

Answer 1

这是演示:

julia> X=sort(rand(6)) # data example X
6-element Vector{Float64}:
 0.03229732486724901
 0.14661947289585864
 0.28060083090585386
 0.35640311556807047
 0.8995421870143288
 0.9063824527540892

julia> Y=sort(rand(5))  # data example Y (note: X and Y sizes can be different)
5-element Vector{Float64}:
 0.40423308422286974
 0.7126138483715454
 0.8721509236032997
 0.9193793976271042
 0.9827581490910492

julia> minimum( (abs(xi-yi) for xi in X, yi in Y) ) # a short, but O(N^2) approach
0.012996944873014948

julia> (d,i,j)=find_min_dist(X,Y) # <- the proposed solution (see code below)
(0.012996944873014948, 6, 4)

julia> abs(X[i]-Y[j]) # <- check that the 2 methods give the same result
0.012996944873014948

这是完整的代码:这不是那么短，抱歉。然而观察只有一次pass，复杂度为O(N)

function find_min_dist(X::AbstractVector{T}, Y::AbstractVector{T}) where {T<:AbstractFloat}
    @assert !isempty(X) && !isempty(Y)

    if Y[1]<X[1]
        (d,j,i) = find_min_dist(Y,X)
        return (d,i,j)
    end
    
    @assert issorted(X) && issorted(Y)
    
    X_n = length(X)
    Y_n = length(Y)

    min_dist = typemax(T)
    min_dist_X_i = 0
    min_dist_Y_j = 0
    
    i = 1
    j = 1

    @inbounds while i ≤ X_n
        # Find first j, such that Y[j] ≥ X[i]
        # and check dist(X[i],Y[j-1]) && dist(X[i],Y[j])
        #
        if (j ≤ Y_n) && (Y[j]<X[i])
            j+=1
        else
            if j > 1, 
               min_dist_candidate = abs(X[i]-Y[j-1])
               if min_dist > min_dist_candidate 
                   min_dist = min_dist_candidate
                   min_dist_X_i = i
                   min_dist_Y_j = j-1
               end
            end

            if j ≤ Y_n
               min_dist_candidate = abs(X[i]-Y[j])
               if min_dist > min_dist_candidate 
                   min_dist = min_dist_candidate
                   min_dist_X_i = i
                   min_dist_Y_j = j
               end
            end

            i+=1
        end
    end
    
    (min_dist,min_dist_X_i,min_dist_Y_j)
end 

这里有一些解释:

想法是在 X 和 Y 上循环一次并找到第一个 j 使得 Y[j] ≥ X [我]。为了不错过第一个 Y[1]，我们在必要时置换 X 和 Y。一旦 Y[j] ≥ X[i]，我们检查 dist(X[i],Y[j-1]) 和 dist(X [i],Y[j])。如果找到更好的 min_dist，我们会用定义最佳对的 i,j 索引记录它。

---

更新:length(X)=100 和 length(Y)=200

的基准

所有对比较:

julia> @benchmark minimum( (abs(xi-yi) for xi in $X, yi in $Y) )
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  36.840 μs … 197.413 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     37.811 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   41.021 μs ±   9.457 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

  ▇█ ▆  ▄  ▃          ▁▁▁    ▁▁▁▁                              ▂
  ██▄█▅▅██▃█▃▃▁▁▄▃▄▄█████████████████▇▇▆▇▇▆▅▇▆▅▆▅▆▅▅▅▅▆▅▅▅▆▆▆▅ █
  36.8 μs       Histogram: log(frequency) by time      81.7 μs <

 Memory estimate: 0 bytes, allocs estimate: 0.

使用 find_min_dist :

julia> @benchmark find_min_dist($X,$Y)
BenchmarkTools.Trial: 10000 samples with 181 evaluations.
 Range (min … max):  583.718 ns …   2.140 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     598.771 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   655.339 ns ± 134.850 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  █▇▄  ▂▁▁▂▂▂▃▃▃▁▁   ▁▁ ▁                                       ▁
  ███▇█████████████▇██████▆▆▇▇▇▇▇▇▇▇▇▇▆▇▆▆▆▇▆▆▆▆▅▆▅▆▅▅▆▅▅▄▅▄▃▄▄ █
  584 ns        Histogram: log(frequency) by time       1.26 μs <

 Memory estimate: 0 bytes, allocs estimate: 0.

建议的解决方案快 60 倍，您可以通过删除 @assert issorted 获得更多 yield 。