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通过添加i - 1到范围的第一个元素 ( start)来返回向量的第 -th 个元素。某些函数使用 优化了方法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

此方法使用算术级数之和的公式，该公式非常有效，因为它的计算时间与向量的大小无关。

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

如果您比较UnitRange具有超高效实现的方法的性能，这种类型将胜出（注意在使用$(...)from 宏时使用变量插值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

让我们用 aUnitRange和一个普通的来对它进行基准测试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

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

当然，在这些玩具示例中，迭代所有元素vec而不是其索引会更明智，但在现实世界中，像这样的情况可能更明智。然而，最后一个示例表明 aUnitRange不一定比普通数组更有效，尤其是当您需要动态计算其所有元素时。 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