将一项内容移动到集合的开头的最佳方法

Question

如果我有一个集合

let initial = [ "a", "b", "c", "d", "e" ]

我想将集合中的一个项目移动到开头（但保持其他项目的顺序不变）

let final = initial.placeFirst { $0 == "b" }
assert(final == [ "b", "a", "c", "d", "e" ])

什么是实现placeFirst的最佳方法？

我的示例具有Equatable元素 - 这只是为了使问题易读，但在现实生活中不幸的是不是这种情况，因此将谓词传递到placeFirst中，该谓词将为我想要的项目返回true。

对于我的用例，应该只有一个与谓词匹配的项目 - 如果有多个匹配项，则将任何（或一些或所有）匹配元素放在开头都可以。

我有一些想法，但似乎这是一种使用Collection / Sequence位的非常巧妙的解决方案，我还不知道。

PS我确实意识到这听起来很像作业问题 - 我保证这不是 :)

- deanWombourne

---

请澄清一下：是否可能有多个满足条件的元素？如果是，应该将第一个匹配的元素移动到前面，还是所有匹配的元素？ - Martin R

澄清一下 :) 只会有一个匹配元素 - 如果有多个匹配，哪一个（或多个）先出现都无所谓。 - deanWombourne

Answer 1

一个可能的实现方式是将其作为RangeReplaceableCollection的可变方法（Swift 3）：

extension RangeReplaceableCollection {
    mutating func placeFirst(where predicate: (Iterator.Element) -> Bool) {
        if let index = index(where: predicate) {
            insert(remove(at: index), at: startIndex)
        }
    }
}

例子：

var array = [ "a", "b", "c", "d", "e" ]
array.placeFirst(where: { $0 == "b" })
print(array) // ["b", "a", "c", "d", "e"]

与如何在Swift中对数组进行洗牌？相似，您可以添加一个非变异方法，接受任意序列并返回一个数组：

extension Sequence {
    func placingFirst(where predicate: (Iterator.Element) -> Bool) -> [Iterator.Element] {
        var result = Array(self)
        result.placeFirst(where: predicate)
        return result
    }
}

例子：

let initial = [ "a", "b", "c", "d", "e" ]
let final = initial.placingFirst { $0 == "b" }
print(final) // ["b", "a", "c", "d", "e"]

- Martin R

Answer 2

一种可能的实现方式是将其作为 MutableCollection 上的一对变异方法（不需要调整集合大小）：

extension MutableCollection {

    mutating func placeFirst(from index: Index) {

        var i = startIndex

        while i < index {
            swap(&self[i], &self[index]) // in Swift 4: swapAt(i, index)
            formIndex(after: &i)
        }
    }

    //                      in Swift 4, remove Iterator.
    mutating func placeFirst(where predicate: (Iterator.Element) throws -> Bool) rethrows {

        var i = startIndex

        while i < endIndex {
            if try predicate(self[i]) {
                placeFirst(from: i)
            }
            formIndex(after: &i)
        }
    }
}

var initial = ["a", "b", "c", "d", "e", "c", "q"]
initial.placeFirst(where: { $0 == "c" })
print(initial) // ["c", "c", "a", "b", "d", "e", "q"]

在 `placeFirst(from:)` 中，我们只需要一个单一的索引，并交换从起始索引到所需索引的所有元素，有效地将给定索引处的元素放置在开头，并将剩余的元素“向上移动”。

然后在谓词版本 `placeFirst(where:)` 中，我们遍历并检查集合的所有索引与谓词匹配，如果找到匹配项，则调用 `placeFirst(from:)`。

而且，正如 Martin 所说 的那样，可以通过先构造一个 `Array` 轻松创建所有序列的非变异变体。

extension Sequence {

    // in Swift 4, remove Iterator.
    func placingFirst(
        where predicate: (Iterator.Element) throws -> Bool
        ) rethrows -> [Iterator.Element] {

        var result = Array(self)
        try result.placeFirst(where: predicate)
        return result
    }
}

