最佳方式

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因为我想在开始的项目。

对于我的使用情况下，应该只有一个项目相匹配的断言 - 如果超过一个匹配，那么在开始把任何（或部分或全部）的匹配元素被罚款。

我有一些想法，但似乎喜欢那种问题会有其采用集合/序列的位，我不知道的又一个非常巧妙的解决办法。

PS我不知道这个听起来像一个家庭作业的问题 - 我保证这不是:)

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"] 

类似的How do I shuffle an array in 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"] 

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:)，我们只采取单一的指标，并交换所有从一开始就指数最高的元素所需指标，有效地将元素给定索引处开始，“市fting”剩余的元素了。

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

而且as Martin says，所有序列的非不同诱变的变体可以通过先构造一个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's implementation标杆，我改变了我的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 
    } 
} 

然后，在斯威夫特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的值在此之上，例如与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 

在所有这些结果，第二对总体上是更可靠的，因为两者都应该从做的分支预测中获益第一次运行。