[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
01/02: Add a faster delete-duplicates function
From: |
Christopher Baines |
Subject: |
01/02: Add a faster delete-duplicates function |
Date: |
Tue, 1 Mar 2022 16:35:31 -0500 (EST) |
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)))))))))