Julia 中的 boolean 矩阵乘法

Question

我需要在 Julia 中将两个 boolean 矩阵相乘。
做简单的A*A或 A^2返回一个 Int64 矩阵。
有没有办法有效地乘以 boolean 矩阵？

Answer 1

继奥斯卡评论添加两个 for围绕您的代码循环，但没有 LoopVectorization 改进，尽管没有在 any 内分配完整数组调用(以便 any 在第一次出现时停止)，这是相当快的(编辑:替换标准 AND & 与短路 && ):

function bool_mul2(A, B)
    mA, nA = size(A)
    mB, nB = size(B)
    nA ≠ mB && error()
    AB = BitArray(undef, mA, nB)
    for i in 1:mA, j in 1:nB
        AB[i,j] = any(A[i,k] && B[k,j] for k in 1:nA)
    end
    AB
end

(注意我删除了 [ 中的 ] 和 any 以不分配到那里。
例如，使用 A和 B大小为 1000×1000，我得到

julia> @btime bool_mul2($A, $B) ;
  16.128 ms (3 allocations: 122.25 KiB)

相比

julia> @btime bool_mul($A, $B) ;
  346.374 ms (12 allocations: 7.75 MiB)

编辑:为了平方矩阵，也许尝试

function bool_square(A)
    m, n = size(A)
    m ≠ n && error()
    A² = BitArray(undef, n, n)
    for i in 1:n, j in 1:n
        A²[i,j] = any(A[i,k] && A[k,j] for k in 1:n)
    end
    A²
end

我得到

julia> A = rand(Bool, 500, 500) ;

julia> @btime $A * $A .!= 0 ;
  42.483 ms (12 allocations: 1.94 MiB)

julia> @btime bool_square($A) ;
  4.653 ms (3 allocations: 30.69 KiB)