julia - `UnitRange` 和 `Array` 有什么区别？

Question

我有两个版本的代码似乎做同样的事情:

sum = 0
for x in 1:100
    sum += x
end

sum = 0
for x in collect(1:100)
    sum += x
end

这两种方法之间有实际区别吗？

Answer 1

在 Julia ，1:100返回一个名为 UnitRange 的特定结构体看起来像这样:

julia> dump(1:100)
UnitRange{Int64}
  start: Int64 1
  stop: Int64 100

这是一个非常紧凑的结构，用于表示具有步骤 1 和任意(有限)大小的范围。 UnitRange是 AbstractRange 的子类型, 表示任意步长范围的类型，子类型 AbstractVector .
UnitRange的实例每当您使用 getindex 时动态计算它们的元素(或语法糖 vector[index] )。例如，使用 @less (1:100)[3]你可以看到这个方法:

function getindex(v::UnitRange{T}, i::Integer) where {T<:OverflowSafe}
    @_inline_meta
    val = v.start + (i - 1)
    @boundscheck _in_unit_range(v, val, i) || throw_boundserror(v, i)
    val % T
end

这是返回 i向量的第 -th 个元素添加 i - 1到范围的第一个元素 ( start )。部分函数有优化方法 UnitRange ，或者更一般地使用 AbstractRange .例如，使用 @less sum(1:100)你可以看到以下内容

function sum(r::AbstractRange{<:Real})
    l = length(r)
    # note that a little care is required to avoid overflow in l*(l-1)/2
    return l * first(r) + (iseven(l) ? (step(r) * (l-1)) * (l>>1)
                                     : (step(r) * l) * ((l-1)>>1))
end

此方法使用 formula for the sum of an arithmetic progression ，这是非常有效的，因为它在与向量大小无关的时间内进行评估。

另一方面， collect(1:100)返回一个普通的 Vector有一百个元素 1, 2, 3, ..., 100。与 UnitRange 的主要区别(或其他类型的 AbstractRange )是 getindex(vector::Vector, i) (或 vector[i] ，与 vector::Vector )不做任何计算，而只是访问 i - 向量的第 - 个元素。 Vector的缺点在 UnitRange是因为这个容器的元素是完全任意的，一般来说在使用它们时没有有效的方法，而 UnitRange表示一组具有特殊属性的数字(排序、恒定步长等)。

如果您比较 UnitRange 的方法的性能具有超高效的实现，这种类型将赢得胜利(注意在使用来自 $(...) 的宏时使用 BenchmarkTools 插入变量):

julia> using BenchmarkTools

julia> @btime sum($(1:1000_000))
  0.012 ns (0 allocations: 0 bytes)
500000500000

julia> @btime sum($(collect(1:1000_000)))
  229.979 μs (0 allocations: 0 bytes)
500000500000

请记住 UnitRange每次使用 getindex 访问元素时都会产生动态计算元素的成本.例如考虑这个函数:

function test(vec)
    sum = zero(eltype(vec))
    for idx in eachindex(vec)
        sum += vec[idx]
    end
    return sum
end

让我们用 UnitRange 对其进行基准测试和一个普通的 Vector :

julia> @btime test($(1:1000_000))
  812.673 μs (0 allocations: 0 bytes)
500000500000

julia> @btime test($(collect(1:1000_000)))
  522.828 μs (0 allocations: 0 bytes)
500000500000

在这种情况下，调用普通数组的函数比使用 UnitRange 的函数要快。因为它不必动态计算 100 万个元素。

当然，在这些玩具示例中，迭代 vec 的所有元素会更明智。而不是它的指数，但在现实世界的情况下，像这样的情况可能更明智。然而，最后一个例子显示了 UnitRange不一定比普通数组更有效，尤其是当您需要动态计算其所有元素时。 UnitRange当您可以利用可以在恒定时间内执行操作的专门方法(如 sum)时，s 会更有效。

作为文件备注，请注意，如果您最初拥有 UnitRange将其转换为普通格式不一定是个好主意 Vector以获得良好的性能，特别是如果您只使用一次或很少使用它，如转换为 Vector涉及范围内所有元素的动态计算和必要内存的分配:

julia> @btime collect($(1:1000_000));
  422.435 μs (2 allocations: 7.63 MiB)

julia> @btime test(collect($(1:1000_000)))
  882.866 μs (2 allocations: 7.63 MiB)
500000500000