arrays - Swift 数组 reversed()[n] 是否有效？

Question

当您调用 reversed()在 Swift 中的数组上，你会得到一个 ReverseCollection，它只是用反向访问包装原始数组。因此这是非常有效的:

let arr = [1,2,3,4]
for i in arr.reversed() { print(i) }

除了访问之外，实际上没有任何东西被逆转； reversed 的时间复杂度这是 O(1)。凉爽的!
但是当我索引到 reversed()通过一个整数并检查快速帮助，看来我已经失去了所有的效率；我看到了序列 reversed()生成一个新数组:

let arr = [1,2,3,4]
let i = arr.reversed()[1] // ???? this is a different `reversed()`!

这似乎是真的，因为 reversed()数组本身不支持按数字索引:

let arr = [1,2,3,4]
let rev = arr.reversed()
let i = rev[1] // compile error!

所以我的问题是:按数字索引到 reversed() 真的是真的吗？数组，如我的第二个示例，失去了 ReverseCollection 索引反转的效率？

Answer 1

是的，按 Int 编制索引导致你失去你的O(1)访问反向数组。相当的问题!
如您所见，reversed()这是一个重载的方法；在 Array具体来说，您有两个定义可供选择:

BidirectionalCollection.reversed() ，返回 ReversedCollection , 和

Sequence.reversed() ，它将任何序列转换为反转的 [Element]

这里的重载对于 Array 来说是最令人困惑的。本身，因为它是唯一的 Sequence输入 type(of: x) == type(of: x.reversed()) .
Swift 类型检查器更喜欢更具体的重载而不是不太具体的重载，所以一般来说，编译器将使用 BidirectionalCollection重载而不是 Sequence一个可能的。摩擦: BidirectionalCollection有一个 opaque index type ，并且不能使用 Int 进行索引;当您使用 Int 对集合进行索引时，编译器反而被迫选择 Sequence BidirectionalCollection 上的过载一。这也是您的第二个代码示例无法编译的原因:Swift 代码推断不考虑其他行的周围上下文；就其本身而言， rev最好是 ReversedCollection<Array<Int>> ，因此尝试使用 Int 对其进行索引失败。
您可以通过以下内容更清楚地看到这一点:

func collType1<T: Collection>(_: T) {
    print(T.self) // ReversedCollection<Array<Int>>
    print(T.Index.self) // Index
}

func collType2<T: Collection>(_: T) where T.Index == Int {
    print(T.self) // Array<Int>
    print(T.Index.self) // Int
}

let x: [Int] = [1, 2, 3]
collType1(x.reversed())
collType2(x.reversed())

以免您怀疑编译器是否可以在 Int 的事实时围绕此进行优化。基于索引的索引似乎没有任何其他副作用，在撰写本文时，答案似乎是“否”。 Godbolt output在这里复制有点太长了，但目前，比较

func foo1(_ array: [Int]) {
    if array.reversed()[100] > 42 {
        print("Wow!")
    }
}

和

func foo2(_ array: [Int]) {
    if array.reversed().dropFirst(100).first! > 42 {
        print("Wow!")
    }
}

启用优化显示 foo2执行直接数组访问

cmp     qword ptr [rdi + 8*rax + 24], 43

优化了 ReversedCollection完全包装，而 foo1经历了更多的间接。