Previously, in _minImplementation(count:sortedBy:), when finding a new, smaller element, we were calculating the insertion index on the full-sized collection, subsequently removing the last element, then inserting the new element at that insertion index. This has a couple small problems:
We were calling partitioningIndex(where:) on a larger collection than necessary. By removing the last element first (which doesn’t need to be compared against again), we make the collection slightly smaller, resulting in fewer comparisons. For simple comparisons (like Ints), this isn’t a big deal, but if the comparison is more expensive (like with a custom struct with multiple properties), this can make a slight difference.
The insertion index that we found could theoretically be invalidated after calling removeLast(), according to the documentation:
Calling this method may invalidate all saved indices of this collection. Do not rely on a previously stored index value after altering a collection with any operation that can change its length.
While this isn’t currently/ever going to be a problem for Array, it‘s still good practice. This could theoretically set us up in the future to use a more optimized data structure with different indexing behavior than Array.
Neither of these are real big issues, but I stumbled upon this today and thought it a small worthwhile change.
Checklist
[ ] I've added at least one test that validates that my change is working, if appropriate
[x] I've followed the code style of the rest of the project
Previously, in
_minImplementation(count:sortedBy:)
, when finding a new, smaller element, we were calculating the insertion index on the full-sized collection, subsequently removing the last element, then inserting the new element at that insertion index. This has a couple small problems:We were calling
partitioningIndex(where:)
on a larger collection than necessary. By removing the last element first (which doesn’t need to be compared against again), we make the collection slightly smaller, resulting in fewer comparisons. For simple comparisons (likeInt
s), this isn’t a big deal, but if the comparison is more expensive (like with a custom struct with multiple properties), this can make a slight difference.The insertion index that we found could theoretically be invalidated after calling
removeLast()
, according to the documentation:While this isn’t currently/ever going to be a problem for
Array
, it‘s still good practice. This could theoretically set us up in the future to use a more optimized data structure with different indexing behavior thanArray
.Neither of these are real big issues, but I stumbled upon this today and thought it a small worthwhile change.
Checklist