]> git.vanrenterghem.biz Git - git.ikiwiki.info.git/blobdiff - doc/todo/smarter_sorting.mdwn
Merge branch 'master' into cvs
[git.ikiwiki.info.git] / doc / todo / smarter_sorting.mdwn
index f8ac216dc37144a5f025d6e7682940ca083822b3..901e143a7e7d5675449aefbdc13c013308de5c94 100644 (file)
@@ -13,14 +13,119 @@ out of maybe thousands).
 As [[smcv]] noted, It could be flipped, so the pagespec is applied first,
 and then sort the smaller matching set. But, checking pagespecs is likely
 more expensive than sorting. (Also, influence calculation complicates
-doing that, since only influences for the M returned pages should be tracked.)
+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.
+> 
+> But, I have not thought enough about influence calculation.
+> I need to figure out which pagespec matches influences need to be
+> accumulated for in order to determine all possible influences of a
+> pagespec are known.
+> 
+> The old code accumulates influences from matching all successful pages
+> up to the num cutoff, as well as influences from an arbitrary (sometimes
+> 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..bc8b23d 100644
+--- a/IkiWiki.pm
++++ b/IkiWiki.pm
+@@ -2122,36 +2122,54 @@ sub pagespec_match_list ($$;@) {
+       my $num=$params{num};
+       delete @params{qw{num deptype reverse sort filter list}};
+       
+-      # when only the top matches will be returned, it's efficient to
+-      # sort before matching to pagespec,
+-      if (defined $num && defined $sort) {
+-              @candidates=IkiWiki::SortSpec::sort_pages(
+-                      $sort, @candidates);
+-      }
+-      
++      # Find the first num matches (or all), before sorting.
+       my @matches;
+-      my $firstfail;
+       my $count=0;
+       my $accum=IkiWiki::SuccessReason->new();
+-      foreach my $p (@candidates) {
+-              my $r=$sub->($p, %params, location => $page);
++      my $i;
++      for ($i=0; $i < @candidates; $i++) {
++              my $r=$sub->($candidates[$i], %params, location => $page);
+               error(sprintf(gettext("cannot match pages: %s"), $r))
+                       if $r->isa("IkiWiki::ErrorReason");
+               $accum |= $r;
+               if ($r) {
+-                      push @matches, $p;
++                      push @matches, $candidates[$i];
+                       last if defined $num && ++$count == $num;
+               }
+       }
++      # We have num natches, but they may not be the best.
++      # Efficiently find and add the rest, without sorting the full list of
++      # candidates.
++      if (defined $num && defined $sort) {
++              @matches=IkiWiki::SortSpec::sort_pages($sort, @matches);
++
++              for ($i++; $i < @candidates; $i++) {
++                      # Comparing candidate with lowest match is cheaper,
++                      # so it's done before testing against pagespec.
++                      if (IkiWiki::SortSpec::cmptwo($candidates[$i], $matches[-1], $sort) < 0 &&
++                          $sub->($candidates[$i], %params, location => $page)
++                      ) {
++                              # this could be done less expensively
++                              # using a binary search
++                              for (my $j=0; $j < @matches; $j++) {
++                                      if (IkiWiki::SortSpec::cmptwo($candidates[$i], $matches[$j], $sort) < 0) {
++                                              splice @matches, $j, $#matches-$j+1, $candidates[$i],
++                                                      @matches[$j..$#matches-1];
++                                              last;
++                                      }
++                              }
++                      }
++              }
++      }
++
+       # Add simple dependencies for accumulated influences.
+-      my $i=$accum->influences;
+-      foreach my $k (keys %$i) {
+-              $depends_simple{$page}{lc $k} |= $i->{$k};
++      my $inf=$accum->influences;
++      foreach my $k (keys %$inf) {
++              $depends_simple{$page}{lc $k} |= $inf->{$k};
+       }
+-      # when all matches will be returned, it's efficient to
+-      # sort after matching
++      # Sort if we didn't already.
+       if (! defined $num && defined $sort) {
+               return IkiWiki::SortSpec::sort_pages(
+                       $sort, @matches);
+@@ -2455,6 +2473,12 @@ sub sort_pages {
+       sort $f @_
+ }
++sub cmptwo {
++      $a=$_[0];
++      $b=$_[1];
++      $_[2]->();
++}
++
+ sub cmp_title {
+       IkiWiki::pagetitle(IkiWiki::basename($a))
+       cmp
+</pre>
 
 This would be bad when M is very large, and particularly, of course, when
 there is no limit and all pages are being matched on. (For example, an