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

html5 • • 问答

当你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 索引反转的效率吗？

回答

是的，索引方式Int会导致您无法O(1)访问反向数组。相当的问题！

正如您所注意到的，reversed()这是一个重载方法；关于Array具体而言，你有两种定义可供选择：

  1. BidirectionalCollection.reversed(), 返回 a ReversedCollection, 和
  2. Sequence.reversed()，这将任何序列变成一个反向 [Element]

这里的重载Array本身是最令人困惑的，因为它是唯一Sequence这样的类型type(of: x) == type(of: x.reversed())。

Swift 类型检查器更喜欢更具体的重载而不是不太具体的重载，所以一般来说，编译器会尽可能使用BidirectionalCollection重载而不是重载Sequence。rub:BidirectionalCollection具有不透明的索引类型，不能使用Int;进行索引。当您使用对集合进行索引时Int，编译器将被迫选择Sequence重载而不是重载BidirectionalCollection。这也是您的第二个代码示例无法编译的原因：Swift 代码推理不考虑其他行上的周围上下文；就其本身而言，rev首选是 a ReversedCollection<Array<Int>>，因此尝试使用 an 对其进行索引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基于 -based 索引的事实似乎没有任何其他副作用的情况下对此进行优化，在撰写本文时，答案似乎是否定的。该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

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

以上是Swift数组reversed()[n]是否有效？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>