1. 25 Mar, 2020 2 commits
2. 16 Mar, 2020 1 commit
3. 05 Mar, 2020 1 commit
• 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

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 ->>.```
4. 04 Mar, 2020 7 commits
5. 25 Jan, 2020 1 commit
6. 10 Jan, 2020 1 commit
7. 06 Dec, 2019 1 commit
• 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```
8. 27 Nov, 2019 1 commit
• Re-implement median function using the quick-select algorithm · 46d8b0ad
Anish Moorthy authored
```The previous implementation of alexandria:median sorted the entire sequence and
chose/averaged the relevant elements, yielding an O(n log n) runtime. This
commit implements a linear-time algorithm as a special case of the
quick-select algorithm (https://en.wikipedia.org/wiki/Quickselect).```
9. 29 May, 2019 3 commits
10. 28 May, 2019 1 commit
11. 25 May, 2019 3 commits
12. 20 May, 2019 1 commit
13. 03 Dec, 2018 1 commit
14. 02 Dec, 2018 1 commit
15. 19 Nov, 2018 1 commit
16. 08 Nov, 2018 10 commits
17. 31 Jan, 2018 1 commit
18. 15 Aug, 2017 1 commit
19. 14 Aug, 2017 2 commits