let initial = ["a", "b", "c", "d", "e", "c", "q"]
let final = initial.placingFirst(where: { $0 == "c" })
print(final) // ["c", "c", "a", "b", "d", "e", "q"]

---

为了与Martin的实现进行基准测试，我改变了我的placeFirst(where:)的实现，只考虑谓词匹配的第一个元素，以使两个实现都能短路：

extension MutableCollection {

    mutating func placeFirstSwap(from index: Index) {

        var i = startIndex

        while i < index {
            swapAt(i, index)
            formIndex(after: &i)
        }
    }

    mutating func placeFirstSwap(where predicate: (Iterator.Element) throws -> Bool) rethrows {

        if let index = try index(where: predicate) {
            placeFirstSwap(from: index)
        }
    }

}

extension RangeReplaceableCollection {
    mutating func placeFirstInsertRemove(where predicate: (Iterator.Element) throws -> Bool) rethrows {
        if let index = try index(where: predicate) {
            insert(remove(at: index), at: startIndex)
        }
    }
}

extension Sequence {
    func placingFirstInsertRemove(where predicate: (Iterator.Element) throws -> Bool) rethrows -> [Iterator.Element] {
        var result = Array(self)
        try result.placeFirstInsertRemove(where: predicate)
        return result
    }

    func placingFirstSwap(where predicate: (Iterator.Element) throws -> Bool) rethrows -> [Iterator.Element] {
        var result = Array(self)
        try result.placeFirstSwap(where: predicate)
        return result
    }
}

然后，在 Swift 4 发布版中使用以下设置：

import Foundation

let a = Array(0 ... 50_000_000)

let i = 33_000_000

print("pivot \(100 * Double(i) / Double(a.count - 1))% through array")

do {
    let date = Date()
    let final = a.placingFirstInsertRemove(where: { $0 == i })
    print(final.count, "Martin's:", Date().timeIntervalSince(date))
}

do {
    let date = Date()
    let final = a.placingFirstSwap(where: { $0 == i })
    print(final.count, "Hamish's:", Date().timeIntervalSince(date))
}

print("---")

do {
    let date = Date()
    let final = a.placingFirstInsertRemove(where: { $0 == i })
    print(final.count, "Martin's:", Date().timeIntervalSince(date))
}

do {
    let date = Date()
    let final = a.placingFirstSwap(where: { $0 == i })
    print(final.count, "Hamish's:", Date().timeIntervalSince(date))
}

当i约为33,000,000时，两种实现似乎具有类似的性能：

pivot 66.0% through array
50000001 Martin's: 0.344986021518707
50000001 Hamish's: 0.358841001987457
---
50000001 Martin's: 0.310263991355896
50000001 Hamish's: 0.313731968402863

在马丁的表现稍微好一些的情况下，例如当i=45,000,000时：

pivot 90.0% through array
50000001 Martin's: 0.35604602098465
50000001 Hamish's: 0.392504990100861
---
50000001 Martin's: 0.321934998035431
50000001 Hamish's: 0.342424035072327

我的表现略好于这个值以下的i，例如当i等于5_000_000时：

pivot 10.0% through array
50000001 Martin's: 0.368523001670837
50000001 Hamish's: 0.271382987499237
---
50000001 Martin's: 0.289749026298523
50000001 Hamish's: 0.261726975440979

在所有这些结果中，第二组通常更可靠，因为两个都应该受益于第一次运行时的分支预测。

- Hamish

---

我想知道如果将1000个元素的集合中的第300个元素移动到前面，哪种方法更快：将699个元素向左移动，然后将999个元素向右移动，还是交换299次相邻元素。 （但我现在没有时间进行基准测试！） - Martin R

@MartinR 我正准备进行基准测试 :) 待会儿告诉你。 - Hamish

@MartinR 看起来差别不大，但显然我的在靠前的元素上表现略好，而你的在靠后的元素上表现更好。 - Hamish