From c0d761bf7f441f8ab9792351a493dc6bd5525dc1 Mon Sep 17 00:00:00 2001 From: Lars Ingebrigtsen Date: Fri, 12 Aug 2022 15:15:11 +0200 Subject: Further seq-uniq speed-ups for lists * lisp/emacs-lisp/seq.el (seq-uniq): Speed up more for long lists (bug#57079). --- lisp/emacs-lisp/seq.el | 20 +++++++++++++++----- 1 file changed, 15 insertions(+), 5 deletions(-) (limited to 'lisp/emacs-lisp/seq.el') diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el index 6ddd8de6e8d..b6f0f66e5b1 100644 --- a/lisp/emacs-lisp/seq.el +++ b/lisp/emacs-lisp/seq.el @@ -458,11 +458,21 @@ TESTFN is used to compare elements, or `equal' if TESTFN is nil." (cl-defmethod seq-uniq ((sequence list) &optional testfn) (let ((result nil)) (if (not testfn) - ;; Fast path. - (while sequence - (unless (member (car sequence) result) - (push (car sequence) result)) - (pop sequence)) + ;; Fast path. If the list is long, use a hash table to speed + ;; things up even more. + (let ((l (length sequence))) + (if (> l 100) + (let ((hash (make-hash-table :test #'equal :size l))) + (while sequence + (unless (gethash (car sequence) hash) + (setf (gethash (car sequence) hash) t) + (push (car sequence) result)) + (setq sequence (cdr sequence)))) + ;; Short list. + (while sequence + (unless (member (car sequence) result) + (push (car sequence) result)) + (pop sequence)))) ;; Slower path. (while sequence (unless (seq-find (lambda (elem) -- cgit v1.2.1