Skip to content

Instantly share code, notes, and snippets.

@purcell purcell/elisp-shuffles.el
Last active Jun 3, 2019

Embed
What would you like to do?
(defun key-quiz--shuffle-list (list)
"Shuffles LIST randomly, modying it in-place."
(dolist (i (reverse (number-sequence 1 (1- (length list)))))
(let ((j (random (1+ i)))
(tmp (elt list i)))
(setf (elt list i) (elt list j))
(setf (elt list j) tmp)))
list)
(defun key-quiz--shuffle-list-nreverse (list)
"Shuffles LIST randomly, modying it in-place."
(dolist (i (nreverse (number-sequence 1 (1- (length list)))))
(let ((j (random (1+ i)))
(tmp (elt list i)))
(setf (elt list i) (elt list j))
(setf (elt list j) tmp)))
list)
(defun elfeed--shuffle (seq)
"Destructively shuffle SEQ."
(let ((n (length seq)))
(prog1 seq ; don't use dotimes result (bug#16206)
(dotimes (i n)
(cl-rotatef (elt seq i) (elt seq (+ i (random (- n i)))))))))
(defun faster-seq-sort-by (function pred sequence)
"Sort SEQUENCE using PRED as a comparison function.
Elements of SEQUENCE are transformed by FUNCTION before being
sorted. FUNCTION must be a function of one argument."
;; This version is modified to avoid calling "random" twice every time the predicate is called.
(seq-map 'cdr
(sort (seq-map (lambda (x) (cons (funcall function x) x)) sequence)
(lambda (a b)
(funcall pred (car a) (car b))))))
(defun seq-sort-by--shuffle (seq)
(seq-sort-by (lambda (_) (random)) #'<= seq))
(defun faster-seq-sort-by--shuffle (seq)
(faster-seq-sort-by (lambda (_) (random)) #'<= seq))
(dolist (sorter '(key-quiz--shuffle-list
key-quiz--shuffle-list-nreverse
elfeed--shuffle
seq-sort-by--shuffle
faster-seq-sort-by--shuffle
))
(message "\n*** %s ***" sorter)
(dolist (list-type '(list vector))
(let ((big-list (seq-into (seq-take obarray 5000) list-type))
(reps 100)
;;(gc-cons-threshold (* 128 1024 1024))
)
(message "-- %s:" list-type)
(garbage-collect)
(benchmark reps `(funcall ',sorter big-list))
)))
*** key-quiz--shuffle-list ***
-- list:
Elapsed time: 5.716712s
-- vector:
Elapsed time: 0.474314s
*** key-quiz--shuffle-list-nreverse ***
-- list:
Elapsed time: 5.208816s
-- vector:
Elapsed time: 0.462552s
*** elfeed--shuffle ***
-- list:
Elapsed time: 9.168661s
-- vector:
Elapsed time: 0.434240s
*** seq-sort-by--shuffle ***
-- list:
Elapsed time: 1.300859s
-- vector:
Elapsed time: 1.292157s
*** faster-seq-sort-by--shuffle ***
-- list:
Elapsed time: 1.323064s (0.128464s in 1 GCs)
-- vector:
Elapsed time: 1.275462s (0.127415s in 1 GCs)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.