# rank-compare-approximations

## Rationale

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 `sort`

, welcome to one of JavaScript's most surreal pitfalls.)

Now. You've come up with a clever approximation to `f`

, called `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 `f`

.

**How good of an approximation is f2 of f?**

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.

## Installation

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
```

(Consider replacing `--save`

with `--save-dev`

if this library will only be used to develop your npm project.)

Import the library into your JavaScript source or a Node terminal via:

`var compare = ;`

## API

`var result = compare(args, f, f2);`

Given

`args: Array<T>`

, that is, an array of some type`T`

, and functions`f: T -> number`

and`f2: T -> number`

, that is, functions that, given some object of type`T`

and returning a number,

the resulting `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 `f`

vs `f2`

.

If `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.

Notionally:

`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 `y`

and `y2`

above—there is no typo in this sentence. Thus, the runtime cost of the library (aside from the cost of invoking `f`

and `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 `f`

versus `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 `Map`

s 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.)

## Example

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.)

Clearly, `f`

and `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.

index | `x` |
sort distance |
---|---|---|

0 | 0 | 0 |

1 | 0.01 | 0 |

2 | 0.02 | 0 |

3 | 0.03 | 0 |

4 | 0.04 | 0 |

5 | 0.05 | 0 |

6 | 0.06 | 7 |

7 | 0.07 | 10 |

8 | 0.08 | 12 |

9 | 0.09 | 14 |

10 | 0.1 | 15 |

11 | 0.11 | 17 |

12 | 0.12 | 15 |

13 | 0.13 | 11 |

14 | 0.14 | 8 |

15 | 0.15 | 6 |

16 | 0.16 | 2 |

17 | 0.17 | -1 |

18 | 0.18 | -4 |

19 | 0.19 | -8 |

20 | 0.2 | -11 |

21 | 0.21 | -13 |

22 | 0.22 | -16 |

23 | 0.23 | -16 |

24 | 0.24 | -14 |

25 | 0.25 | -13 |

26 | 0.26 | -11 |

27 | 0.27 | -8 |

28 | 0.28 | -2 |

29 | 0.29 | 0 |

30 | 0.3 | 0 |

31 | 0.31 | 0 |

32 | 0.32 | 0 |

33 | 0.33 | 0 |

34 | 0.34 | 0 |

35 | 0.35 | 0 |

36 | 0.36 | 0 |

37 | 0.37 | 0 |

38 | 0.38 | 0 |

39 | 0.39 | 5 |

40 | 0.4 | 9 |

41 | 0.41 | 12 |

42 | 0.42 | 13 |

43 | 0.43 | 15 |

44 | 0.44 | 16 |

45 | 0.45 | 16 |

46 | 0.46 | 13 |

47 | 0.47 | 10 |

48 | 0.48 | 6 |

49 | 0.49 | 3 |

50 | 0.5 | 0 |

51 | 0.51 | -3 |

52 | 0.52 | -6 |

53 | 0.53 | -10 |

54 | 0.54 | -13 |

55 | 0.55 | -16 |

56 | 0.56 | -16 |

57 | 0.57 | -15 |

58 | 0.58 | -13 |

59 | 0.59 | -12 |

60 | 0.6 | -9 |

61 | 0.61 | -5 |

62 | 0.62 | 0 |

63 | 0.63 | 0 |

64 | 0.64 | 0 |

65 | 0.65 | 0 |

66 | 0.66 | 0 |

67 | 0.67 | 0 |

68 | 0.68 | 0 |

69 | 0.69 | 0 |

70 | 0.7 | 0 |

71 | 0.71 | 0 |

72 | 0.72 | 2 |

73 | 0.73 | 8 |

74 | 0.74 | 11 |

75 | 0.75 | 13 |

76 | 0.76 | 14 |

77 | 0.77 | 16 |

78 | 0.78 | 16 |

79 | 0.79 | 13 |

80 | 0.8 | 11 |

81 | 0.81 | 8 |

82 | 0.82 | 4 |

83 | 0.83 | 1 |

84 | 0.84 | -2 |

85 | 0.85 | -6 |

86 | 0.86 | -8 |

87 | 0.87 | -11 |

88 | 0.88 | -15 |

89 | 0.89 | -17 |

90 | 0.9 | -15 |

91 | 0.91 | -14 |

92 | 0.92 | -12 |

93 | 0.93 | -10 |

94 | 0.94 | -7 |

95 | 0.95 | 0 |

96 | 0.96 | 0 |

97 | 0.97 | 0 |

98 | 0.98 | 0 |

99 | 0.99 | 0 |

Code to produce the above:

`var Math * 01 + x;var x;var N = 100;var x = Array;var result = ;x;`