Assume you have an expensive function
f that, given something, returns a number. You don't particularly care about the output of
f; you actually care about how it sorts (or ranks) some collection of inputs, that is, you care about
results in the following:
var inputs; // initialized to an array of something that `f` consumeslet results = inputs;results;
(If you're confused by the argument to
Now. You've come up with a clever approximation to
f2, that won't give exactly the same outputs as
f but might be much faster to compute.
f2 might not even sort a collection of inputs in the same way as
How good of an approximation is
In other words, how closely do elements of a set sort under two separate functions?
This little dependency-free library quickly lets you answer this question.
This library is intended to be installed in Node.js (and potentially bundled for browsers via Browserify, etc.). Therefore, assuming you have Node.js installed and an npm project initialized, run the following in the same directory as your npm project:
$ npm install --save rank-compare-approximations
--save-dev if this library will only be used to develop your npm project.)
var compare = ;
var result = compare(args, f, f2);
args: Array<T>, that is, an array of some type
T, and functions
f: T -> numberand
f2: T -> number, that is, functions that, given some object of type
Tand returning a number,
result: Array<number> will be an array of numbers, the same length as
args, whose elements tell you how many indexes away each element of
args sorted according to
f2 is a great approximation to
f, this will be an array entirely containing 0s: 0 is good, it means "zero sort (or rank) error". If
f2 occasionally mis-sorts (relative to
f), some elements of the result will be non-zero, but most should be 0. If
f2 is a bad approximation of
f, then few elements of the result will be zero.
var y = args;var y2 = args;var ySort = y;var y2Sort = y2;var result = args;
The above is actually one way that this library is tested. It's slow because repeatedly calling
findIndex like this is needlessly quadratic. The performance-minded reader will notice that we could create a
Map to store the reverse-indexes, which is the other way that this library is tested. See tests.js.
The library actually implements something a little bit more clever than this: it sorts the sort indexes of
y2 above—there is no typo in this sentence. Thus, the runtime cost of the library (aside from the cost of invoking
f2) is four sorts.
(This is "clever" in the algorithmic sense: it might not be immediately obvious why finding the sort indexes of the sort indexes of the mapping under
f2 can be compared via subtraction, but some doodling with pen and paper will show you why it works. This implementation might be slower than something more straightforward using
Maps as hinted above and implemented in the tests. My casual benchmarking showed that the library, using four sorts, was within 15% of the straightforward implementation.)
Consider an expensive function
var f = x => x + Math.sin(2 * Math.PI * 3 * x) * 0.1 + x that you want to approximate using
var f2 = x => x. The two are plotted below:
(Image courtesy of intmath.com.)
f2 will sort some areas of the x-axis the same but other areas differently, specifically, the areas where
f is decreasing while
f2 stays increasing. The table below shows the index, the value of
x, and the sort distance (the output of
compare). The sort distance remains zero except for those portions where
f(x) is decreasing, while
f2 fails to capture that.
Code to produce the above:
var Math * 01 + x;var x;var N = 100;var x = Array;var result = ;x;