On Fri, Oct 13, 2006 at 01:24:30AM +0200, Marcin 'Qrczak' Kowalczyk wrote:
> Aubrey Jaffer <ajaffer_at_clearmethods.com> writes:
>
> > | The key should be extracted exactly once for each element.
> >
> > Because there are potentially more than O(N) comparisons, keys are
> > potentially accessed more than once. So the sort routines would need
> > to allocate O(N) storage to hold the keys to meet this requirement.
>
> If an implementation extracts keys once, I have a choice: for a fast
> key extraction function I can pass a comparator which extracts keys
> on each comparison to save some memory, and for a slow key extraction
> I can rely on the variant with a key extractor doing the appropriate
> thing.
And if the key-extract function is impure, this can affect the results
and not just the run time -- e.g., sorting a list of files by time of
last modification, where the get-key calls Unix stat(2) or equivalent,
would yield Bad Stuff if a file were modified during the sort.
--
(let ((C call-with-current-continuation)) (apply (lambda (x y) (x y)) (map
((lambda (r) ((C C) (lambda (s) (r (lambda l (apply (s s) l)))))) (lambda
(f) (lambda (l) (if (null? l) C (lambda (k) (display (car l)) ((f (cdr l))
(C k))))))) '((#\J #\d #\D #\v #\s) (#\e #\space #\a #\i #\newline)))))
Received on Thu Oct 19 2006 - 02:54:39 UTC