Re: [selectors-api] Summary of Feature Requests for v2

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.


Received on Thursday, 24 September 2009 21:21:29 UTC