julia - 为什么对 Julia 矩阵向量乘法强制执行顺序加快了？

Question

我试过以下。

a = randn(100,100);
b = randn(100,100);
c = randn(100,1);

@time a*b*c
@time a*(b*c)

结果

julia> @time a*b*c;
  0.000591 seconds (7 allocations: 79.234 KiB)

julia> @time a*(b*c);
  0.000101 seconds (6 allocations: 1.906 KiB)

结果与上述相当一致。虽然它确实可以直观地理解为什么第二个更好(矩阵向量乘法两次而不是大型矩阵矩阵乘法)。

我想知道，难道 Julia 不应该优化这个知道矩阵的维度并且它可以重新排序操作以优化它吗？或者我只是太懒了，或者我没有看到其他技术问题。

所以，这就是我使用 dump() 时得到的结果。在 (a*b*c)

  head: Symbol call
  args: Array{Any}((4,))
    1: Symbol *
    2: Array{Float64}((100, 100)) [0.290788 -0.0601455 … -0.408164 1.16261; -0.539274 -1.56979 … 2.56233 0.806247; … ; 1.30981 -1.31929 … 1.38655 -1.89169; -1.58483 0.318804 … -0.0500151 2.13105]
    3: Array{Float64}((100, 100)) [-0.464882 1.60371 … -0.390234 0.605401; -1.06837 0.296049 … 0.759708 0.0124688; … ; -0.149613 -1.38653 … 0.284494 1.47524; 0.34351 0.420449 … 0.544973 1.85736]
    4: Array{Float64}((100, 1)) [1.64066; 0.593296; … ; 0.908361; 0.486164]
  typ: Any

dump(a*(b*c))

Expr
  head: Symbol call
  args: Array{Any}((3,))
    1: Symbol *
    2: Array{Float64}((100, 100)) [0.290788 -0.0601455 … -0.408164 1.16261; -0.539274 -1.56979 … 2.56233 0.806247; … ; 1.30981 -1.31929 … 1.38655 -1.89169; -1.58483 0.318804 … -0.0500151 2.13105]
    3: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol *
        2: Array{Float64}((100, 100)) [-0.464882 1.60371 … -0.390234 0.605401; -1.06837 0.296049 … 0.759708 0.0124688; … ; -0.149613 -1.38653 … 0.284494 1.47524; 0.34351 0.420449 … 0.544973 1.85736]
        3: Array{Float64}((100, 1)) [1.64066; 0.593296; … ; 0.908361; 0.486164]
      typ: Any
  typ: Any

那么，假设运算符是关联的，是否存在试图优化此问题的问题？否则它会变得非常复杂或难以处理吗？

Answer 1

编辑:整个答案假设 *是 Julia 中的二元运算符。 这是不正确的因此，OP问题是完全有效的。见 https://discourse.julialang.org/t/is-there-any-way-to-make-custom-binary-infix-operators-right-associative/3202/5进行一些讨论(特别提到 * 被解析为 n-arry, which can be seen here )。我将在下面留下原始答案。

矩阵-矩阵乘法需要n^3步骤(对于小矩阵)。矩阵向量乘法需要n^2脚步。
a*b*c与 (a*b)*c 相同总共需要n^3+n^2操作，而 a*(b*c)需要2*n^2操作，因为它只包含矩阵向量乘法。

如果你想自动优化你的矩阵代数表达式，你可以试试像 https://github.com/Jutho/TensorOperations.jl 这样的库。 (该类型问题在谷歌上的第一次点击)。评论中提到的另一个选项是 https://github.com/AustinPrivett/MatrixChainMultiply.jl

至于为什么 Julia 不自动执行此操作:这必须是解析器的一部分(运算符的优先级)，但是您不希望解析器能够窥视运行时内部以了解对象是什么。另一方面，这当然可以通过前面提到的包在编译之前应用宏来实现。如果您使用一些编译时类型信息，也许这也是可行的，但是这对于 Julia 优雅的多调度机制中只有几个类型来说是一个相当丑陋的特例。