Julia成对广播

广播是通过扩展(“广播”)不具有相同长度的维度来工作的,以使用NxKx1广播的(例如)大小为Nx1xM的阵列给出NxKxM阵列。

这意味着,如果您广播一个长度为N的向量的操作,您将获得一个长度N的向量。

所以你需要一个字符串数组是长度为N的向量,另一个是1xM矩阵:

julia> using Random

julia> str1 = [randstring('A':'C', 3) for _ in 1:5]
5-element Vector{String}:
 "ACC"
 "CBC"
 "AAC"
 "CAB"
 "BAB"

1.8.0> str2 = [randstring('A':'C', 3) for _ in 1:4]
4-element Vector{String}:
 "ABB"
 "BAB"
 "CAA"
 "BBC"

1.8.0> str1 .== permutedims(str2)
5×4 BitMatrix:
 0  0  0  0
 0  0  0  0
 0  0  0  0
 0  0  0  0
 0  1  0  0

permutedims 将长度N矢量改变为1xN矩阵。

顺便说一句,你很少使用 broadcast 在您的代码中( broadcast(==, a, b) ),而是使用点语法, a .== b ,这更地道。

您应该将一个向量转换为广播机制,通过扩展输入的维度来构建矩阵。

julia> str_list = ["hello", "car", "me", "good", "people", "good"];

julia> equal_strs = broadcast(==, str_list, permutedims(str_list))
6×6 BitMatrix:
 1  0  0  0  0  0
 0  1  0  0  0  0
 0  0  1  0  0  0
 0  0  0  1  0  1
 0  0  0  0  1  0
 0  0  0  1  0  1

此外,以下内容也类似。

equal_strs = str_list .== permutedims(str_list)
equal_strs = isequal.(str_list, permutedims(str_list))

假设“list”指的是Vector,因为Julia中没有类似python的列表。如果你指的是元组,我建议无论如何都将其转换为Vector,因为广播最好与Arrays(Vector是其子类型)一起使用。

str_list = ["one", "two", "three", "one", "two"]

现在你只需要

broadcast(==, str_list, permutedims(str_list))

或使用点运算符更简洁

str_list .== permutedims(str_list)

引擎盖下发生了什么:

Julia中的广播在元素方面起作用,所以如果您有2个矢量,它将不会做任何事情,因为维度匹配。

但是如果你有一个向量和一个矩阵 (矢量是1D阵列,矩阵是2D阵列) 形状 (N,1) 和 (1,N) Julia将播放 1 尺寸给你一个形状矩阵 (N,N) 这就是你想要的。

现在通常用数字 ' 而不是 permutedims

num_list .== num_list'

至于为什么它不适用于字符串,请参阅 this answer 。

lst .== permutedims(lst) 正如其他答案所建议的那样,这是一个非常好的方法来找到结果。但它需要O(n^2)个比较,如果列表很长,则最好使用O(n*log(n))个比较算法。下面是这样一个带有一点基准的算法的实现:

function equal_str(lst)
    sp = sortperm(lst)
    isp = invperm(sp)
    same = [i==1 ? false : lst[sp[i]]==lst[sp[i-1]] for i=1:length(lst)]
    ac = accumulate((k,v)-> ifelse(v==false, k+1, k), same; init=0)
    return [ ac[isp[i]]==ac[isp[j]] for i=1:length(lst),j=1:length(lst) ]
end

基准给出:

julia> using Random

julia> using BenchmarkTools

julia> lst = [randstring('A':'C',3) for i=1:40];

julia> show(lst)
["CBA", "CAB", "BCA", "AAC", "AAA", "ABC", "BBA", "CAB", "CBC", "CCA",
 "BCC", "BCB", "CAB", "BCB", "ACC", "CBC", "CCC", "CCB", "BCB", "BCB", 
 "ABA", "AAC", "CCC", "ABC", "BAC", "CAB", "BAB", "BCB", "CCA", "CAC", 
 "AAA", "BBC", "ABC", "BCB", "CBA", "CAA", "CAB", "CAC", "CBC", "CBC"]

julia> @btime $lst .== permutedims($lst) ;
  9.025 μs (5 allocations: 4.58 KiB)

julia> @btime equal_str($lst) ;
  6.112 μs (8 allocations: 3.08 KiB)

越大 lst 差异就越大。正如OP所建议的,这只适用于将列表与其本身进行比较。为了比较两个列表,对于O(n*log(n))时间应该使用不同的算法。

最后,即使这种算法在排序方面也有点过于困难,但产生结果时固有的时间/空间复杂性为O(n^2)。

更新: 一个更线性的O(n)时间计算(仍然是O(n^2)来制作矩阵):

function equal_str_2(lst)
    d = Dict{String,Int}()
    d2 = Dict{Int, Vector{Int}}()
    for p in pairs(lst)
        if haskey(d,p[2])
            push!(d2[d[p[2]]],p[1])
        else
            d[p[2]] = p[1]
            d2[p[1]] = [p[1]]
        end
    end
    res = zeros(Bool, (length(lst), length(lst)))
    for p in values(d2)
        for q in Iterators.product(p,p)
            res[q[1],q[2]] = true
            res[q[2], q[1]] = true
        end
    end
    return res
end

与更大的 lst :

julia> lst = [randstring('A':'C',3) for i=1:140];

julia> @btime $lst .== permutedims($lst) ;
  99.094 μs (5 allocations: 6.89 KiB)

julia> @btime equal_str($lst) ;
  51.981 μs (9 allocations: 23.12 KiB)

julia> @btime equal_str_2($lst) ;
  21.539 μs (72 allocations: 27.47 KiB)