Feature Proposal: add Sort::Maker as general sorting helper

Motivation

Currently:
  • Each module and plugin has its own sort functions
  • Lists are often not sorted case-insensitive because of fear of performance loss, resulting in (for humans) strange word order
  • Key sort can be made more efficient

It would be useful to have one sorting mechanism that core code and plugins can use. This core sort code can be tested.

Proposal

Add CPAN:Sort::Maker to the distributed CPAN directory.

Description and Documentation

I was triggered by A Fresh Look at Efficient Perl Sorting. It is a widely quoted paper that has resulted in CPAN:Sort::Maker - A simple way to make efficient sort subs.

I have looked at 2 alternatives to use:

CPAN:Sort::Key is not a pure Perl library, so not suited for Foswiki. I haven't looked any further into it.

CPAN:Sort::Maker is, and am quite pleased with the API. It took a while to get some working examples, so I have attached sort_maker_test.pl (remove txt extension of course) if you want to play with it.

I can see a second benefit of using this library: it is quite easy to change the sorting algorithm to test which one performs best for the given task. It might be a Schwartzian Transform, or a Guttman-Rosler Transform, or a plain sort.

Also sorting by multiple keys is easy.

-- Contributors: ArthurClemens - 26 Oct 2008, 14 Mar 2010

Discussion

excellent smile I'll prod them asap, and then see if making the sorting a pluggable part of store is worth it (that way we can keep the old code in this release, and upgrade it in place (even using a Contrib).

-- SvenDowideit - 15 Mar 2010

I'm thinking the most flexible use we can have, is to wrap CPAN:Sort::Maker into a Foswiki::Iterator::SortedIterator - which 'isa' . Foswiki::ListIterator (yes, the second isn't in the right place, but we can't move it without breaking plugins.

however, this is not the most effective way for us to speed up searches as that is a processing done after we've tested each topic for a query. What I'm still trying to figure out how to do, is to only evaluate about the same number of candidate topics as the SEARCH is trying to output - which requires more Store magic, and then a further change to how the Algo's do their thing.

-- SvenDowideit - 27 Mar 2010

Accepted by 14-day rule.

Note that what is accepted is adding the CPAN lib.

We have not accepted a major code refactoring of core code to start using these. It is too risky in a 1.1 scope.

-- KennethLavrsen - 30 Mar 2010

Fine. I will add developer documentation as well.

-- ArthurClemens - 30 Mar 2010

 
Topic revision: r10 - 06 Dec 2010, GeorgeClark
The copyright of the content on this website is held by the contributing authors, except where stated elsewhere. See Copyright Statement. Creative Commons License    Legal Imprint    Privacy Policy