Hacker News Reader

Comment by drewda | Hacker News Reader

@mbostock: Why is there Dart code in the project? Just because that's where you borrowed one of the sort functions from?

Thanks for another useful library!

View on HN

Yep. Typed arrays don't have a built-in sort method, and even the built-in array.sort is extremely slow. I ported Dart's dual-pivot quicksort implementation, which reduced the time to sort 1M floats from ~2.5s to ~350ms (timed in Node v0.6.2).

https://github.com/square/tesseract/blob/master/src/quicksor...

Good to know. I'll have to consider switching away from Underscore's sort, which is probably equally slow.

By the way, quicksort.js is code you wrote, right? I assume that's too nice and concise to be from the Dart generator...

Underscore doesn't have a "sort" apart from the native Array.prototype.sort, but it does have a "sortBy", which is something else entirely.

The sortBy method is just producing an integer array that is then sorted using each browser's implementation of Array.prototype.sort. Is that a proper reading of the code?

Bingo. You got it.

Right; I ported it from the Dart implementation, not from the generated JavaScript.

For sorting numbers, you might also want to look at Radixsort.js, which takes O(n) time, although it isn't in-place like quicksort:

https://github.com/jasondavies/radixsort.js

I haven't finished implementing the Float64Array version, but it beats everything else I've compared it with even for relatively small sizes e.g. my benchmark is 65,536 floats and it's already around 2.5x faster than native sort (using Node.js)! Admittedly, Float32Array vs. native sorting of 64-bit floats is not a fair comparison, but you could argue that many applications would get away fine with 32-bit floats anyway. :)

Got inspired and it now supports Float64Array. :)

Reply on news.ycombinator.com