X-Git-Url: http://git.vanrenterghem.biz/git.ikiwiki.info.git/blobdiff_plain/df022df35e3e3fd1d2916e762a2359f23a84a955..154c4ea9e:/doc/todo/smarter_sorting.mdwn diff --git a/doc/todo/smarter_sorting.mdwn b/doc/todo/smarter_sorting.mdwn index 4a638213f..901e143a7 100644 --- 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]]
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 @_ }