Javascript，如何写一个Array.sort方法，使其通过超时策略被调用？

Question

我的 sort() 函数遇到了瓶颈，例如：

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

这会使浏览器冻结几秒钟。

对于循环的相同情况，建议使用 "timeout" 策略，例如此处描述的策略：

How to stop intense Javascript loop from freezing the browser

那么问题来了，可以用sort方法来实现吗？

*在评论讨论后编辑

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

Answer 1

您可以实现自己的排序功能，例如这里是一个简单的选择排序：

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();
}

这比原版 sort 慢得多，但不会阻塞主线程。

Answer 2

您可以使用本机 sort 方法执行排序，但要在单独的线程中使用 Web Worker。 Web Worker 将在完成工作时发出通知。我已经将其包装在 ES6 promise 中，因此您可以使用 then 方法（请参阅下面的非 promise 版本）：

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]
});

非承诺版本如下所示：

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);
});

请注意，IE（至少版本 11）会在 Blob URL 上引发安全错误。作为解决方法，您必须创建一个仅包含以下内容的单独 JS 脚本文件：

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

...然后将该脚本作为 URL 引用到原始脚本中的 Worker：

new Worker('script.js')

Javascript，如何写一个Array.sort方法，使其通过超时策略被调用？

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

javascript

sorting

freeze