rif <[EMAIL PROTECTED]> writes: > What is the fastest way to sort a simple-array of double-floats in > CMUCL? Currently I'm using this: > > (declaim (optimize (speed 3) (safety 0) (debug 1))) > > (declaim (inline df-comp)) > (defun df-comp (df1 df2) > (declare (type double-float df1 df2)) > (< df1 df2)) > > (defun test-sort (arr) > (declare (type df-vec arr)) > (sort arr #'df-comp)) > > This compiles without any notes, but it conses a ton and is about 4x > slower than the equivalent C program that calls qsort. Given that I'm > sorting lots of arrays with millions of elements, I'd like to speed > this up if possible. I can always wrap qsort if I have to, but I was > wondering if there was a faster way to do it in CMUCL.
I looked a little at it, and it seems to me that a quicksort seems to do better in this case. This seems to be quite a bit faster: --- ;; From <URL: http://home.pipeline.com/~hbaker1/LQsort.html >, but not ;; the point of that article. (declaim (maybe-inline vqs split1 split2 qsort)) (defun vqs (v k m) ; Quicksort vector v from k up to m. (declare ;(fixnum k m) (type (simple-array double-float (*)) v)) (if (>= k m) v (let* ((x (aref v k)) ; Create a hole at k. (i (split1 v k (1- m) x))) ; Do partition. (setf (aref v i) x) ; Put x back into the hole. (vqs v k i) ; Quicksort v from k up to i. (vqs v (1+ i) m)))) ; Quicksort v from i+1 up to m. (defun split1 (v i j x) ; hole is at v(i). (declare ;(fixnum i j) (type (simple-array double-float (*)) v) (double-float x)) (if (= i j) i (let* ((vj (aref v j))) ; Copy elt. to vj. (if (< vj x) (progn (setf (aref v i) vj) (split2 v (1+ i) j x)) (split1 v i (1- j) x))))) (defun split2 (v i j x) ; hole is at v(j). (declare ;(fixnum i j) (type (simple-array double-float (*)) v) (double-float x)) (if (= i j) i (let* ((vi (aref v i))) ; Copy elt. to vi. (if (>= vi x) (progn (setf (aref v j) vi) (split1 v i (1- j) x)) (split2 v (1+ i) j x))))) (defun test-sort (arr) (declare (type (simple-array double-float (*)) arr)) (qsort arr)) --- Regards, 'mr -- [Emacs] is written in Lisp, which is the only computer language that is beautiful. -- Neal Stephenson, _In the Beginning was the Command Line_
