Add extract method to Array

I think @yxckjhasdkjh's point is that stablePartition gives you a very similar result, where elements are grouped in a similar way to extract, just as the start/end of a single array, instead of two. One can then (relatively) efficiently mutate the array to convert it into two separate ones:

let index = a.stablePartition(isSuffixElement: { $0 % 2 == 0 })
let b = Array(a.suffix(from: index))
a.removeSubrange(index...)

This particular approach has the advantage over the rough implementation above in that it has no explicit loops, and instead is just composed of a few successive linear time operations, and so is linear time itself. In contrast, both the repeated remove(at: i)s and insert(... at: 0)s result in the loop in the rough extract being O(self.count2), that is, quadratic in the length of the array (both of these can be fixed "manually", but I suspect using stablePartition or similar will be the easiest to understand).

Additionally, depending what one is doing, it may even be okay to avoid the suffix copy, and instead just work directly with the sliced version.

(I'll also just reiterate the presentation that @yxckjhasdkjh links to: it's an enjoyable and informative session to watch when designing algorithms like this.)

9 Likes