Noncommital Premarital Mischief
    Wondering what’s next for npm?Check out our public roadmap! »

    binary-insert
    TypeScript icon, indicating that this package has built-in type declarations

    1.2.1 • Public • Published

    Binary Insert for Javascript

    Simple function binaryInsert(array, value, comparator) that provides binary insert functionality for a sorted array in javascript. This is mostly intended for larger arrays, and the performance gain may be viewed in the benchmark.

    Binary insertion is O(log(n)) while Javascript's .sort() (using quicksort or similar) is O(n * log(n)), while linear insertion is O(n). When inserting a single value (in a sorted array) binary insertion is the clear winner; however this breaks down when inserting multiple values (a) because each time binary insertion is used it will have a cost of O(log(n)), which will result in a cost of O(a * log(n)). At first glance this may appear to be the same as Javascript's sort implementation, but it has quite the performance difference when multiple values are inserted as can be viewed in the benchmarks below.

    If you're inserting into a large sorted list, but not necessarily all at once this can provide much higher performance than sorting every time you add an element, or even when you add multiple values and then sort. However, if you're adding quite a few values (especially on larger arrays) and then sorting after you will see better performance - refer to benchmarks to see where this breaks down in terms of number of insertions and array size.

    Note, the array MUST be SORTED or the insert position will be nonsensical.

    Example usage

    npm install binary-insert

    import { binaryInsert } from "binary-insert";
    // or can do:
    const binaryInsert = require('binary-insert').binaryInsert;
     
    const ary = [1,2,3,5];
    const comparator = (a,b) => a - b;
    binaryInsert(ary, 4, comparator); // this actually returns ary as well
    // ary = [1,2,3,4,5]

    Benchmarks

    The benchmark results can be viewed below and a quick a snapshot of them is given in the tables here too. These were done on a Macbook Pro with (Haswell) 2.3 GHz Quad-Core Intel Core i7. The benchmark action can also be run to obtain similar results on whatever is powering the Github action workflows. The array values were the same for both binary and insert-then-sort and the insertion values were randomly generated (but the same values were used for both binary and insert-then-sort insertions).

    Single value insert (averaged over 50 runs)

    Array Size Binary Insert (ms) Insert then sort (ms)
    10 0.007095 0.001031
    100 0.002791 0.003197
    1,000 0.002635 0.022575
    10,000 0.008906 0.214727
    100,000 0.029025 2.354665
    1,000,000 0.790569 26.176829

    Multi value insert (array size = 100,000, averaged over 50 runs)

    Number of insertions Binary Insert (ms) Insert then sort (ms)
    10 0.126522 2.469704
    100 1.635489 2.514384
    300 4.972899 2.510613
    600 9.857568 2.611133
    900 23.032073 2.668079
    Averaged over 50 runs.
                    SINGLE VALUE INSERT RESULTS
    Array Size			Binary Insert (ms)			Insert then Sort (ms)
    10				0.007095				0.001031
    100				0.002791				0.003197
    1000				0.002635				0.022575
    10000				0.008906				0.214727
    100000				0.029025				2.354665
    1000000				0.790569				26.176829
    
                                MULTI VALUE INSERT RESULTS
    Array Size			Number of Insertions			Binary Insert (ms)			Insert then Sort (ms)
    10				10					0.003544				0.000874
    100				10					0.001907				0.098443
    1000				10					0.002778				0.029314
    10000				10					0.013893				0.200234
    100000				10					0.126522				2.469704
    1000000				10					6.533801				26.832977
    
    10				100					0.010288				0.000621
    100				100					0.016141				0.006602
    1000				100					0.024389				0.027441
    10000				100					0.165347				0.295880
    100000				100					1.635489				2.514384
    1000000				100					19.314336				25.200716
    
    10				300					0.028600				0.000865
    100				300					0.046016				0.004789
    1000				300					0.080592				0.035301
    10000				300					0.422537				0.257292
    100000				300					4.972899				2.510613
    1000000				300					73.036811				27.031756
    
    10				600					0.060059				0.000818
    100				600					0.095325				0.005672
    1000				600					0.150927				0.034564
    10000				600					0.811396				0.261965
    100000				600					9.857568				2.611133
    1000000				600					110.728053				27.444640
    
    10				900					0.103899				0.000797
    100				900					0.157177				0.004501
    1000				900					0.226895				0.031276
    10000				900					1.372212				0.268816
    100000				900					23.032073				2.668079
    1000000				900					226.192967				27.160759
    
    

    An attempt at explaining the performance difference

    I haven't looked at the V8 source, and I'm actually making some assumptions here on the underlying implementation of splice and push based on the performance noticed here.

    The Big-O of Binary Insert really looks more like O(log(n) + n), which is the sum of finding the insertion point (O(log(n))) and resizing the array (O(n) - via splice()) to insert the value.

    The Big-O of Insert-then-sort really looks more like O(n * log(n) + n), which is the sum of sorting the array (O(n * log(n))) and pushing (O(n)) an element onto the array. However, Javascript's Array probably acts like an ArrayList where pushing a value will resize the array once, but not multiple times (well, unless the resized amount has been exceeded). So, when inserting multiple values the array is (usually) only resized once, so the resize penalty is not paid each time like it is with Binary Insert (which uses splice to insert the element).

    So, when inserting multiple elements (a) the cost for Binary Insert is O(a * (log(n) + n)). Yet, the cost for Insert-then-sort is still (roughly) the same at O(n * log(n) + n).

    There is, of course, more going on than this reduction, as it doesn't perfectly explain the output, but it should provide a pretty intuitive explanation for the benchmark results.

    Install

    npm i binary-insert

    DownloadsWeekly Downloads

    39

    Version

    1.2.1

    License

    MIT

    Unpacked Size

    10.4 kB

    Total Files

    5

    Last publish

    Collaborators

    • avatar