Skip to content

Re-implement median function using the quick-select algorithm

Anish Moorthy requested to merge anlsh/alexandria:master into master

I wanted to submit a re-implementation of alexandria:median. Currently the function works by fully sorting the sequence, which has a complexity of O(n log n). This commit implements it as a special case of the quick select algorithm, which brings its complexity down to O(n).

The new implementation is more complicated, though I think it's still simpler than some other algorithms in alexandria. Anyways, the performance gains are dramatic enough that I thought I'd at least submit the patch. I did some testing via the timing code below, and observed speedups of 5-10x even on sequences with just 100 elements.

I could also provide the quick select algorithm as its own function if there's any interest, though it seems like this would have to go into the alexandria-2 branch.

;; Speed-testing function
(defun test-median-speed (mag)
  (labels ((get-vec-median (vec)
             (if (oddp (length vec))
                 (aref vec (ash (length vec) -1))
                 (* 1/2 (+ (aref vec (ash (length vec) -1))
                           (aref vec (1- (ash (length vec) -1))))))))
    (let ((arr (loop for i from 0 upto (expt 10 mag) collect (random 1000000))))
      (assert (=
               (time (get-vec-median (sort (alexandria:copy-sequence 'vector arr) #'<)))
               (time (alexandria:median arr)))))))

Merge request reports