从三元组 (obj, obj, distance/simularity) 在 Julia 中创建成对距离矩阵

Question

我有一个矩阵，其形式为“obj obj distance”，玩具矩阵如下所示：

r = [[1,1,1,2,2,2,3,3,3]  [1,2,3,1,2,3,1,2,3]  [0,.5,.75,.75,0,.25,.5,.25,0]]

我目前有一个解决方案：

using NamedArrays

function DistanceMatrixFromTriColumn(r::AbstractArray)
               Names = unique(vcat(r[:,1],r[:,2]))
               Dist = NamedArray(zeros(length(Names),length(Names)),(Names,Names))
               for row in Names
                       for col in Names
                               Dist[row,col] = r[(r[:,1] .== row) .& (r[:,2] .== col),:3][1]
                       end
               end
               return Dist
       end

DistanceMatrixFromTriColumn(r)

这实际上只是一个嵌套的 for 循环，先遍历第一列，然后再遍历第二列。它输出如下内容：

3×3 Named Matrix{Float64}
A ╲ B │  1.0   2.0   3.0
──────┼─────────────────
1.0   │  0.0   0.5  0.75
2.0   │ 0.75   0.0  0.25

但我认为有更快的方法，应该有一种方法可以使用索引来做类似的事情，不是吗？我想我记得曾经看到有人在 R 中做过类似的解决方案。

Answer 1

有了R，就可以用xtabs

> xtabs(z ~ ., r)
   B
A      1    2    3
  1 0.00 0.50 0.75
  2 0.75 0.00 0.25
  3 0.50 0.25 0.00

数据

r <- data.frame(
    A = c(1, 1, 1, 2, 2, 2, 3, 3, 3),
    B = c(1, 2, 3, 1, 2, 3, 1, 2, 3),
    z = c(0, .5, .75, .75, 0, .25, .5, .25, 0)
)

Answer 2

对于您发布的对象已可靠编号的情况，您可以使用类似

的方法来加快速度

function distancematrixfromtricolumn(r::AbstractArray)
    names = unique(view(r,:,1))
    dist = NamedArray(zeros(length(names),length(names)),(names,names))
    for i = 1:size(r,1)
        row = Int(r[i,1])
        col = Int(r[i,2])
        dist[row,col] = r[i,3]
    end
    return dist
end

您可能还会注意到一些风格上的变化：我将一些名称改为小写，以遵循 Julia 约定，函数和变量是小写的，而模块和类型是 CamelCase。

比较两个版本：

julia> distancematrixfromtricolumn(r)
3×3 Named Matrix{Float64}
A ╲ B │  1.0   2.0   3.0
──────┼─────────────────
1.0   │  0.0   0.5  0.75
2.0   │ 0.75   0.0  0.25
3.0   │  0.5  0.25   0.0

julia> DistanceMatrixFromTriColumn(r) == distancematrixfromtricolumn(r)
true

julia> using BenchmarkTools

julia> @benchmark DistanceMatrixFromTriColumn($r)
BenchmarkTools.Trial: 10000 samples with 8 evaluations.
 Range (min … max):  3.897 μs … 535.305 μs  ┊ GC (min … max): 0.00% … 98.80%
 Time  (median):     4.863 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   5.828 μs ±  16.267 μs  ┊ GC (mean ± σ):  9.92% ±  3.54%

    ▂▆▇█▇▇▅▃▁
  ▃▅█████████▇▇▇▆▅▅▆▅▅▄▃▃▂▂▂▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁ ▃
  3.9 μs          Histogram: frequency by time        10.6 μs <

 Memory estimate: 7.39 KiB, allocs estimate: 73.

julia> @benchmark distancematrixfromtricolumn($r)
BenchmarkTools.Trial: 10000 samples with 10 evaluations.
 Range (min … max):  1.352 μs … 528.474 μs  ┊ GC (min … max): 0.00% … 99.32%
 Time  (median):     1.543 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   1.821 μs ±   8.510 μs  ┊ GC (mean ± σ):  8.04% ±  1.72%

   ▇█▄▁▁▁
  ███████▆▆▆▅▄▃▃▃▃▂▂▂▂▃▃▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▂▁▁▁▁▁▁▁▁▁ ▂
  1.35 μs         Histogram: frequency by time        3.33 μs <

 Memory estimate: 2.08 KiB, allocs estimate: 25.

虽然原则上还有其他一些事情可以考虑使 for 循环更快，但此时我们的大部分执行时间和所有分配都来自对 unique 和 NamedArray.

的构造

从三元组 (obj, obj, distance/simularity) 在 Julia 中创建成对距离矩阵

Creating a pairwise distance matrix in Julia from triplets (obj, obj, distance/simularity)

r

multidimensional-array

julia

distance-matrix