| Date: Tue, 20 Feb 2007 20:55:40 -0500
| From: Daniel Villeneuve <daniel_villeneuve_at_sympatico.ca>
|
| ---
| This message is a formal comment which was submitted to
| formal-comment_at_r6rs.org, following the requirements described at:
|
http://www.r6rs.org/process.html
| ---
| submitter's name: Daniel Villeneuve
| submitter's email address: daniel_villeneuve_at_sympatico.ca
| type of issue: enhancement
| priority: minor
| R6RS component: Sorting
| version of the report: 5.92
|
| SUMMARY
|
| Implementations could provide better sorting performance
| with a slightly different sorting interface.
|
| DESCRIPTION
|
| This comment is in two related parts.
|
| PART A: prototype for comparison functions
|
| The comparison function provided to list-sort and
| vector-sort should return a 3-way result when comparing two
| objects a and b:
| - negative integer: a < b
| - 0: a = b
| - positive integer: a > b
|
| This avoids comparing items twice, which can be costly in
| some cases (e.g., comparing vectors of numbers).
Merge-sort does not compare pairs of items twice. Any sorting
algorithm which did could be improved by removing one of the
comparisons [because (<= a b) is equivalent to (not (< b a))]. 3-way
comparisons do not improve sorting performance.
| PART B: prototype of the sorting functions
|
| Sorting can be made more efficient by providing a getter (projection)
| function separate from the comparison function:
|
| Both
|
| (list-sort (lambda (a b) (cmp-increasing-number
| (get-field-1 a)
| (get-field-1 b)))
| x)
|
| and
|
| (list-sort get-field-1 cmp-increasing-number x)
|
| would behave the same, except that the sorting function could take
| advantage of the separation between the getter and the comparator.
Please see
http://srfi.schemers.org/srfi-95/srfi-95.html, whose
functions take an optional key-procedure argument. SRFI-95 mandates
that the key-procedure be called at most once on every element in the
list or array.
Received on Thu Feb 22 2007 - 13:07:06 UTC