Array#sort(prop)

Kris Kowal kris.kowal at cixar.com
Sun Apr 1 17:16:39 PDT 2012


This is all pretty straightforward library work. With Narwhal’s "util"
module and with my previous work on Chiron, I made some small
composable tools, in much the same spirit as Jeremy Ashkenas’s work on
Underscore.  Consider two higher order functions.

by(relation) accepts a relation (a function that accepts a value and
returns a related value) and returns a comparator.

get(name) returns a relation function that retrieves the named
property of an object.

These compose like:

points.sort(by(get("x")))
points.sort(by(distanceFrom({x:10,y:20})))

So that much can be done in libraries.

What can’t be done without shimming the sort function is a Schwartzian
transformation. This is where you do a map/sort/map to reduce
applications of the relation, which can double the performance of a
sort in the most degenerate case: large completely unsorted array and
a costly relation. Some years ago I found that the optimization was
beneficial for arrays longer than 3 for a getter relation.

function schwartzianSort(values, relation, compare) {
    return values.map(function (value) {
        return [relation(value), value];
    }).sort(function (a, b) {
        return compare(a[0], b[0]);
    }).map(function (pair) {
        return pair[1];
    });
}

To facilitate this and the above notation, the comparator returned by
the "by" function was annotated with "compare" and "by" properties
which were the original relation and comparator. ("by" accepted an
alternate comparator as a second argument; the default had sensible
semantics for all same-type pairs of primordials and did not coerce
strings to numbers, a noteworthy wart of the existing specified
default comparator).

The alternate "sort" (in-place) and "sorted" (sorted copy) functions
would accept any object with a "by" property (and optional "compare"
property) would invoke the Schwartzian transform.

Adding support for this optimization to Array#sort would be
interesting, and the interface might provide an opportunity to allow
users to opt-in for a more sensible default comparator.  If "sort"
receives an object with "compare" or "by" properties, it could go
through the new code-path.  Passing a non-function object would
guarantee the more sensible default "compare".

A more sensible default "compare" would sort strings lexically, and
sort arrays with left-to-right precedence and recurse on each element.

Sensible invocations:

values.sort({by:relation})
values.sort({by:relation,compare:altCompare})
values.sort({compare}) // if default compare is added in global scope
values.sort({}) // default comparator

Kris Kowal


More information about the es-discuss mailing list