1. 16 Mar, 2020 1 commit
2. 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 ->>.```
3. 04 Mar, 2020 7 commits
4. 25 Jan, 2020 1 commit
5. 10 Jan, 2020 1 commit
6. 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```
7. 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).```
8. 29 May, 2019 3 commits
9. 28 May, 2019 1 commit
10. 25 May, 2019 3 commits
11. 20 May, 2019 1 commit
12. 03 Dec, 2018 1 commit
13. 02 Dec, 2018 1 commit
14. 19 Nov, 2018 1 commit
15. 08 Nov, 2018 10 commits
16. 31 Jan, 2018 1 commit
17. 15 Aug, 2017 1 commit
18. 14 Aug, 2017 2 commits
19. 05 May, 2017 1 commit
20. 10 Apr, 2017 1 commit
• Fix: earlier keys take priority in ALIST-HASH-TABLE and PLIST-HASH-TABLE · 0426bd2f
Attila Lendvai authored
```Also record tests for the new behavior.

This is a semantic change, but more in line with how alists and
plists are defined in the CLHS.

See '15.6. Association Lists' and 'property list' in the Glossary.

Reported by Christoph Arenz to alexandria-devel in
'Wrong handling of duplicate keys in alist-hash-table and plist-hash-table'.```