Best way to move an item to the beginning of a collection
If I have a collection
let initial = [ "a", "b", "c", "d", "e" ]
and I wanted to move an item from this collection to the beginning (but don't keep the order of the rest of the items)
let final = initial.placeFirst { $0 == "b" }
assert(final == [ "b", "a", "c", "d", "e" ])
What would be the best way to implement it placeFirst
?
My example has elements like Equatable
- this is just to make the question readable, this is unfortunately not the case in real life, so the predicate went to placeFirst
, which will return true
for the element I want to start with.
In my use case, there should only be one element that matches the predicate - if there are multiple matches, then flagging any (or some or all) of the matching elements at the start would be fine.
I have a few ideas, but it looks like the problem would be a very neat solution that uses the Collection / Sequence bits. I do not know yet.
PS I do understand how much this sounds like homework - I promise it isn't :)
source to share
Possible implementation as a mutating method in 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)
}
}
}
Example:
var array = [ "a", "b", "c", "d", "e" ]
array.placeFirst(where: { $0 == "b" })
print(array) // ["b", "a", "c", "d", "e"]
As in How to shuffle an array in Swift? , you can add a non-mutating method that takes an arbitrary sequence and returns an array:
extension Sequence {
func placingFirst(where predicate: (Iterator.Element) -> Bool) -> [Iterator.Element] {
var result = Array(self)
result.placeFirst(where: predicate)
return result
}
}
Example:
let initial = [ "a", "b", "c", "d", "e" ]
let final = initial.placingFirst { $0 == "b" }
print(final) // ["b", "a", "c", "d", "e"]
source to share
Possible implementation as a pair of mutating methods on MutableCollection
(does not require changing the size of the collection):
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"]
In placeFirst(from:)
we just take one index and swap all the elements from the starting index to the desired index, effectively placing the element at the given index at the beginning and "shifting" the remaining elements up.
Then, in the predicate version, placeFirst(where:)
we iterate over and check the predicate against all indexes of the collection, calling on placeFirst(from:)
if we find a match.
And as Martin says , a non-mutating variant for all sequences can be easily created by first building 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"]
To make a comparison with Martin's implementation , I changed the implementation of mine placeFirst(where:)
to only consider the first item that matches the predicate, so both implementations are short -circuit:
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
}
}
Then with the following setup in Swift 4 assembly:
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))
}
When i
around 33_000_000
, both implementations have similar performance:
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
When Martin performs slightly better for values i
on this, for example with 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
and my performance is slightly better for values i
less than this, for example with 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
In all of these results, the second pair is generally more reliable, as both should benefit from the branch prediction performed by the first run.
source to share