Optimising the functional approach
Iterative vs functional approach: Is it possible to use the (existing) functional methods without losing performance?
I don't think it's possible to use the standard library's existing collection methods without losing performance here – as I go onto investigate, there are quite a few inefficiencies with them. We can however make quite a few improvements by defining methods of our own to bring the performance close to the iterative approach.
For your implementation of the mutable version of permute() that uses the existing standard library collection methods:
extension Array where Element: Comparable { mutating func permute2() -> Bool { // Nothing to do for empty or single-element arrays: if count <= 1 { return false } // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j // exists. guard let j = indices.reversed().dropFirst() .first(where: { self[$0] <= self[$0 + 1] }) else { return false } // L3: Find last l such that self[j] <= self[l], then exchange elements j and l: let l = indices.reversed() .first(where: { self[j] <= self[$0] })! swap(&self[j], &self[l]) // L4: Reverse elements j+1 ... count-1: replaceSubrange(j+1..<count, with: self[j+1..<count].reversed()) return true } }
This gives me a benchmark time down of ~2.65 seconds (running it with a Swift 3.1 -O build). Here's some improvements we can make to reduce this time...
Reversing a slice
The first thing that stands out to me is the line:
replaceSubrange(j+1..<count, with: self[j+1..<count].reversed())
The problem with this is that self[j+1..<count].reversed() returns a reversed view onto the ArraySlice – which in turn has a view onto the array's buffer. Therefore when you come to call replaceSubrange, the array's buffer is not uniquely referenced. This therefore forces a copy of the array, which is a costly operation to be doing at every call of permute().
One nice syntactic (and a slight performance) improvement over this would be to instead call reverse() on the ArraySlice itself:
self[j + 1 ..< count].reverse()
Note that I've added whitespace around the binary operators, which I think makes it much more readable.
Performance-wise this is slightly better because we're now mutating (a temporary) ArraySlice, before re-assigning it to back to Array's subscript – therefore now only the slice itself needs to be copied (not the entire array).
This brings my benchmark time down from ~2.65 seconds to ~2.06 seconds.
However, we're still doing an unnecessary copy (although really I think the compiler should be able optimise this away and mutate the array directly – but this doesn't currently appear to be the case).
One way in order to allow us to mutate the array directly, rather than going through ArraySlice is to simply define a method to reverse the elements of an array between two given indices:
extension Array {
/// Reverses the elements of the collection within a given range of indices.
///
/// - Parameter indices: A range of valid indices of the collection,
/// the elements of which will be reversed.
///
mutating func reverse(indices: Range<Index>) {
if indices.isEmpty { return }
var low = indices.lowerBound
var high = index(before: indices.upperBound)
while low < high {
swap(&self[low], &self[high])
formIndex(after: &low)
formIndex(before: &high)
}
}
}
This implementation is based off the standard library's own reverse() method. Note that it may be more natural to express the indices parameter as a ClosedRange, due to the fact that the range should never be empty – however for increased interoperability, I would simply suggest adding this as another overload for this, if desired.
It's also worth noting that in practise, I would consider defining this as an extension of
MutableCollection where Self : BidirectionalCollection, rather than Array. However, unfortunately, it appears to compiler is unable to specialise its implementation when doing so, which leads to reduced performance.
But regardless of these details, now we can say:
reverse(indices: j + 1 ..< count)
Which brings my benchmark time down from ~2.06 seconds to ~1.46 seconds.
If we're going for maximal performance here, we can also use Range's init(uncheckedBounds:) initialiser to skip the precondition check that lowerBound <= upperBound, given that we know
j + 1 < count (as the maximum value of j is count - 2).
reverse(indices: Range(uncheckedBounds: (lower: j + 1, upper: count)))
This brings my benchmark time down from ~1.46 seconds to ~1.45 seconds. However, we're still way off the target benchmark time of ~0.02 seconds for your original mutating version of permute().
Optimising first(where:)
The major bottleneck here appears to be with Sequence's first(where:) method. If we take a look at its implementation, we can see it's implemented as:
internal enum _StopIteration : Error {
case stop
}
// ...
extension Sequence {
public func first(
where predicate: (Iterator.Element) throws -> Bool
) rethrows -> Iterator.Element? {
var foundElement: Iterator.Element?
do {
try self.forEach {
if try predicate($0) {
foundElement = $0
throw _StopIteration.stop
}
}
} catch is _StopIteration { }
return foundElement
}
}
As first glance, this looks insane. Using forEach(_:) and a throwing a dummy Error type to exit the loop?
Turns out this is an attempted optimisation by the standard library team in order to allow for sequences to implement their own version of forEach(_:) in a more efficient manner than iterating over their iterator. This is discussed in both SR-3166 and this (closed) pull request.
However, unfortunately, this implementation of first(where:) is causing a big performance bottleneck for our implementation of permute(). From what I can tell, the main suspect appears to be the throwing of the _StopIteration error, which involves the wrapping in an existential Error container.
A simple fix to this problem is to define our own first(where:) method that just uses a for-in loop for random-access collections. This allows us to take advantage of a more performant version of the method, while still allowing for complicated non-random-access collections to have a first(where:) implementation that uses their (potentially) customised forEach(_:) implementation.
extension RandomAccessCollection {
func first(where predicate: (Iterator.Element) throws -> Bool) rethrows -> Iterator.Element? {
for element in self {
if try predicate(element) {
return element
}
}
return nil
}
}
This now brings my benchmark time down from ~1.45 seconds to a nice ~0.04 seconds, which is only 2x slower than your original version of permute(), but is implemented with more functional methods. For your convenience, here's a gist with all the changes that I've made.
I couldn't find any other immediately obvious candidates for optimisation – but would certainly be interested if anyone else can.
Mutating vs. non-mutating
Which API is clearer?
I think both are fairly clear in terms of their usage (although they will require documenting in order to inform to the user that they do the permutations lexicographically). It's often common to implement a mutating and non-mutating version of the same logic (there are lots of examples in the stdlib), as both have can their uses in different circumstances.
Although for the non-mutating version, there's no need to completely re-invent the wheel – you can simply refactor it to use the mutating version's implementation:
extension Array where Element : Comparable {
func nextPermutation() -> Array? {
var result = self
return result.permute() ? result : nil
}
}
This doesn't impact the performance due to the fact that Array has copy-on-write semantics, so the array buffer won't actually be copied unless permute() actually does a permutation.
But really, for most common usages of this logic, I think the sequence-based API would probably be the clearest API to use – as I imagine most use cases will revolve around having to iterate through different permutations.
Can we make the non-mutating method as fast as the mutating one?
I don't believe so – if you want to have a copy of the array prior to the mutation, you'll have to pay the cost of a copy. I suspect the compiler may be able to optimise cases where the caller doesn't rely on the value of the original array remaining the same – but that's up to the compiler, and AFAIK there's no easy way to assist it with that in this case.