01/02: Add a faster delete-duplicates function

[Christopher Baines]

cbaines pushed a commit to branch master
in repository data-service.

commit 6cd3541d1abbc044a8537a326cd8aaea6bf8db7f
Author: Christopher Baines <mail@cbaines.net>
AuthorDate: Tue Mar 1 20:34:06 2022 +0000

    Add a faster delete-duplicates function
    
    Which is useful when deleting duplicates from large lists.
---
 guix-data-service/utils.scm | 24 +++++++++++++++++++++++-
 1 file changed, 23 insertions(+), 1 deletion(-)

diff --git a/guix-data-service/utils.scm b/guix-data-service/utils.scm
index ed13ef4..d59c18f 100644
--- a/guix-data-service/utils.scm
+++ b/guix-data-service/utils.scm
@@ -33,7 +33,9 @@
 
             chunk
             chunk!
-            chunk-for-each!))
+            chunk-for-each!
+
+            delete-duplicates/sort!))
 
 (define (call-with-time-logging action thunk)
   (simple-format #t "debug: Starting ~A\n" action)
@@ -202,3 +204,23 @@
       (do-one-iteration lsts)))
 
   #t)
+
+(define (delete-duplicates/sort! unsorted-lst less)
+  (if (null? unsorted-lst)
+      unsorted-lst
+      (let ((sorted-lst (sort! unsorted-lst less)))
+
+        (let loop ((lst (cdr sorted-lst))
+                   (last-element (car sorted-lst))
+                   (result (list (car sorted-lst))))
+          (if (null? lst)
+              result
+              (let ((current-element (car lst)))
+                (if (eq? current-element last-element)
+                    (loop (cdr lst)
+                          last-element
+                          result)
+                    (loop (cdr lst)
+                          current-element
+                          (cons current-element
+                                result)))))))))