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

*To*: srfi-95@srfi.schemers.org*Subject*: Wording of the rationale*From*: Jens Axel Søgaard <jensaxel@soegaard.net>*Date*: Tue, 07 Nov 2006 13:49:06 +0100*Delivered-to*: srfi-95@srfi.schemers.org*User-agent*: Thunderbird 1.5.0.7 (Windows/20060909)

I am little unhappy about the wording of the rationale: RATIONALE When SRFI 32 Sort Libraries was withdrawn, it had 28 procedures for what should have been a clean, simple interface. In my view SRFI-32 *is* clean and simple. Comparing the number 28 to the number of procedures defined in SRFI-95 is unfair, since SRFI-95 covers the "What"-part but not the "How to"-part of SRFI-32. These 28 arose for several reasons: * List and Vector versions were separated, even though Scheme has manifest types which eliminate ambiguity as to the caller's intentions. Separating list and vector functions are tradition. In R5RS we have, for example list-ref, vector-ref and string-ref instead of general ref.

* Four varieties of algorithms were provided (quick, heap, insert, merge) even though quick, heap, and insert sorts have no significant advantage over merge-sort. First: The choice between these algorithms were in the "How to"-part of SRFI-32. If a user doesn't care, which algorithm is used, he can use list-sort!, vector-sort!. Second: What does "no significant advantage" mean? I were of the impression, that the "hidden constants" of O(n log (n)) of vector-quick-sort were smaller than that of vector-merge-sort. Third: The different algorithms have different memory requirements. If very large vectors are sorted, it makes sense to choose a slower algorithm that allocates very little extra memory. Some versions of vector-merge-sort! allocate a helper array the size of the original. Also: Is merge-sort the fastest algorithm, if the elements are "almost sorted"? * Sort and stable-sort varieties were included, even though an unstable sort has no performance advantage. As I see it, the reason they are in SRFI-32 is not efficiency but completeness. Nevertheless, if vector-quick-sort! (which is unstable) is faster than vector-merge-sort! (which is stable) then it makes sense to let vector-sort! default to vector-quick-sort! and let vector-stable-sort! default to vector-merge-sort! in the name of efficiency. -- Jens Axel Søgaard

**Follow-Ups**:**Re: Wording of the rationale***From:*Jens Axel Søgaard <jensaxel@soegaard.net>

**Re: Wording of the rationale***From:*Per Bothner <per@bothner.com>

**Re: Wording of the rationale***From:*Aubrey Jaffer <agj@alum.mit.edu>

- Prev by Date:
**Memory use of sort!** - Next by Date:
**Wording of the rationale** - Previous by thread:
**Re: Memory use of sort!** - Next by thread:
**Re: Wording of the rationale** - Index(es):