Skip to content
Snippets Groups Projects
  1. Aug 21, 2020
  2. Jul 06, 2020
  3. Jun 17, 2020
  4. Mar 31, 2020
  5. Mar 27, 2020
  6. Mar 25, 2020
  7. Mar 16, 2020
  8. Mar 05, 2020
    • Andrea Richiardi's avatar
      Introduce line-up-first and line-up-last macros · 2e399427
      Andrea Richiardi authored
      This patch introduces the line-up-first and line-up-last macros in
      control-flow.  The macros have been popularized by Clojure and afterwards
      adopted in Emacs Lisp (see thread-first and thread-last in subr-x.el).
      
      This implementation is a port of the latter, where we use a common
      line-up-iter(ative) tail recursive function for computing the results.  The
      choice of the full name was made in the spirit of the library, conservatively
      avoiding new syntax like -> or ->>.
      2e399427
  9. Mar 04, 2020
  10. Jan 25, 2020
  11. Jan 10, 2020
  12. Dec 06, 2019
    • 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 alexandria/alexandria!17
      1224346a
  13. Nov 27, 2019
  14. May 29, 2019
  15. May 28, 2019
  16. May 25, 2019
  17. May 20, 2019
  18. Dec 03, 2018
  19. Dec 02, 2018
  20. Nov 19, 2018
  21. Nov 08, 2018
Loading