Re: [xml] XPath optimizations

Petr Pajas wrote:

   glance). I've replaced Shell's sort with Bubble sort. As everyone
   knows its complexity is between O(n) and O(n^2), which is the worst
   case (inverted list) and of course worse than Shell's sort in
   average case. How ever, in case of presorted node-list, bubble sort
   always compares two subsequent nodes in the list in which case
   xmlXPathCmpNodes does not go far when traversing the tree and is
   O(1). (Both Shell's sort and quick-sort usually compares nodes far
   in the list, so xmlXPathCmpNodes has far journeys pretty often).
   Since in most cases, XPath results *are* actually already well
   sorted (and I can hardly imagine an expression resulting in a long
   reversely ordered node-list), bubble sort seems much better choice

Here's a suggestion. Before doing the actual sorting, examine N nodes.
If they (or most of them) are in increasing order, we will use Bubble
sort, otherwise we use Shell's sort.

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]