Skip to content
GitLab
Projects Groups Topics Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Register
  • Sign in
  • A alexandria
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributor statistics
    • Graph
    • Compare revisions
  • Issues 11
    • Issues 11
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 2
    • Merge requests 2
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Deployments
    • Deployments
    • Environments
    • Releases
  • Monitor
    • Monitor
    • Incidents
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Repository
  • Wiki
    • Wiki
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • alexandria
  • alexandria
  • Merge requests
  • !17

Re-implement median function using the quick-select algorithm

  • Review changes

  • Download
  • Email patches
  • Plain diff
Merged Anish Moorthy requested to merge anlsh/alexandria:master into master Nov 27, 2019
  • Overview 3
  • Commits 1
  • Pipelines 0
  • Changes 1

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)))))))
Assignee
Assign to
Reviewers
Request review from
Time tracking
Source branch: master