Writing a Non-Blocking JavaScript Quicksort
breck-mckye.com
Writing a Non-Blocking JavaScript Quicksort
1–10 of 43 posts
Re: Writing a Non-Blocking JavaScript Quicksort
#2The obvious solution is to use a Web Worker,
var code = "onmessage = function (evt) {evt.data.sort(); postMessage(evt.data)}";
function asyncSort(data, cb) {
var worker = new Worker(URL.createObjectURL(new Blob([code])));
worker.onmessage = function (evt) { cb(evt.data); };
worker.postMessage(data);
}
asyncSort([3, 2, 1], function (res) { console.log(res); });
"[1, 2, 3]"Re: Writing a Non-Blocking JavaScript Quicksort
#3The obvious solution is to use a Web Worker, var code = "onmessage = function (evt) {evt.data.sort(); postMessage(evt.data)}"; function asyncSort(data, cb) { var worker = new Worker(URL.createObjectURL(new Blob([code]))); worker.onmessage = function (evt) { cb(evt.data); }; worker.postMessage(data); } Example, asyncSort([3, 2, 1], function (res) { console.log(res); }); Prints, "[1, 2, 3]"
I thought that as well, if you are going to use setImmediate, it would probably make the most sense to just a web worker which is actually standardized and supported in all browsers (and won't turn your quick sort fn into a mess).
However it looked like he needed to support IE8, so this might be an ok solution (although I would argue a terrible one for anyone who doesn't need to support IE8/9).
Re: Writing a Non-Blocking JavaScript Quicksort
#4The obvious solution is to use a Web Worker, var code = "onmessage = function (evt) {evt.data.sort(); postMessage(evt.data)}"; function asyncSort(data, cb) { var worker = new Worker(URL.createObjectURL(new Blob([code]))); worker.onmessage = function (evt) { cb(evt.data); }; worker.postMessage(data); } Example, asyncSort([3, 2, 1], function (res) { console.log(res); }); Prints, "[1, 2, 3]"
The whole thing issue was that it had to run in IE8.
Re: Writing a Non-Blocking JavaScript Quicksort
#5The 'long tail' really oughtn't be that long if they switched to the native sort when a partition becomes small enough.
Re: Writing a Non-Blocking JavaScript Quicksort
#6The obvious solution is to use a Web Worker, var code = "onmessage = function (evt) {evt.data.sort(); postMessage(evt.data)}"; function asyncSort(data, cb) { var worker = new Worker(URL.createObjectURL(new Blob([code]))); worker.onmessage = function (evt) { cb(evt.data); }; worker.postMessage(data); } Example, asyncSort([3, 2, 1], function (res) { console.log(res); }); Prints, "[1, 2, 3]"
The whole thing issue was that it had to run in IE8.
setImmediate is not supported in IE8 either.
Re: Writing a Non-Blocking JavaScript Quicksort
#7Re: Writing a Non-Blocking JavaScript Quicksort
#8You need to add a test at the start of your quicksort function - when the number of elements for this invocation is < 500, invoke native sort on the current subset.
Re: Writing a Non-Blocking JavaScript Quicksort
#9The main takeaway for me was lesson #4:
"setTimeout and browser timing are deceptive and shouldn’t be wholly trusted"... and as a result, use the setImmediate API.
Re: Writing a Non-Blocking JavaScript Quicksort
#10The 'long tail' really oughtn't be that long if they switched to the native sort when a partition becomes small enough.
> switched to the native sort when a partition becomes small enough
Isn't that exactly what they are doing?
>> Our approach was simply to prefer the native implementation unless working in IE8 or with arrays over a thousand items.