Various methods of randomly shuffling a list or vector of elements in emacs lisp, with benchmarks

elisp-shuffles.el

(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))

(defun faster-seq-sort-by--shuffle (seq)
  (faster-seq-sort-by (lambda (_) (random)) #'<= seq))

(defun my-seq-shuffle (sequence)
  "Unrolled version of seq-sort-by"
  (seq-map 'cdr
           (sort (seq-map (lambda (x) (cons (random) x)) sequence)
                 (lambda (a b)
                   (<= (car a) (car b))))))

(defun hugot-shuffle (list)
  "Method from hugot, tweaked to avoid converting vecs back into lists when not needed"
  (let* ((vec (seq-into list 'vector))
         (length (length vec))
         (n 0))
    (while (< n length)
      (let ((i (+ n (random (- length n))))
            (tmp (aref vec n)))
        (setf (aref vec n) (aref vec i)
              (aref vec i) tmp))
      (cl-incf n))
    (if (vectorp list)
        vec
      (seq-into vec 'list))))

(defun elfeed-on-vec-shuffle (list)
  "Elfeed's method, but converting to vec"
  (let* ((seq (seq-into list 'vector)))
    (let ((n (length seq)))
      (prog1 (if (vectorp list) seq (seq-into seq 'list))
        (dotimes (i n)
          (cl-rotatef (elt seq i) (elt seq (+ i (random (- n i))))))))))


(dolist (sorter '(key-quiz--shuffle-list
                  key-quiz--shuffle-list-nreverse
                  elfeed--shuffle
                  seq-sort-by--shuffle
                  faster-seq-sort-by--shuffle
                  my-seq-shuffle
                  hugot-shuffle
                  elfeed-on-vec-shuffle
                  ))
  (message "\n*** %s ***" sorter)
  (dolist (list-type '(list vector))
    (let ((big-list (seq-into (number-sequence 1 5000) list-type))
          (reps 100)
          ;;(gc-cons-threshold  (* 128 1024 1024))
          )
      (message "-- %s:" list-type)
      (garbage-collect)
      (benchmark reps `(funcall ',sorter big-list))
      )))

results.txt

*** key-quiz--shuffle-list ***
-- list:
Elapsed time: 6.650204s
-- vector:
Elapsed time: 0.240027s

*** key-quiz--shuffle-list-nreverse ***
-- list:
Elapsed time: 6.742569s
-- vector:
Elapsed time: 0.244173s

*** elfeed--shuffle ***
-- list:
Elapsed time: 11.157770s
-- vector:
Elapsed time: 0.236123s

*** seq-sort-by--shuffle ***
-- list:
Elapsed time: 0.644674s
-- vector:
Elapsed time: 0.685449s

*** faster-seq-sort-by--shuffle ***
-- list:
Elapsed time: 0.573194s
-- vector:
Elapsed time: 0.572976s

*** my-seq-shuffle ***
-- list:
Elapsed time: 0.470165s
-- vector:
Elapsed time: 0.465306s

*** hugot-shuffle ***
-- list:
Elapsed time: 0.209031s
-- vector:
Elapsed time: 0.197855s

*** elfeed-on-vec-shuffle ***
-- list:
Elapsed time: 0.252475s
-- vector:
Elapsed time: 0.239680s

Hey! I needed a shuffle function too and came up with this one. It cheats because it converts whatever sequence it got into a vector and then converts that to a list in the end, but it's quite fast :)

(defun shuffle (list)
  (let* ((vec (seq-into list 'vector))
         (length (length vec))
         (n 0))
    (while (< n length)
      (let ((i (+ n (random (- length n))))
            (tmp (aref vec n)))
        (setf (aref vec n) (aref vec i)
              (aref vec i) tmp))
      (cl-incf n))
    (seq-into vec 'list)))

*** key-quiz--shuffle-list ***
-- list:
Elapsed time: 5.914583s
-- vector:
Elapsed time: 0.236862s

*** key-quiz--shuffle-list-nreverse ***
-- list:
Elapsed time: 6.054802s
-- vector:
Elapsed time: 0.232880s

*** elfeed--shuffle ***
-- list:
Elapsed time: 10.985217s
-- vector:
Elapsed time: 0.245041s

*** seq-sort-by--shuffle ***
-- list:
Elapsed time: 0.717010s
-- vector:
Elapsed time: 0.734833s

*** faster-seq-sort-by--shuffle ***
-- list:
Elapsed time: 0.590572s
-- vector:
Elapsed time: 0.592119s

*** shuffle ***
-- list:
Elapsed time: 0.206029s
-- vector:
Elapsed time: 0.204306s
~

@hugot Thanks. How many elements were in those sequences you benchmarked the sorting of?

@alphapapa Same as in the original gist, 5000. Although I now have my questions about the reliability of that. I didn't notice it initially, but using seq-take on the obarray seems like an overly creative way to create a big list when we have number-sequence. Not to mention, what if there's less than 5000 symbols in the obarray? 🙃 Would probably best to change that bit of code if we were to use this as a reliable benchmark.

Yes, I'd recommend making a specific sequence, and testing with larger sizes, too.

@hugot your method is faster still if you avoid converting vecs back into lists when the input was a list.

I updated the gist with these variations, and a better source of initial input.

@purcell great, thanks!