• Philipp Marek's avatar
    Merge branch 'master' into 'master' · 1224346a
    Philipp Marek authored
    Re-implement median function using the quick-select algorithm
    
    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)))))))
    ```
    
    See merge request !17
    1224346a
Name
Last commit
Last update
doc Loading commit data...
.boring Loading commit data...
.gitignore Loading commit data...
AUTHORS Loading commit data...
LICENCE Loading commit data...
README Loading commit data...
alexandria-tests.asd Loading commit data...
alexandria.asd Loading commit data...
arrays.lisp Loading commit data...
binding.lisp Loading commit data...
conditions.lisp Loading commit data...
control-flow.lisp Loading commit data...
definitions.lisp Loading commit data...
features.lisp Loading commit data...
functions.lisp Loading commit data...
hash-tables.lisp Loading commit data...
io.lisp Loading commit data...
lists.lisp Loading commit data...
macros.lisp Loading commit data...
numbers.lisp Loading commit data...
package.lisp Loading commit data...
sequences.lisp Loading commit data...
strings.lisp Loading commit data...
symbols.lisp Loading commit data...
tests.lisp Loading commit data...
types.lisp Loading commit data...