alexandria merge requestshttps://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests2019-12-06T11:14:54Zhttps://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/17Re-implement median function using the quick-select algorithm2019-12-06T11:14:54ZAnish MoorthyRe-implement median function using the quick-select algorithmI 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, whi...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)))))))
```Philipp MarekPhilipp Marekhttps://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/16Remove the orphaned export ORDINARY-LAMBDA-LIST-KEYWORDS2019-05-28T05:48:13ZlovroluRemove the orphaned export ORDINARY-LAMBDA-LIST-KEYWORDSFixes #8Fixes #8https://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/15Improve docstrings for WITH-GENSYMS and ONCE-ONLY2019-05-25T18:28:46ZlovroluImprove docstrings for WITH-GENSYMS and ONCE-ONLYI've made explicit what the point of `once-only` is and how exactly it works, especially regarding its `initform`s.I've made explicit what the point of `once-only` is and how exactly it works, especially regarding its `initform`s.https://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/14Added types and autoinlining functions.2023-09-09T20:14:07ZSpenser TruexAdded types and autoinlining functions.Sorry, I messed up the old worktree; had to start a new project.
All code taken and modified from the old CLOCC ext.lisp http://clocc.sourceforge.net/dist/port.html
Tests pass, and include error throwing on the types.
Sorry, I messed up the old worktree; had to start a new project.
All code taken and modified from the old CLOCC ext.lisp http://clocc.sourceforge.net/dist/port.html
Tests pass, and include error throwing on the types.
https://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/12WIP: Revive autoinline and typed variables/constant macros from CLOSS's PORT ...2019-04-29T10:13:11ZSpenser TruexWIP: Revive autoinline and typed variables/constant macros from CLOSS's PORT ext.lispModified `define-constant` so that a type could optionally be added.
Copied and renamed two functions from PORT ext.lisp ("extensions"), which allow for automatically generation `definline` clauses on defuns, and for defining global v...Modified `define-constant` so that a type could optionally be added.
Copied and renamed two functions from PORT ext.lisp ("extensions"), which allow for automatically generation `definline` clauses on defuns, and for defining global variables with type similarly less verbosely.
`defcustom` is for defining global variables with type.
Includes tests. I didn't modify any code in alexandria to use these, but I defined them in the first file (definitions.lisp) in the asd, so they could be used throughout if wanted.
Looking to also do shell.lisp and sys.lisp (select functions that fit alexandria's goal). I hope this will be accepted.
https://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/11Update ASD2019-05-29T09:22:11ZPhilipp MarekUpdate ASDhttps://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/10Issue 52019-05-29T09:17:21ZPhilipp MarekIssue 5https://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/9Avoid duplicate logic in WHEN-LET* (take 2)2019-05-29T09:23:24ZPhilipp MarekAvoid duplicate logic in WHEN-LET* (take 2)By using an explicit PROGN we can interpolate straight into the LET.
The PROGN shouldn't matter, as the WHEN interferes with DECLAREs anyway.By using an explicit PROGN we can interpolate straight into the LET.
The PROGN shouldn't matter, as the WHEN interferes with DECLAREs anyway.https://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/8Correct the documentation string of the SWITCH macro2018-12-03T07:08:45ZMomchil IvanovCorrect the documentation string of the SWITCH macrohttps://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/7Master2018-11-08T16:57:41ZPhilipp MarekMasterMost commits are straightforward; if WHEN-LET* needs discussion, I'm on #lisp as well.Most commits are straightforward; if WHEN-LET* needs discussion, I'm on #lisp as well.https://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/5Change to "unspecified" in MAP-COMBINATIONS.2018-10-27T16:10:49ZPhilipp MarekChange to "unspecified" in MAP-COMBINATIONS.https://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/4Do not inline LENGTH on LispWorks.2018-11-08T16:57:53ZKamil ShakirovDo not inline LENGTH on LispWorks.Fixes compile-time warnings: "Inline expansion for LENGTH not found"Fixes compile-time warnings: "Inline expansion for LENGTH not found"https://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/3Docstring update in macros.lisp. Replace "," with ":" to match other similar…2018-11-08T16:56:49ZKnut Olav BøhmerDocstring update in macros.lisp. Replace "," with ":" to match other similar…Docstring update in macros.lisp. Replace "," with ":" to match other similar examples, and output example.Docstring update in macros.lisp. Replace "," with ":" to match other similar examples, and output example.https://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/2Docstrings fixes for housekeeping changes.2018-11-08T16:55:35ZJacek Złydachcommon-lisp.net@jacek.zlydach.plDocstrings fixes for housekeeping changes.I assume docstrings are meant to reflect argument names here.I assume docstrings are meant to reflect argument names here.https://gitlab.common-lisp.net/alexandria/alexandria/-/merge_requests/1update the mailing list links in the readme2017-04-23T12:13:30ZSmith Dhumbumroongupdate the mailing list links in the readmeUpdated the mailing list links in the readme to the up-to-date ones.Updated the mailing list links in the readme to the up-to-date ones.