Julia 中的布尔矩阵乘法

Question

我需要在 Julia 中将两个布尔矩阵相乘。

简单地做A*A或A^2返回一个 Int64 矩阵。

有没有办法有效地乘以布尔矩阵？

Answer 1

遵循 Oscarfor关于在代码周围添加两个循环的评论，但没有 LoopVectorization 改进，尽管没有在any调用中分配完整数组（以便any在第一次出现时停止），这是相当快的（编辑：&用 short替换标准 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)

Answer 2

一个非常简单的解决方案是

function bool_mul(A,B)
    return A*B .!= 0
end

这不会是最有效的，因为它会为 分配一个矩阵A*B，但最终可能会成为最快的解决方案之一。