swift数组reversed()是否有效？

当你打电话的时候 reversed() 在swift中的数组上，您会得到一个reversecollection，它仅使用反向访问来 Package 原始数组。因此，这是非常有效的：

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索引Reversion的效率？

是的，索引由 Int 是不是让你失去了理智 O(1) 访问反向阵列。完全明白了！
正如你所注意到的， reversed() 这里是一个重载方法；在…上 Array 具体而言，您有两个定义可供选择： BidirectionalCollection.reversed() ，返回一个 ReversedCollection ，及 Sequence.reversed() ，它将任何序列转换为反向序列 [Element] 这里的重载最让人困惑 Array 它本身，因为它是唯一的 Sequence 打字使 type(of: x) == type(of: x.reversed()) .
swift类型检查器更喜欢更具体的重载，而不是不太具体的重载，因此一般来说，编译器将使用 BidirectionalCollection 重载而不是 Sequence 在可能的情况下。难点在于： BidirectionalCollection 具有不透明索引类型，不能使用 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输出有点太长，无法在此处复制，但目前，比较

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 完全 Package ，而 foo1 经历了明显更多的间接过程。

swift数组reversed()是否有效？

1条答案

相关问题

热门标签

最新问答