最佳方式

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 

在所有這些結果，第二對總體上是更可靠的，因爲兩者都應該從做的分支預測中獲益第一次運行。