Function std.algorithm.sorting.schwartzSort
Alternative sorting method that should be used when comparing keys involves an expensive computation.
SortedRange!(R,(a,b)=>binaryFun!less(unaryFun!transform(a),unaryFun!transform(b))) schwartzSort(alias transform, alias less, SwapStrategy ss = SwapStrategy
R r
)
if (isRandomAccessRange!R && hasLength!R && hasSwappableElements!R && !is(typeof(binaryFun!less) == SwapStrategy));
auto schwartzSort(alias transform, SwapStrategy ss, R)
(
R r
)
if (isRandomAccessRange!R && hasLength!R && hasSwappableElements!R);
Instead of using less(a, b) for comparing elements,
schwartzSort uses less(transform(a), transform(b)). The values of the
transform function are precomputed in a temporary array, thus saving on
repeatedly computing it. Conversely, if the cost of transform is small
compared to the cost of allocating and filling the precomputed array, sort
may be faster and therefore preferable.
This approach to sorting is akin to the Schwartzian transform, also known as
the decorate-sort-undecorate pattern in Python and Lisp. The complexity is the
same as that of the corresponding sort, but schwartzSort evaluates
transform only r times (less than half when compared to regular
sorting). The usage can be best illustrated with an example.
Example
uint hashFun(string) { ... expensive computation ... }
string[] array = ...;
// Sort strings by hash, slow
sort!((a, b) => hashFun(a) < hashFun(b))(array);
// Sort strings by hash, fast (only computes arr.length hashes):
schwartzSort!(hashFun, "a < b")(array);The schwartzSort function might require less temporary data and
be faster than the Perl idiom or the decorate-sort-undecorate idiom
present in Python and Lisp. This is because sorting is done in-place
and only minimal extra data (one array of transformed elements) is
created.
To check whether an array was sorted and benefit of the speedup of
Schwartz sorting, a function schwartzIsSorted is not provided
because the effect can be achieved by calling isSorted!less(map!transform(r)).
Parameters
| Name | Description |
|---|---|
| transform | The transformation to apply. Either a unary function
(unaryFun!transform(element)), or a binary function
(binaryFun!transform(element, index)). |
| less | The predicate to sort the transformed elements by. |
| ss | The swapping strategy to use. |
| r | The range to sort. |
Returns
The initial range wrapped as a SortedRange with the
predicate (a, b) => binaryFun!less(transform(a), transform(b)).
Example
import std