From: ···········@alcoa.com
Subject: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <7f2bj0$br4$1@nnrp1.dejanews.com>
I wanted to use the quicksort routine in Graham's book ANSI Common Lisp but
it is broken. Does anyone know how to fix it? Is there another lisp sort
routine someone can recommend? I need a fast sort of a vector of floats and
an optimized version of Graham's routine was 5 times faster than the built in
sort for my needs. But I can't use it if its broke! (original and optimized
both broke)
(defmacro while (test &rest body)
`(do ()
((not ,test))
,@body))
(defun quicksort (vec l r)
(let ((i l)
(j r)
(p (svref vec (round (+ l r) 2)))) ; 1
(while (<= i j) ; 2
(while (< (svref vec i) p) (incf i))
(while (> (svref vec j) p) (decf j))
(when (<= i j)
(rotatef (svref vec i) (svref vec j))
(incf i)
(decf j)))
(if (> (- j l) 1) (quicksort vec l j)) ; 3
(if (> (- r i) 1) (quicksort vec i r)))
vec)
(setq aaa (vector 1.0 10.0 2.0 9.0 3.0 8.0 4.0 7.0 5.0 6.0))
#(1.0 10.0 2.0 9.0 3.0 8.0 4.0 7.0 5.0 6.0)
(quicksort aaa 0 9)
#(1.0 2.0 3.0 4.0 5.0 6.0 8.0 7.0 9.0 10.0)
--
John Watton
Alcoa Inc.
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On Wed, 14 Apr 1999 15:18:01 GMT, ···········@alcoa.com wrote:
>Does anyone know how to fix it?
> (if (> (- j l) 1) (quicksort vec l j)) ; 3
> (if (> (- r i) 1) (quicksort vec i r)))
(if (>= (- j l) 1) (quicksort vec l j))
(if (>= (- r i) 1) (quicksort vec i r)))
I'd say...
/L/e/k/t/u
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i
iQA/AwUBNxSzR/4C0a0jUw5YEQLxLgCfVWw1wlz9buGuvsoRmcB6uRifRiEAoMte
I8S4OOWEn7GZiCcdSzD+LxoU
=lgmB
-----END PGP SIGNATURE-----
From: ·····@corman.net
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <7f2k5k$juu$1@nnrp1.dejanews.com>
In article <············@nnrp1.dejanews.com>,
···········@alcoa.com wrote:
> I wanted to use the quicksort routine in Graham's book ANSI Common Lisp but
> it is broken. Does anyone know how to fix it? Is there another lisp sort
> routine someone can recommend? I need a fast sort of a vector of floats and
> an optimized version of Graham's routine was 5 times faster than the built in
> sort for my needs. But I can't use it if its broke! (original and optimized
> both broke)
I had the same problem (with the code from Graham's book).
I just ported a C implementation I found somewhere. The following
is distributed with Corman Lisp. I hope it helps you. Let me know
if you find any bugs in it :-)
-Roger Corman
;;;;
;;;; File: quicksort.lisp
;;;; Contents: Quicksort implementation.
;;;;
;;;; Common Lisp code by Roger Corman
;;;;
(defun quicksort (vec lo hi comp-func)
(if (> hi lo)
(let* ((mid (round (+ lo hi) 2))
(i lo)
(j (+ hi 1))
(p (elt vec mid)))
(rotatef (elt vec mid) (elt vec lo)) ;; swap mid element to first
(loop
(loop do (incf i)
until (or (> i hi) (funcall comp-func p (elt vec i))))
(loop do (decf j)
until (or (<= j lo) (funcall comp-func (elt vec j) p)))
(if (< j i) (return))
(rotatef (elt vec i)(elt vec j)))
(rotatef (elt vec lo) (elt vec j)) ;;put partition element in place
(quicksort vec lo (- j 1) comp-func) (quicksort vec i hi comp-func))) vec)
(defun qsort (sequence comp-func)
(quicksort sequence 0 (- (length sequence) 1) comp-func))
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
·····@corman.net writes:
> I had the same problem (with the code from Graham's book). I just
> ported a C implementation I found somewhere. The following is
> distributed with Corman Lisp. I hope it helps you. Let me know if
> you find any bugs in it :-)
What is the copyright status (license) of that code?
···········@alcoa.com writes:
> I wanted to use the quicksort routine in Graham's book ANSI Common Lisp but
> it is broken. Does anyone know how to fix it? Is there another lisp sort
Out of curiosity, any reason why you are using this routine rather than the
sort function that is part of common lisp?
Sunil
From: ···········@alcoa.com
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <7f2uqm$tue$1@nnrp1.dejanews.com>
In article <···············@whizzy.cc.gatech.edu>,
Sunil Mishra <·······@whizzy.cc.gatech.edu> wrote:
> Out of curiosity, any reason why you are using this routine rather than the
> sort function that is part of common lisp?
>
> Sunil
>
Speed. The built in sort takes a comparison function as an input. It probably
then uses apply, whereas a custom sort will have the comparison function
included. Also the built in sort takes a sequence as input and is unlikely to
optimize for a simple-array of single-floats which is what I use. Graham's
quicksort optimized with the necessary declarations (and corrected as
previous posters have suggested) is 5 times faster than the built-in using
Franz ACL 5.0 for single-float simple-arrays of length 25.
My application is a median filter for image processing. With a median filter
a pixel value is replaced with the median value in some range around the
pixel. It is very effective at removing random noise. I have also implemented
an Olympic filter which is related to the median. An Olympic filter replaces
a pixel with the average of some number of middle values about a pixel, after
throwing out the highs and lows.
--
John Watton
Alcoa Inc.
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
From: Philip Lijnzaad
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <u790bugtdg.fsf@ebi.ac.uk>
On Wed, 14 Apr 1999 20:46:15 GMT,
"John" == john watton <···········@alcoa.com> writes:
John> Speed.
Just a quick note: quicksort is apparently not the best general purpose
algorithm: it is not stable (so any previous ordering among things sorting
equal in the current invocation is lost), and the run-time becomes worse and
worse the more order there is in the list before sorting (for this reason,
many quicksorts randomize their input first, which undoes part of the speed
advantages).
Numerical Recipes in * (Press et al.; I wonder when the Lisp edition is due
:-) recommend heap-sort (also O(NlogN)) ; I can well imagine that a
standard sort function in Lisp is implemented using heap-sort.
But for your application it sounds like quicksort could be appropriate,
although for small N, quicksort might be slower (due to function calling
overhead) than sorting by straight-insertion (O(N**2)) or shell-sort
(O(N**1.5)).
Cheers,
Philip
--
To accurately forge this signature, use a lucidatypewriter-medium-12 font
-----------------------------------------------------------------------------
Philip Lijnzaad, ········@ebi.ac.uk | European Bioinformatics Institute
+44 (0)1223 49 4639 | Wellcome Trust Genome Campus, Hinxton
+44 (0)1223 49 4468 (fax) | Cambridgeshire CB10 1SD, GREAT BRITAIN
PGP fingerprint: E1 03 BF 80 94 61 B6 FC 50 3D 1F 64 40 75 FB 53
From: Lars Marius Garshol
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <wkk8vet9wk.fsf@ifi.uio.no>
* Philip Lijnzaad
|
| Just a quick note: quicksort is apparently not the best general
| purpose algorithm: it is not stable (so any previous ordering among
| things sorting equal in the current invocation is lost),
This depends on how you choose your pivot. With a median-of-three
pivot chosen from the first, middle and last elements this isn't a
problem in real life, although it can be in theory.
| and the run-time becomes worse and worse the more order there is in
| the list before sorting
Provided you use a poor pivoting strategy...
| (for this reason, many quicksorts randomize their input first, which
| undoes part of the speed advantages).
Where did you hear this?
--Lars M.
From: Gareth McCaughan
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <86n20a9hs6.fsf@g.pet.cam.ac.uk>
Lars Marius Garshol wrote:
> This depends on how you choose your pivot. With a median-of-three
> pivot chosen from the first, middle and last elements this isn't a
> problem in real life, although it can be in theory.
There are plausible input datasets that make median-of-3 quicksort
perform really badly. See the article by Bentley and McIlroy called
"Engineering a sort function" in (I think) an issue of "Software
Practice and Experience" something like 10 years ago.
You need to be a little more sophisticated if you want a really
robust quicksort.
(I entirely disagree, though, with the bizarre opinion expressed
in NRiC that heapsort is "better" than quicksort. A well-engineered
quicksort will generally perform much better than heapsort. For
some datasets mergesort is better, though.)
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
From: Philip Lijnzaad
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <u7u2uhk0r6.fsf@ebi.ac.uk>
On 15 Apr 1999 13:12:27 +0200,
"Lars" == Lars Marius Garshol <······@ifi.uio.no> writes:
Lars> This depends on how you choose your pivot. With a median-of-three
Lars> pivot chosen from the first, middle and last elements this isn't a
Lars> problem in real life, although it can be in theory.
would you use quicksort for doing a median of three ? (Num. Rec. reckons
that for sets <= 7, straight insertion is faster than qsort)
Lars> | and the run-time becomes worse and worse the more order there is in
Lars> | the list before sorting
Lars> Provided you use a poor pivoting strategy...
does this imply that at every step you'd have to scan the partition for the
right pivot ? I imagine that's costly, no?
Lars> | (for this reason, many quicksorts randomize their input first, which
qsort in the GNU C library and the one in Numerical Recipes do this; the
latter says it follows Knuth (which I don't have handy).
Lars> | undoes part of the speed advantages).
this bit is probably not very grave, as you can do it on the fly. Cheers,
Philip
--
To accurately forge this signature, use a lucidatypewriter-medium-12 font
-----------------------------------------------------------------------------
Philip Lijnzaad, ········@ebi.ac.uk | European Bioinformatics Institute
+44 (0)1223 49 4639 | Wellcome Trust Genome Campus, Hinxton
+44 (0)1223 49 4468 (fax) | Cambridgeshire CB10 1SD, GREAT BRITAIN
PGP fingerprint: E1 03 BF 80 94 61 B6 FC 50 3D 1F 64 40 75 FB 53
From: Lars Marius Garshol
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <wkzp49cruo.fsf@ifi.uio.no>
* Lars Marius Garshol
|
| This depends on how you choose your pivot. With a median-of-three
| pivot chosen from the first, middle and last elements this isn't a
| problem in real life, although it can be in theory.
* Philip Lijnzaad
|
| would you use quicksort for doing a median of three ?
No. I'd do the median of the first, middle and last element. That will
deal with the cases where the input is more or less ordered and should
perform acceptably in most other cases.
| does this imply that at every step you'd have to scan the partition
| for the right pivot ? I imagine that's costly, no?
This should be answered by the above.
--Lars M.
From: Hanley
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <371A1D99.61798B03@nmia.com>
Philip Lijnzaad wrote:
(for this reason,
> many quicksorts randomize their input first, which undoes part of the speed
> advantages).
No. No reasonably-written quicksort does this. It is far faster
and simpler to choose the pivot element randomly. It has the same
effect, and reduces the overhead of reshuffling.
dave
From: Lars Marius Garshol
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <wkr9pmtfz9.fsf@ifi.uio.no>
* john watton
|
| Graham's quicksort optimized with the necessary declarations (and
| corrected as previous posters have suggested) is 5 times faster than
| the built-in using Franz ACL 5.0 for single-float simple-arrays of
| length 25.
For arrays that short you may find insertion sort to be faster. From
what I've been told, industrial-strength quicksort implementations
usually use insertion sort for array segments smaller than 20.
--Lars M.
Lars Marius Garshol <······@ifi.uio.no> writes:
> * john watton
> |
> | Graham's quicksort optimized with the necessary declarations (and
> | corrected as previous posters have suggested) is 5 times faster than
> | the built-in using Franz ACL 5.0 for single-float simple-arrays of
> | length 25.
>
> For arrays that short you may find insertion sort to be faster. From
> what I've been told, industrial-strength quicksort implementations
> usually use insertion sort for array segments smaller than 20.
>
> --Lars M.
That's what I had read too, but the reason was quite odd and I'm not sure
it will hold up in the lisp world. The reason they had stated was that
recursing down to a single element has a very high recursion overhead, so
some other sort turns out to be far more efficient. The book went on to
recommend shell-sort, since it is the most efficient of the (non-recursive)
linear sorting algorithms.
Sunil
From: Lars Marius Garshol
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <wkyajtcrnp.fsf@ifi.uio.no>
* Lars Marius Garshol
|
| For arrays that short you may find insertion sort to be faster. From
| what I've been told, industrial-strength quicksort implementations
| usually use insertion sort for array segments smaller than 20.
* Sunil Mishra
|
| That's what I had read too, but the reason was quite odd and I'm not
| sure it will hold up in the lisp world. The reason they had stated
| was that recursing down to a single element has a very high
| recursion overhead, so some other sort turns out to be far more
| efficient.
This is what I've heard as well, but there's also a bit of overhead in
the general book-keeping to start each recursive quick-sort so it may
well hold true even if function calls are inexpensive.
At least, it's worth a try, especially since insertion sort is so
simple to program.
| The book went on to recommend shell-sort, since it is the most
| efficient of the (non-recursive) linear sorting algorithms.
So it is, but most of the advantage stems from it being able to
quickly transport badly placed elements to positions closer to the
correct ones. For small arrays it's very likely that the book-keeping
involved with the different sorting distances will undo this.
At any rate, I would start with insertion sort. If you do it right,
the transition to shell sort is just question of inserting an extra
loop.
--Lars M:
(...) ;quicksort vs. insertion sort vs. shellsort
I don't recall anyone mentioning heapsort in this thread.
I won't claim it is the best choice for small arrays, but
it has the nice property of performing well even in the
worst case (quicksort is fastest in the average case
but not so in the worst case).
In other words, which is the sorting algorithm of choice
depends on several things, and one of them may be a
requirement to guarantee speed under _any_ circumstances.
(Thou shalt know and meet thy requirements.)
In any case, this is well covered by a lot of literature,
so don't just take it from my quick summary.
--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
From: Hanley
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <371A1FE6.57D49A75@nmia.com>
Sunil Mishra wrote:
> Lars Marius Garshol <······@ifi.uio.no> writes:
>
> > * john watton
> > |
> > | Graham's quicksort optimized with the necessary declarations (and
> > | corrected as previous posters have suggested) is 5 times faster than
> > | the built-in using Franz ACL 5.0 for single-float simple-arrays of
> > | length 25.
> >
> > For arrays that short you may find insertion sort to be faster. From
> > what I've been told, industrial-strength quicksort implementations
> > usually use insertion sort for array segments smaller than 20.
> >
> > --Lars M.
>
> That's what I had read too, but the reason was quite odd and I'm not sure
> it will hold up in the lisp world. The reason they had stated was that
> recursing down to a single element has a very high recursion overhead, so
> some other sort turns out to be far more efficient.
Also, insertion sort has a lower constant overhead then quicksort, so at some
point it becomes more efficient.
> The book went on to
> recommend shell-sort, since it is the most efficient of the (non-recursive)
> linear sorting algorithms.
The book is wrong then. No sort has to be recursive, but heapsort isn't
recursive by nature at all.
dave
Hanley <····@nmia.com> writes:
> The book is wrong then. No sort has to be recursive, but heapsort isn't
> recursive by nature at all.
>
> dave
Well, I used recursive incorrectly here. I simply meant an algorithm that
does not rely on partially sorting and merging subsets of the entire
vector, which quicksort and merge sort do. Heap sort does not, I stand
corrected.
Sunil
From: Bernhard Pfahringer
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <7f4jp0$1jik$1@www.univie.ac.at>
Hi, for a real speedup try the following simple modification.
Insight: Need only sort the subpart which will contain the median.
(defun quick-median (vec l r &optional (median-position (ash (length vec) -1)))
(declare (type (simple-array single-float (*)) vec)
(type fixnum l r median-position))
(when (<= l median-position r)
(let ((i l)
(j r)
(p (aref vec (round (+ l r) 2))))
(declare (type single-float p)
(type fixnum i j))
(while (<= i j)
(while (< (aref vec i) p) (incf i))
(while (> (aref vec j) p) (decf j))
(when (<= i j)
(rotatef (aref vec i) (aref vec j))
(incf i)
(decf j)))
(if (>= (- j l) 1) (quick-median vec l j))
(if (>= (- r i) 1) (quick-median vec i r)))
(aref vec median-position)))
Bernhard
PS: There are linear-time approximators for the median
(J.Pearl: A Space-Efficient On-Line Method of Computing Quantile Estimates,
in J.Algorithms, 2(2):164-177, 1981)
but for your small vectors these approximations might not be what you want.
--
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for http://www.ai.univie.ac.at/~bernhard/
Artificial Intelligence ········@ai.univie.ac.at
From: Duane Rettig
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <4ogkpho5i.fsf@beta.franz.com>
···········@alcoa.com writes:
> In article <···············@whizzy.cc.gatech.edu>,
> Sunil Mishra <·······@whizzy.cc.gatech.edu> wrote:
>
> > Out of curiosity, any reason why you are using this routine rather than the
> > sort function that is part of common lisp?
> >
> > Sunil
> >
>
> Speed. The built in sort takes a comparison function as an input. It probably
> then uses apply, whereas a custom sort will have the comparison function
> included. Also the built in sort takes a sequence as input and is unlikely to
> optimize for a simple-array of single-floats which is what I use.
Actually, we do optimize for (simple-array t (*)), and I was slightly
unprepared for the resultant comparison, although I can explain it
(see below). For such simple general vectors, we use a merge-sort, which is
much faster than quicksort, although for large arrays it must allocate an
extra workspace vector. For specialized arrays, we stay with the older
quicksort algorithm.
> Graham's
> quicksort optimized with the necessary declarations (and corrected as
> previous posters have suggested) is 5 times faster than the built-in using
> Franz ACL 5.0 for single-float simple-arrays of length 25.
It turns out that trying to sort unboxed values (i.e. in a specialized array)
causes huge amounts of boxing. I was prepared to expect a 5x or 10x speed
difference, but not 200x...
USER(1): (setq a (make-array 2500 :element-type 'single-float :initial-contents
(loop for i single-float from 1.0 to 2500.0 collect i)))
#(1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0 ...)
USER(2): (setq b (make-array 2500 :initial-contents
(loop for i single-float from 1.0 to 2500.0 collect i)))
#(1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0 ...)
USER(3): (time (sort a #'>))
; cpu time (non-gc) 5,130 msec user, 10 msec system
; cpu time (gc) 570 msec user, 0 msec system
; cpu time (total) 5,700 msec user, 10 msec system
; real time 5,720 msec
; space allocation:
; 5,000 cons cells, 0 symbols, 50,020,016 other bytes, 0 static bytes
#(2500.0 2499.0 2498.0 2497.0 2496.0 2495.0 2494.0 2493.0 2492.0 2491.0
...)
USER(4): (time (sort b #'>))
; cpu time (non-gc) 20 msec user, 10 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 20 msec user, 10 msec system
; real time 37 msec
; space allocation:
; 2 cons cells, 0 symbols, 32 other bytes, 0 static bytes
#(2500.0 2499.0 2498.0 2497.0 2496.0 2495.0 2494.0 2493.0 2492.0 2491.0
...)
USER(5):
If you look at the bytes consed, the reason becomes clear: the specialized
array conses over 50Mb, and the general vector effectively doesn't cons.
The consing is caused by the boxing up of single-float pairs that is done
in order to make each comparison.
It's been a while since I looked at sort speed, when I originally got about
a 5x speedup in general vectors by reducing consing and going with msort.
I can see that I need to take another look at sort, wrt specialized arrays.
Two things might be possible: reducing the number of comparisons by going
to a merge-sort, and/or allowing the predicate to work on unboxed values
(this one might be hard to do for the general case).
I assume that the times for most algorithms will be swamped by the boxing
problem, and that this is a problem on all lisps that provide for
specialized vectors of unboxed values. It might be interesting to see
results in other lisps.
> My application is a median filter for image processing. With a median filter
> a pixel value is replaced with the median value in some range around the
> pixel. It is very effective at removing random noise. I have also implemented
> an Olympic filter which is related to the median. An Olympic filter replaces
> a pixel with the average of some number of middle values about a pixel, after
> throwing out the highs and lows.
Given the nature of the problem, and the sizes of your arrays (which I took
from another post to average 25), and given the significant time difference
between general and specialized vectors, you might consider two alternative
approaches, trying for each approach both the built-in sort and yours:
1. Go with general vectors (i.e. (simple-array t (*)) ) only. This may cause
unacceptable speed loss for non-sorting data manipulation, but it might be
worth a try.
2. Use the specialized arrays for most purposes, and copy the array into
a general array for the sort and back out again. The consing cost of
this is an N-sized array once (unless you stack-allocate it), plus N
single-floats each time you want to sort. Pretty grotesque solution,
but you may find it easier to swallow if you can catch some of that
200x speed difference.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
The result are similar in LWW but with a less radical speed difference.
Here are the results for LispWorks Windows:
CL-USER 10 > (extended-time (sort a #'>))
1.9 seconds used.
Standard Allocation 50020000 bytes.
Fixlen Allocation 0 bytes.
total gc activity = 0.852
main promote ( 2 calls) = 0.31
mark and sweep ( 194 calls) = 0.821
internal promote ( 2 calls) = 0.000
promote ( 0 calls) = 0.000
fixup ( 2 calls) = 0.16
compact ( 0 calls) = 0.000
CL-USER 11 > (extended-time (sort b #'>))
0.6 seconds used.
Standard Allocation 0 bytes.
Fixlen Allocation 0 bytes.
total gc activity = 0.000
main promote ( 0 calls) = 0.000
mark and sweep ( 0 calls) = 0.000
internal promote ( 0 calls) = 0.000
promote ( 0 calls) = 0.000
fixup ( 0 calls) = 0.000
compact ( 0 calls) = 0.000
Seems that sometimes it could be better to use unspecialized arrays.
Marc Battyani
Duane Rettig <·····@franz.com> wrote in message
··················@beta.franz.com...
>....
> It turns out that trying to sort unboxed values (i.e. in a specialized
array)
> causes huge amounts of boxing. I was prepared to expect a 5x or 10x speed
> difference, but not 200x...
>
> USER(1): (setq a (make-array 2500 :element-type 'single-float
:initial-contents
> (loop for i single-float from 1.0 to 2500.0 collect
i)))
> #(1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0 ...)
> USER(2): (setq b (make-array 2500 :initial-contents
> (loop for i single-float from 1.0 to 2500.0 collect
i)))
> #(1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0 ...)
> USER(3): (time (sort a #'>))
> ; cpu time (non-gc) 5,130 msec user, 10 msec system
> ; cpu time (gc) 570 msec user, 0 msec system
> ; cpu time (total) 5,700 msec user, 10 msec system
> ; real time 5,720 msec
> ; space allocation:
> ; 5,000 cons cells, 0 symbols, 50,020,016 other bytes, 0 static bytes
> #(2500.0 2499.0 2498.0 2497.0 2496.0 2495.0 2494.0 2493.0 2492.0 2491.0
> ...)
> USER(4): (time (sort b #'>))
> ; cpu time (non-gc) 20 msec user, 10 msec system
> ; cpu time (gc) 0 msec user, 0 msec system
> ; cpu time (total) 20 msec user, 10 msec system
> ; real time 37 msec
> ; space allocation:
> ; 2 cons cells, 0 symbols, 32 other bytes, 0 static bytes
> #(2500.0 2499.0 2498.0 2497.0 2496.0 2495.0 2494.0 2493.0 2492.0 2491.0
> ...)
> USER(5):
>
> If you look at the bytes consed, the reason becomes clear: the specialized
> array conses over 50Mb, and the general vector effectively doesn't cons.
> The consing is caused by the boxing up of single-float pairs that is done
> in order to make each comparison.
>
> It's been a while since I looked at sort speed, when I originally got
about
> a 5x speedup in general vectors by reducing consing and going with msort.
> I can see that I need to take another look at sort, wrt specialized
arrays.
> Two things might be possible: reducing the number of comparisons by going
> to a merge-sort, and/or allowing the predicate to work on unboxed values
> (this one might be hard to do for the general case).
>
> I assume that the times for most algorithms will be swamped by the boxing
> problem, and that this is a problem on all lisps that provide for
> specialized vectors of unboxed values. It might be interesting to see
> results in other lisps.
> --
> Duane Rettig Franz Inc. http://www.franz.com/ (www)
> 1995 University Ave Suite 275 Berkeley, CA 94704
> Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
"Marc Battyani" <·············@csi.com> writes:
> The result are similar in LWW but with a less radical speed difference.
> Here are the results for LispWorks Windows:
>
> CL-USER 10 > (extended-time (sort a #'>))
>
> 1.9 seconds used.
> Standard Allocation 50020000 bytes.
> Fixlen Allocation 0 bytes.
> total gc activity = 0.852
> main promote ( 2 calls) = 0.31
> mark and sweep ( 194 calls) = 0.821
> internal promote ( 2 calls) = 0.000
> promote ( 0 calls) = 0.000
> fixup ( 2 calls) = 0.16
> compact ( 0 calls) = 0.000
>
> CL-USER 11 > (extended-time (sort b #'>))
>
> 0.6 seconds used.
> Standard Allocation 0 bytes.
> Fixlen Allocation 0 bytes.
> total gc activity = 0.000
> main promote ( 0 calls) = 0.000
> mark and sweep ( 0 calls) = 0.000
> internal promote ( 0 calls) = 0.000
> promote ( 0 calls) = 0.000
> fixup ( 0 calls) = 0.000
> compact ( 0 calls) = 0.000
>
> Seems that sometimes it could be better to use unspecialized arrays.
>
> Marc Battyani
Apologies for the extra-wide columns, but that is what the lisp output was.
LWW 4.1 on an O2 seems to do a little better as far as time comparisons go,
but the speed compared to your windows box is pretty dismal.
CL-USER 121 > (extended-time (sort a #'>))
user time = 9.909
system time = 0.050
Elapsed time = 0:00:11
Allocation = 25010372 bytes
0 Page faults
total gc activity = 1.153094 / 1.140913 / 0.00000012181
main promote ( 5 calls) = 0.00000028034 / 0.00000022723 / 0.0000005311
mark and sweep ( 49 calls) = 1.125060 / 1.118190 / 0.0000006870
internal promote ( 5 calls) = 0.00000095 / 0.00000069 / 0.00000026
promote ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
fixup ( 5 calls) = 0.00000016424 / 0.00000011755 / 0.0000004669
compact ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
NIL
CL-USER 122 > (extended-time (sort b #'>))
user time = 7.478
system time = 0.025
Elapsed time = 0:00:08
Allocation = 0 bytes
0 Page faults
total gc activity = 0.0000000 / 0.0000000 / 0.0000000
main promote ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
mark and sweep ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
internal promote ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
promote ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
fixup ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
compact ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
NIL
I also tried a vector copy:
CL-USER 123 > (extended-time (coerce a '(vector t)))
user time = 0.007
system time = 0.002
Elapsed time = 0:00:00
Allocation = 32792 bytes
2 Page faults
total gc activity = 0.0000000 / 0.0000000 / 0.0000000
main promote ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
mark and sweep ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
internal promote ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
promote ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
fixup ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
compact ( 0 calls) = 0.0000000 / 0.0000000 / 0.0000000
NIL
Looks like copying then sorting is going to be *far* more efficient.
Sunil
From: Hanley
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <371A1F5F.B980AEA7@nmia.com>
···········@alcoa.com wrote:
My application is a median filter for image processing. With a median filter
> a pixel value is replaced with the median value in some range around the
> pixel. It is very effective at removing random noise. I have also implemented
> an Olympic filter which is related to the median. An Olympic filter replaces
> a pixel with the average of some number of middle values about a pixel, after
> throwing out the highs and lows.
In this case, you *don't* want to do a regular sort of the data if you
are really trying to optimize for speed!
Medians can be derived in constant time, but the algorithm is hard and
the overhead is high.
On the other hand, since you are using your own sort, you can do an
optimization:
Do the usual quicksort partition.
Iterate over the partition which will contain the median. You can know this
because the place which will hold the median is the middle element.
This will halve the algorithmic complexity, and make the whole operation be
in-place, and also mean that it will make no function calls.
Furthermore, you can write something analogus to a sort-tree if you're
trying to find the median of a small number of elements. This would mean
no moving of data. Kewl. :) Need a lot more time to expalin this, however.
dave
From: Gareth McCaughan
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <86yajpymmu.fsf@g.pet.cam.ac.uk>
Dave Hanley wrote:
> Medians can be derived in constant time, but the algorithm is hard and
> the overhead is high.
*Constant* time?! You mean linear, yes?
> On the other hand, since you are using your own sort, you can do an
> optimization:
>
> Do the usual quicksort partition.
>
> Iterate over the partition which will contain the median. You can know this
> because the place which will hold the median is the middle element.
>
> This will halve the algorithmic complexity, and make the whole operation be
> in-place, and also mean that it will make no function calls.
This actually produces a linear-time algorithm (or, at least, an
expected-linear-time algorithm -- you can lose if you repeatedly
pick bad pivots, just as in quicksort; the same sort of techniques
work for improving pivoting, too). The recurrence is something
like T(n) = n + T(n/2), which clearly gives T(n) = n + n/2 + n/4 + ...,
and that's O(n).
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
Sunil Mishra <·······@whizzy.cc.gatech.edu> writes:
> ···········@alcoa.com writes:
>
> > I wanted to use the quicksort routine in Graham's book ANSI Common Lisp but
> > it is broken. Does anyone know how to fix it? Is there another lisp sort
>
> Out of curiosity, any reason why you are using this routine rather
> than the sort function that is part of common lisp?
I believe John's next sentence explains it:
I need a fast sort of a vector of floats and an optimized version
of Graham's routine was 5 times faster than the built in sort for
my needs.
Why use a QUICKSORT routine before you figured out that the regular
SORT is the bottleneck of your program?
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
From: ···········@alcoa.com
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <7f4pt1$evv$1@nnrp1.dejanews.com>
In article <··············@copernico.parades.rm.cnr.it>,
Marco Antoniotti <·······@copernico.parades.rm.cnr.it> wrote:
>
> Why use a QUICKSORT routine before you figured out that the regular
> SORT is the bottleneck of your program?
>
Franz's very nice time profiler told me that my application (median filter)
was spending 87% of its time in sort. So I concluded that it was the
bottleneck and on a whim tried an external sort which immediately gave me a 5
times speedup. I am happy and not about to knock the built in sort one bit.
Afterall, since becoming a lisp programmer in 1985 this is the first time I
have resorted to a specialized sort.
--
John Watton
Alcoa Inc.
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
From: Christopher R. Barry
Subject: Graham's variable names. (was Re: Quicksort in Graham's ANSI Common Lisp broken)
Date:
Message-ID: <87k8vesacx.fsf@2xtreme.net>
(Not so) modern symbol-completion capable editors let you use more
descriptive variable names with the same ammount of typing. Lisp gives
you a real word-delimeter character so you don't have to tolerate crap
like gtk_do_something_lame or ImAReallyCuteJavaOrCeePlusPlusName and
use variable names like i, j, k, l....
#include <stdlib.h>
/* swap two ints */
int sw(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
return 0;
}
/* iterative quicksort (average execution time: O(NlogN)) */
int qs(int *h, int N)
{
int n=0,m=1,k=0,p=0,q=N,r,w,b,z;
int *x=malloc(sizeof(int)*N),*y=malloc(sizeof(int)*N);
if(!x||!y)return 1;
while(m<N)n++,m*=2;
while(k||q-p>1)
if(q-p<2)p=x[--k],q=y[k];
else
{
z=h[((w=r=p)+(b=q))/2];
while(w-b)h[w]<z?sw(h+r++,h+w++):h[w]-z?sw(h+--b,h+w):w++;
r-p<=q-w?x[k]=w,y[k++]=q,q=r:(x[k]=p,y[k++]=r,p=w);
}
return 0;
}
Christopher
* ···········@alcoa.com, 4/14/1999 - 15:18
| I wanted to use the quicksort routine in Graham's book ANSI Common Lisp but
| it is broken.
m.. Let me add one more bug to this list. I've read ANSI Common Lisp last
year, and came to know the binary search tree algorithm is broken and
reported it to Paul but didn't get any response. I don't know if there's
any errata about this book but as long as I see in his onlisp and acl book
homepage, I can't see any corrections about that.
--
Chung jae youn
··········@pllab.kaist.ac.kr
http://pllab.kaist.ac.kr/~jay
* Jae-youn Chung wrote:
> m.. Let me add one more bug to this list. I've read ANSI Common Lisp last
> year, and came to know the binary search tree algorithm is broken and
> reported it to Paul but didn't get any response. I don't know if there's
> any errata about this book but as long as I see in his onlisp and acl book
> homepage, I can't see any corrections about that.
There is a new edition due pretty soon I think (may already be out) --
perhaps that fixes the bugs?
--tim
From: ···········@alcoa.com
Subject: Re: Quicksort in Graham's ANSI Common Lisp broken
Date:
Message-ID: <7f8llv$tbm$1@nnrp1.dejanews.com>
In article <···············@lostwithiel.tfeb.org>,
Tim Bradshaw <···@tfeb.org> wrote:
> There is a new edition due pretty soon I think (may already be out) --
> perhaps that fixes the bugs?
Some time ago the Prentice-Hall web site said the 2nd edition was due this
month (April 1999), but when I tried to order a copy I was told not it was
available until next year.
--
John Watton
Alcoa Inc.
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own