Swift数组反转()[n]是否有效？

Question

在Swift中对数组调用reversed()时，会得到一个ReverseCollection，它只是用reversed Access包装原始数组。因此，这是非常有效的：

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

除了访问之外，没有什么东西实际上被逆转了；这里reversed的时间复杂度为O(1)。酷！

但是，当我按整数索引到reversed()并检查Quick Help时，我似乎失去了所有的效率；向我展示了序列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()是一个重载的方法；在数组上，有两个定义可供选择：

1. BidirectionalCollection.reversed()，它返回reversedCollection和
2. sequence.reversed()，它将任何序列转换为反向的[Element]

这里的重载对于数组本身来说是最令人困惑的，因为它是序列类型中唯一的类型(of:x)==type(of:x.reversist())。

Swift类型检查器更喜欢更特定的重载，而不是更不特定的重载，因此一般情况下，编译器将尽可能使用BidirectionalCollection重载，而不是Sequence重载。rub:BidirectionalCollection具有不透明的索引类型，不能使用int进行索引；当使用int索引到集合时，编译器将被迫选择sequence重载而不是bidirectionalcollection重载。这也是第二个代码示例编译失败的原因：Swift代码推断不考虑其他行的周围上下文；就其本身而言，rev首选为reversedCollection > ，因此试图用int索引到它将失败。

您可以通过以下内容更清楚地看到这一点：

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

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

let x: [Int] = [1, 2, 3]
seqType1(x.reversed())
seqType2(x.reversed())

当基于int的索引似乎没有任何其他副作用时，为了避免您怀疑编译器是否可以围绕这一点进行优化，在编写本文时，答案似乎是“否”。Godbolt的输出有点太长，不能在这里复制，但目前，比较

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