[elpa] externals/dash 11907f4 145/316: Speed up `-uniq` with hash-table. (#305)

[ELPA Syncer]

branch: externals/dash
commit 11907f4592ff1813536366d54245d3ecf6b99198
Merge: 77f3bf4 a5706bb
Author: Matus Goljer <goljer@logio.cz>
Commit: GitHub <noreply@github.com>

    Speed up `-uniq` with hash-table. (#305)
    
    Speed up `-uniq` with hash-table.
---
 dash.el         | 19 ++++++++++++++++---
 dev/examples.el | 14 +++++++++++++-
 2 files changed, 29 insertions(+), 4 deletions(-)

diff --git a/dash.el b/dash.el
index 587c074..f48c517 100644
--- a/dash.el
+++ b/dash.el
@@ -2274,9 +2274,22 @@ The test for equality is done with `equal',
 or with `-compare-fn' if that's non-nil.
 
 Alias: `-uniq'"
-  (let (result)
-    (--each list (unless (-contains? result it) (!cons it result)))
-    (nreverse result)))
+  ;; Implementation note: The speedup gained from hash table lookup
+  ;; starts to outweigh its overhead for lists of length greater than
+  ;; 32.  See discussion in PR #305.
+  (let* ((len (length list))
+         (lut (and (> len 32)
+                   ;; Check that `-compare-fn' is a valid hash-table
+                   ;; lookup function or `nil'.
+                   (memq -compare-fn '(nil equal eq eql))
+                   (make-hash-table :test (or -compare-fn #'equal)
+                                    :size len))))
+    (if lut
+        (--filter (unless (gethash it lut)
+                    (puthash it t lut))
+                  list)
+      (--each list (unless (-contains? lut it) (!cons it lut)))
+      (nreverse lut))))
 
 (defalias '-uniq '-distinct)
 
diff --git a/dev/examples.el b/dev/examples.el
index ff7a92d..7142370 100644
--- a/dev/examples.el
+++ b/dev/examples.el
@@ -692,7 +692,19 @@ new list."
 
   (defexamples -distinct
     (-distinct '()) => '()
-    (-distinct '(1 2 2 4)) => '(1 2 4)))
+    (-distinct '(1 2 2 4)) => '(1 2 4)
+    (-distinct '(t t t)) => '(t)
+    (-distinct '(nil nil nil)) => '(nil)
+    (let ((-compare-fn nil))
+      (-distinct '((1) (2) (1) (1)))) => '((1) (2))
+    (let ((-compare-fn #'eq))
+      (-distinct '((1) (2) (1) (1)))) => '((1) (2) (1) (1))
+    (let ((-compare-fn #'eq))
+      (-distinct '(:a :b :a :a))) => '(:a :b)
+    (let ((-compare-fn #'eql))
+      (-distinct '(2.1 3.1 2.1 2.1))) => '(2.1 3.1)
+    (let ((-compare-fn #'string=))
+      (-distinct '(dash "dash" "ash" "cash" "bash"))) => '(dash "ash" "cash" 
"bash")))
 
 (def-example-group "Other list operations"
   "Other list functions not fit to be classified elsewhere."