View source code
Display the source code in std/algorithm/sorting.d from which this page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

Function std.algorithm.sorting.schwartzSort

Alternative sorting method that should be used when comparing keys involves an expensive computation. 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.length times (less than half when compared to regular sorting). The usage can be best illustrated with an example.

Prototype

SortedRange!(R,(a,b)=>binaryFun!less(unaryFun!transform(a),unaryFun!transform(b))) schwartzSort(alias transform, alias less, std.algorithm.mutation.SwapStrategy ss, R)(
  R r
)
if (isRandomAccessRange!R && hasLength!R);

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

NameDescription
transform The transformation to apply.
less The predicate to sort 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.algorithm.iteration : map;
import std.numeric : entropy;

auto lowEnt = [ 1.0, 0, 0 ],
     midEnt = [ 0.1, 0.1, 0.8 ],
    highEnt = [ 0.31, 0.29, 0.4 ];
auto arr = new double[][3];
arr[0] = midEnt;
arr[1] = lowEnt;
arr[2] = highEnt;

schwartzSort!(entropy, "a > b")(arr);

writeln(arr[0]); // highEnt
writeln(arr[1]); // midEnt
writeln(arr[2]); // lowEnt
assert(isSorted!("a > b")(map!(entropy)(arr)));

Authors

Andrei Alexandrescu

License

Boost License 1.0.

Comments