5

为了激发我的问题，考虑在 Julia中处理元素类型的锯齿状数组（为简单起见）时的情况。Int有两种存储方式：

  1. 作为Vector{Vector{Int}}
  2. 作为Vector{Union{Vector{Int}, Int}}（特别是，如果希望存储足够多的一元向量）

我的问题是哪一个更高效/更快/更好？

要回答这个问题，除其他外，我需要知道它们是如何存储在内存中的。即：

  1. 我认为 type 的变量Vector{Vector{Int}}将被视为同类类型数组，因此我希望它连续存储在内存中，因此对 cpu-cache 更友好。我对吗？还是连续性仅适用于元素数据类型为原始的数组？

  2. 一种类型的变量是否会Vector{Union{Vector{Int}, Int}}被视为异构数组，因此不会 连续存储在内存中？

  3. 将内存中连续表示的好处与没有数组容器用于 1 元素数组成员的好处相比，即将它们存储为原始数据类型（Int在这种情况下）？哪一种效率更高？

4

1 回答 1

9

T如果isbits(T)为真，Julia 的数组将只存储 unboxed 类型的元素。也就是说，元素必须既不可变又无指针。查看元素是否立即存储的一种简单方法是分配一个未初始化的数组。未装箱（立即）值的连续数组会有乱码：

julia> Array(Int, 3)
3-element Array{Int64,1}:
 4430901168
 4470602000
 4430901232

而非 isbits 类型的数组将具有#undef指针：

julia> Array(Vector{Int}, 3)
3-element Array{Array{Int64,1},1}:
 #undef
 #undef
 #undef

想象一下，如果后者返回一个连续的Ints 块会发生什么。它怎么知道做多大？或者一个向量在哪里停止而下一个向量在哪里开始？这将取决于向量的大小，目前尚不清楚。

AVector{Union{Vector{Int}, Int}}将类似地将其元素存储为指针；这次是因为 Julia 不知道如何解释每个内联元素（它应该像整数还是像数组一样读取内存？）。它还有一个额外的缺点，那就是 Julia 不再知道它会从索引返回什么类型。这是一种类型不稳定性，而且性能肯定会比仅使用单元素向量差得多。

可以创建自己的参差不齐的数组类型来内联存储其元素，但是让它像普通数组一样与标准库一起使用是非常棘手的，因为它打破了许多关于索引如何工作的假设。你可以看看我的最新尝试：RaggedArrays.jl。您可以在Issue#2中看到我如何将其与之前的努力进行比较。

于 2016-01-13T15:50:45.870 回答