3

我需要对可变数量的数组有效地实现笛卡尔积。

我已经尝试过productfrom 的功能Iterators.jl，但性能欠佳。

我是一名 python 黑客，使用了 sklearn 的这个功能，并获得了良好的性能结果。

我曾尝试编写此函数的 Julia 版本，但无法产生与 python 函数相同的结果。

我的代码是：

function my_repeat(a, n)
    # mimics numpy.repeat
    m = size(a, 1)
    out = Array(eltype(a), n * m)
    out[1:n] = a[1]
    for i=2:m
        out[(i-1)*n+1:i*n] = a[i]
    end
    return out
end

function cartesian(arrs; out=None)
    dtype = eltype(arrs[1])

    n = prod([size(i, 1) for i in arrs])

    if is(out, None)
        out = Array(dtype, n, length(arrs))
    end

    m = int(n / size(arrs[1], 1))
    out[:, 1] = my_repeat(arrs[1], m)

    if length(arrs[2:]) > 0
        cartesian(arrs[2:], out=out[1:m, 2:])
        for j = 1:size(arrs[1], 1)-1
            out[(j*m + 1):(j+1)*m, 2:] = out[1:m, 2:]
        end
    end

    return out
end

我用以下方法测试它：

aa = ([1, 2, 3], [4, 5], [6, 7])
cartesian(aa)

返回值为：

12x3 Array{Float64,2}:
1.0  9.88131e-324  2.13149e-314
1.0  2.76235e-318  2.13149e-314
1.0  9.88131e-324  2.13676e-314
1.0  9.88131e-324  2.13676e-314
2.0  9.88131e-324  2.13149e-314
2.0  2.76235e-318  2.13149e-314
2.0  9.88131e-324  2.13676e-314
2.0  9.88131e-324  2.13676e-314
3.0  9.88131e-324  2.13149e-314
3.0  2.76235e-318  2.13149e-314
3.0  9.88131e-324  2.13676e-314
3.0  9.88131e-324  2.13676e-314

我相信这里的问题是当我使用这一行时：cartesian(arrs[2:], out=out[1:m, 2:])关键字参数out没有在递归调用中就地更新。

可以看出，我对这个函数的 Python 版本做了一个非常天真的翻译（见上面的链接）。很可能存在内部语言差异，使天真的翻译变得不可能。我不认为这是真的，因为来自 julia 文档的函数部分的引用：

Julia 函数参数遵循有时称为“传递共享”的约定，这意味着值在传递给函数时不会被复制。函数参数本身充当新的变量绑定（可以引用值的新位置），但它们引用的值与传递的值相同。在函数内对可变值（例如数组）所做的修改将对调用者可见。这与 Scheme、大多数 Lisps、Python、Ruby 和 Perl 以及其他动态语言中的行为相同。

我怎样才能使这个（或等效的）函数在 Julia 中工作？

4

3 回答 3

4

Base中有一个repeat函数。

更短更快的变体可能会使用@forcartesianCartesian 包中的宏：

using Cartesian

function cartprod(arrs, out=Array(eltype(arrs[1]), prod([length(a) for a in arrs]), length(arrs)))
    sz = Int[length(a) for a in arrs]
    narrs = length(arrs)
    @forcartesian I sz begin
        k = sub2ind(sz, I)
        for i = 1:narrs
            out[k,i] = arrs[i][I[i]]
        end
    end
    out
end

行的顺序与您的解决方案不同，但也许这并不重要？

于 2013-10-22T09:27:29.077 回答
3

我想到了。

这不是 Julia 没有就地更新函数参数的问题，而是 using slice operator 的问题a[ind]，它制作了数据的副本，而不是通过引用来索引我的数组。多维数组文档的这一部分给出 了答案：

SubArray 是 AbstractArray 的一种特殊形式，它通过引用而不是复制来执行索引。SubArray 使用 sub 函数创建，调用方式与 getindex 相同（使用数组和一系列索引参数）。sub 的结果看起来与 getindex 的结果相同，只是数据保留在原处。sub 将输入索引向量存储在 SubArray 对象中，该对象稍后可用于间接索引原始数组。

通过将此行更改为：

cartesian(arrs[2:], out=out[1:m, 2:])

到以下：

out_end = size(out, 2)
cartesian(arrs[2:], out=sub(out, 1:m, 2:out_end))
于 2013-10-21T17:21:00.920 回答
0

这是一个老问题，但随着 Julia 的进步，答案已经发生了变化。

基本问题是切片就像a[1:3,:]复制一样。如果您在函数中更新该副本，它对a自身没有影响。

现代的答案是用来@view a[1:3,:]获取对底层数组的一部分的引用。对此视图的更新将反映在底层数组中。

您可以强制整个代码块将视图语义与@views宏一起使用。

有关更多讨论，请参阅函数参数的就地更新。

于 2021-05-23T18:21:39.153 回答