Javascript, how to write a Array.sort method so that it is called through a timeout strategy?

Question

I am having a bottleneck with my sort() functions, something like:

list.sort(function (a,b) {return (a.value - b.value);});

that freezes the browser for a couple of seconds.

For the same situation with a loop it is recommended to use a "timeout" strategy, such as the one described here:

How to stop intense Javascript loop from freezing the browser

Then, the question is, can this be implemented with the sort methods?

*EDITED following the comment discussion

// main_div is a div defined before
for (let i=0; i<list.length; i++) {
    main_div.appendChild(document.getElementById(list[i].id));
}

How many elements in the array? Is there a possibility to use a web worker — Jaromanda X
– Jaromanda X, Commented Aug 28, 2016 at 10:28
@JaromandaX I am looking into it now, discovered few minutes ago so I have no idea. The elements are like +500 now, but they could/will be more — GWorking
– GWorking, Commented Aug 28, 2016 at 10:32
500 elements is freezing the browser for 2 seconds? are you running on a 80386? — Jaromanda X
– Jaromanda X, Commented Aug 28, 2016 at 10:33
@JaromandaX Now that you say it like this, probably what is freezing the browser is re-colocating the DOM nodes rather than the sorting. But still, the question remains relevant since as you suggested it involves using a webworker. I am looking at html5rocks.com/en/tutorials/workers/basics and trying to get a js_file from a function like in here stackoverflow.com/questions/3379875/… but with no success so far — GWorking
– GWorking, Commented Aug 28, 2016 at 10:36
@JaromandaX but I am also running a Chromebook, and the full system is loosing responsivity from time to time so the sort could also be a bottleneck — GWorking
– GWorking, Commented Aug 28, 2016 at 10:37

trincot · Accepted Answer · 2016-08-28 12:26:48Z

5

You could execute the sort with the native sort method, but in a separate thread, using a web worker. The web worker will notify when it has completed its job. I have wrapped this in an ES6 promise, so you can use the then method (see further down for non-promise version):

function asyncSort(data) {
    // Return a promise
    return new Promise(function (resolve) {
        // function to be called by web worker:
        function onmessage(e) {
            e.data.sort();
            postMessage(e.data);
        }
        // Create the worker, passing it the above code (as blob URL)
        var worker = new Worker(URL.createObjectURL(
            new Blob(['onmessage = ' + onmessage.toString()])));
        // Capture the event when worker has finished
        worker.onmessage = function (e) { 
            resolve(e.data); // resolve the promise
        };
        // Let worker execute the sort (async)
        worker.postMessage(data);
    });
}

// Sample call
asyncSort([2, 3, 1]).then(function (result) {
    console.log(result); // [1, 2, 3]
});

The non-promise version looks like this:

function asyncSort(data, callback) {
    function onmessage(e) {
        e.data.sort();
        postMessage(e.data);
    }
    var worker = new Worker(URL.createObjectURL(
        new Blob(['onmessage = ' + onmessage.toString()])));
    worker.onmessage = function (e) { 
        callback(e.data);
    };
    worker.postMessage(data);
}

asyncSort([2, 3, 1], function (result) {
    console.log(result);
});

Note that IE (at least up to version 11) raises a security error on the Blob URL. As a work-around you would have to create a separate JS script file with just this content:

onmessage = function (e) {
    e.data.sort();
    postMessage(e.data);
}

...and then reference that script as the URL to the Worker in the original script:

new Worker('script.js')

edited Aug 28, 2016 at 12:26

answered Aug 28, 2016 at 12:09

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

GWorking Over a year ago

Yes! that's what I was looking for, and thanks to let me see how to define a new worker with a simple function. A pity the webworkers cannot have access to the document or the DOM though :)

trincot Over a year ago

You're welcome. Just an additional idea for the DOM manipulation: create an array with pairs of sort data and related DOM HTML (fragment). Sort that by the "sort data" (whatever you sort by), and then join all the HTML together and insert it back. Downside is that you need to reassign event handlers.

GWorking Over a year ago

What I do is to generate an array with the id of my node and the data I want to sort, so the sort() only sorts this array, then with the sorted array I can access to my node through the id. I think this is what you're saying in some sense (?)

trincot Over a year ago

That is a good solution, yes: you would look up each element again by its id after the sort returns, and then move it to its correct position. I was actually hinting for providing the complete HTML of the node (instead of its id), thinking you could just destroy all elements in one go and recreate them by injecting the sorted HTML. In some situations this might be faster, but with the event handling downside.

georg · Accepted Answer · 2016-08-28 11:00:29Z

2

You can implement your own sorting function, for example, here a simple selection sort:

function asort(a, compare, done) {
    var i = 0, j = 0, len = a.length;

    function step() {
        if(j >= len)
            [i, j] = [i + 1, i + 1];
        if(i >= len)
            return done();
        if(compare(a[j], a[i]) < 0)
            [a[i], a[j]] = [a[j], a[i]]
        j++;
        setTimeout(step, 0);
    };

    step();
}

This is far slower than the stock sort, but doesn't block the main thread.

answered Aug 28, 2016 at 11:00

georg

216k57 gold badges324 silver badges401 bronze badges

3 Comments

Jaromanda X Over a year ago

perhaps you should add a note regarding your use of ES2015+ methods that wont work in IE11 for example - nor will it work in Edge unless you have the anniversary update (Edge 14)

georg Over a year ago

Thanks for the heads up… but honestly I don't see a point in comments like this. If you feel something should be added to the post - just edit it, this is how SO works.

Jaromanda X Over a year ago

I've only been on SO for a year and I've had such advice given every effing time i post an answer that wine work on ie7 or something. So I thought THAT was how it worked around here. I.e. find anything to criticize a good answer

Collectives™ on Stack Overflow

Javascript, how to write a Array.sort method so that it is called through a timeout strategy?

2 Answers 2

4 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related