Aubrey Jaffer writes:
> | Date: Tue, 20 Feb 2007 20:55:40 -0500
> | From: Daniel Villeneuve <daniel_villeneuve_at_sympatico.ca>
> |
> | 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.
While this is true for a standard merge sort, I've found it
easier to get my merge sort implementation both stable and
Omega(n) (best case) by telling apart <, > and =. In my
implementation, this occurs when trying to grow a decreasing
sublist (if new item is less than start of sublist, insert
it before the start, if it is equal, insert it at the end of
the equal prefix of the sublist, else stop growing and
return to plain merge). I can't tell as of now if it would
be possible to rewrite the algorithm so that I could always
use a single one-sided comparison.
>From another angle, when wanting to chain several comparison
criteria, one needs to know if the first criterion is < or >
or =, and continue with a secondary criterion only in the
third case:
;; less?-like 2-level comparison, ordering first on the vec
;; component and, if equal, on crit
(lambda (a b)
(cond
((vector-less? (vec a) (vec b)) #t)
((vector-less? (vec b) (vec a)) #f)
(else (crit-less? (crit a) (crit b)))))
;; 3-way-like 2-level comparison, as above
(lambda (a b)
(let ((r (vector-cmp (vec a) (vec b))))
(cond
((zero? r) (crit-cmp (crit a) (crit b)))
(else r))))
These two points are related but not tightly bound. I agree
this can be seen as fine tuning.
> | PART B: prototype of the sorting functions
> |
> | Sorting can be made more efficient by providing a getter (projection)
> | function separate from the comparison function:
>
> 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.
That's fine (I should have browsed the SRFIs before writing
this comment).
--
Daniel
Received on Thu Feb 22 2007 - 22:45:30 UTC