- From: Boris Zbarsky <bzbarsky@MIT.EDU>
- Date: Thu, 24 Sep 2009 17:20:41 -0400
- To: John Resig <jresig@mozilla.com>
- CC: public-webapps <public-webapps@w3.org>
On 9/24/09 5:09 PM, John Resig wrote: > It's only if it's an array that we have to do the dance. Even in the > case where the array of results is already in document order the sort > will be incredibly fast (O(N)). O(N) in number of nodes in the array, and that assumes that the array is not being sorted using quicksort or some such. But the "constant" here is not actually a constant. The time required to compare the DOM positions of two nodes is very much dependent on the DOM, though clearly bounded above for a given DOM. Last I checked, it's not that hard to produce situations in both Gecko and Webkit (haven't looked at the Trident and Presto source, so can't comment on those) where each such position comparison is O(N) in number of nodes in the DOM (though that usually involves having a very shallow DOM with a single node that has lots of kids). So it's not that hard to end up with O(N^2) or worse behavior for sorting an array of nodes. Of course that's true whether the sort is done in JS or in C++. But it might be worth thinking about use cases here and whether they can be addressed in ways that don't involve sorting node arrays. -Boris
Received on Thursday, 24 September 2009 21:21:29 UTC