Skip to content

Instantly share code, notes, and snippets.

@alphapapa

alphapapa/elisp-shuffles.el

Forked from purcell/elisp-shuffles.el
Created September 15, 2024 08:19
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save alphapapa/bbd720e321e54f6f7bd75f44c46e06c3 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save alphapapa/bbd720e321e54f6f7bd75f44c46e06c3 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @purcell purcell revised this gist Jun 3, 2019. 2 changed files with 31 additions and 21 deletions.
    3 changes: 2 additions & 1 deletion elisp-shuffles.el
    View file
    Original file line number Diff line number Diff line change
    @@ -46,12 +46,13 @@ sorted. FUNCTION must be a function of one argument."
    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 - %s:" list-type sorter)
    (message "-- %s:" list-type)
    (garbage-collect)
    (benchmark reps `(funcall ',sorter big-list))
    )))
    49 changes: 29 additions & 20 deletions results.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -1,20 +1,29 @@
    *** list - key-quiz--shuffle-list:
    Elapsed time: 5.523651s
    *** vector - key-quiz--shuffle-list:
    Elapsed time: 0.470950s
    *** list - key-quiz--shuffle-list-nreverse:
    Elapsed time: 5.214715s
    *** vector - key-quiz--shuffle-list-nreverse:
    Elapsed time: 0.459148s
    *** list - elfeed--shuffle:
    Elapsed time: 9.111954s
    *** vector - elfeed--shuffle:
    Elapsed time: 0.422567s
    *** list - seq-sort-by--shuffle:
    Elapsed time: 1.301746s
    *** vector - seq-sort-by--shuffle:
    Elapsed time: 1.282321s
    *** list - faster-seq-sort-by--shuffle:
    Elapsed time: 1.245782s (0.116512s in 1 GCs)
    *** vector - faster-seq-sort-by--shuffle:
    Elapsed time: 1.239501s (0.116404s in 1 GCs)
    *** 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)
  2. @purcell purcell revised this gist Jun 3, 2019. 2 changed files with 31 additions and 19 deletions.
    20 changes: 11 additions & 9 deletions elisp-shuffles.el
    View file
    Original file line number Diff line number Diff line change
    @@ -22,12 +22,13 @@
    (let ((n (length seq)))
    (prog1 seq ; don't use dotimes result (bug#16206)
    (dotimes (i n)
    (cl-rotatef (elt seq i) (elt seq (+ i (cl-random (- n i)))))))))
    (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)
    @@ -45,11 +46,12 @@ sorted. FUNCTION must be a function of one argument."
    seq-sort-by--shuffle
    faster-seq-sort-by--shuffle
    ))
    (let ((big-list (copy-sequence obarray))
    (reps 100)
    ;;(gc-cons-threshold (* 128 1024 1024))
    )
    (message "%s:" sorter)
    (garbage-collect)
    (benchmark reps `(funcall ',sorter big-list))
    ))
    (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 - %s:" list-type sorter)
    (garbage-collect)
    (benchmark reps `(funcall ',sorter big-list))
    )))
    30 changes: 20 additions & 10 deletions results.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -1,10 +1,20 @@
    key-quiz--shuffle-list:
    Elapsed time: 4.336526s (0.511012s in 2 GCs)
    key-quiz--shuffle-list-nreverse:
    Elapsed time: 5.775736s (0.514238s in 1 GCs)
    elfeed--shuffle:
    Elapsed time: 6.998477s
    seq-sort-by--shuffle:
    Elapsed time: 13.718084s (0.579970s in 2 GCs)
    faster-seq-sort-by--shuffle:
    Elapsed time: 12.714004s (0.831056s in 3 GCs)
    *** list - key-quiz--shuffle-list:
    Elapsed time: 5.523651s
    *** vector - key-quiz--shuffle-list:
    Elapsed time: 0.470950s
    *** list - key-quiz--shuffle-list-nreverse:
    Elapsed time: 5.214715s
    *** vector - key-quiz--shuffle-list-nreverse:
    Elapsed time: 0.459148s
    *** list - elfeed--shuffle:
    Elapsed time: 9.111954s
    *** vector - elfeed--shuffle:
    Elapsed time: 0.422567s
    *** list - seq-sort-by--shuffle:
    Elapsed time: 1.301746s
    *** vector - seq-sort-by--shuffle:
    Elapsed time: 1.282321s
    *** list - faster-seq-sort-by--shuffle:
    Elapsed time: 1.245782s (0.116512s in 1 GCs)
    *** vector - faster-seq-sort-by--shuffle:
    Elapsed time: 1.239501s (0.116404s in 1 GCs)
  3. @purcell purcell created this gist Jun 3, 2019.
    55 changes: 55 additions & 0 deletions elisp-shuffles.el
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,55 @@

    (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 (cl-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."
    (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
    ))
    (let ((big-list (copy-sequence obarray))
    (reps 100)
    ;;(gc-cons-threshold (* 128 1024 1024))
    )
    (message "%s:" sorter)
    (garbage-collect)
    (benchmark reps `(funcall ',sorter big-list))
    ))
    10 changes: 10 additions & 0 deletions results.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,10 @@
    key-quiz--shuffle-list:
    Elapsed time: 4.336526s (0.511012s in 2 GCs)
    key-quiz--shuffle-list-nreverse:
    Elapsed time: 5.775736s (0.514238s in 1 GCs)
    elfeed--shuffle:
    Elapsed time: 6.998477s
    seq-sort-by--shuffle:
    Elapsed time: 13.718084s (0.579970s in 2 GCs)
    faster-seq-sort-by--shuffle:
    Elapsed time: 12.714004s (0.831056s in 3 GCs)