Merge branch 'master' of ssh://git.ikiwiki.info/srv/git/ikiwiki.info

[git.ikiwiki.info.git] / doc / todo / smarter_sorting.mdwn

diff --git a/doc/todo/smarter_sorting.mdwn b/doc/todo/smarter_sorting.mdwn
index 4a638213f8aeaaf1481a0b21b477606fdf8d873c..901e143a7e7d5675449aefbdc13c013308de5c94 100644 (file)
--- a/doc/todo/smarter_sorting.mdwn
+++ b/doc/todo/smarter_sorting.mdwn
@@ -16,15 +16,9 @@ more expensive than sorting. (Also, influence calculation complicates
 doing that.)
 
 Another option, when there is a limit on M pages to return, might be to
-cull the M top pages without sorting the rest. This could be done using
-a variant of Ye Olde Bubble Sort. Take the first M pages, and (quick)sort.
-Then for each of the rest, check if it is higher than the Mth page.
-If it is, bubble it up so it's sorted.
-If not, throw it out (that's the fast bit and why this is not O(N^2)).
+cull the M top pages without sorting the rest.
 
-> The patch below implements this, perhaps not as efficiently as possible.
-> It speeds up building just the top page of my blog by 1 second (out of
-> 18). It's probably buggy.
+> The patch below implements this.
 > 
 > But, I have not thought enough about influence calculation.
 > I need to figure out which pagespec matches influences need to be
@@ -36,13 +30,18 @@ If not, throw it out (that's the fast bit and why this is not O(N^2)).
 > zero) number of failed matches. New code does not accumulate influences
 > from all the top successful matches, only an arbitrary group of
 > successes and some failures.
+> 
+> Also, by the time I finished this, it was not measuarably faster than 
+> the old method. At least not with a few thousand pages; it
+> might be worth revisiting this sometime for many more pages? [[done]]
+> --[[Joey]] 
 
 <pre>
 diff --git a/IkiWiki.pm b/IkiWiki.pm
-index 1730e47..6798799 100644
+index 1730e47..bc8b23d 100644
 --- a/IkiWiki.pm
 +++ b/IkiWiki.pm
-@@ -2122,36 +2122,53 @@ sub pagespec_match_list ($$;@) {
+@@ -2122,36 +2122,54 @@ sub pagespec_match_list ($$;@) {
        my $num=$params{num};
        delete @params{qw{num deptype reverse sort filter list}};
        
@@ -89,7 +88,8 @@ index 1730e47..6798799 100644
 +                              # using a binary search
 +                              for (my $j=0; $j < @matches; $j++) {
 +                                      if (IkiWiki::SortSpec::cmptwo($candidates[$i], $matches[$j], $sort) < 0) {
-+                                              $matches[$j]=$candidates[$i];
++                                              splice @matches, $j, $#matches-$j+1, $candidates[$i],
++                                                      @matches[$j..$#matches-1];
 +                                              last;
 +                                      }
 +                              }
@@ -112,7 +112,7 @@ index 1730e47..6798799 100644
        if (! defined $num && defined $sort) {
                return IkiWiki::SortSpec::sort_pages(
                        $sort, @matches);
-@@ -2455,6 +2472,12 @@ sub sort_pages {
+@@ -2455,6 +2473,12 @@ sub sort_pages {
        sort $f @_
  }