1. 06 Dec, 2019 1 commit
    • 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
  2. 27 Nov, 2019 1 commit
  3. 29 May, 2019 3 commits
  4. 28 May, 2019 1 commit
  5. 25 May, 2019 3 commits
  6. 20 May, 2019 1 commit
  7. 03 Dec, 2018 1 commit
  8. 02 Dec, 2018 1 commit
  9. 19 Nov, 2018 1 commit
  10. 08 Nov, 2018 10 commits
  11. 31 Jan, 2018 1 commit
  12. 15 Aug, 2017 1 commit
  13. 14 Aug, 2017 2 commits
  14. 05 May, 2017 1 commit
  15. 10 Apr, 2017 2 commits
  16. 12 Feb, 2017 2 commits
  17. 22 Nov, 2016 1 commit
    • Steve Losh's avatar
      housekeeping · 85f82ed8
      Steve Losh authored
      fix typos in docstring and error messages.
      85f82ed8
  18. 27 Oct, 2016 5 commits
  19. 23 Aug, 2016 1 commit
    • Attila Lendvai's avatar
      numbers.lisp/lerp: The correct version is numerically stable, · 926a0666
      Attila Lendvai authored
      at the expense of an extra multiply. The unstable version can often be
      converted to a fast instruction on a lot of machines, though this is
      machine/implementation specific. As alexandria is more about correct code,
      than efficiency, and we're only talking about a single extra multiply,
      many would prefer the stable version.
      
      Patch by github.com/mfiano.
      926a0666
  20. 03 Apr, 2016 1 commit
    • Jan Moringen's avatar
      use implementation's EMPTYP when available · afaf1a16
      Jan Moringen authored
      Using the implementation's EMPTYP has the potential advantage of
      supporting user-defined sequence types (as is the case with SBCL).
      
      This commit tests for SEQUENCE:EMPTYP and defines ALEXANDRIA:EMPTYP in
      terms of it.
      
      For implementations that do not provide SEQUENCE:EMPTYP, nothing
      changes.
      afaf1a16