mbostock/d3 — pull request #1829 by ChALkeR (2014-04-06 00:27:06+00:00)
Title: Huge d3.interpolateString optimization: fix #1826 and #1827.

Two major changes here:
1) Use algorithm with compexity O(n) instead of O(n^2).
2) Replace calls to splice() with constructing a new array.

First change makes the algorithm a lot faster, it was incredibly slow
when some of the corresponding numbers in a and b were equal.

The second change makes the algorithm much faster for cases
when many small intervals have to be removed or coalesced,
but makes the algorithm about 10% slower for the case when
no elements have to be removed (keeping the whole array).

The interpolator complexity and execution time have not increased.

The test results are not too precise, I ran each one only a few times.

Worst-case for the old algorithm (0% different numbers between a and b):
12000 numbers: 20 ms instead of 300 ms.
60000 numbers: 90 ms instead of 13 seconds.
300000 numbers: 300 ms instead of 9 minutes.
1500000 numbers: 1.6 seconds.

Average-case for the old algorithm (93% different numbers between a and b):
12000 numbers: 50 ms instead of 60 ms.
60000 numbers: 130 ms instead of 1250 ms.
300000 numbers: 520 ms instead of 41 seconds.
1500000 numbers: 2.8 seconds.

Best-case for the old algorithm (100% different numbers between a and b):
12000 numbers: 25 ms instead of 20 ms.
60000 numbers: 100 ms instead of 90 ms.
300000 numbers: 550 ms instead of 510 ms.
1500000 numbers: 4.4 s. instead of 4.4 s.

1500000 numbers is a string with 2.1e7 chars, that's 20 MiB in one-byte encoding.