GNU bug report logs - #68271
[PATCH 0/3] Make some deduplicating speedups.

Previous Next

Full log

Message #17 received at 68271 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: Christopher Baines <mail <at> cbaines.net>
Cc: Josselin Poiret <dev <at> jpoiret.xyz>,
 Simon Tournier <zimon.toutoune <at> gmail.com>, Mathieu Othacehe <othacehe <at> gnu.org>,
 Tobias Geerinckx-Rice <me <at> tobias.gr>, 68271 <at> debbugs.gnu.org,
 Ricardo Wurmus <rekado <at> elephly.net>, Christopher Baines <guix <at> cbaines.net>
Subject: Re: [bug#68271] [PATCH 1/3] guix: utils: Add delete-duplicates/sort.
Date: Fri, 12 Jan 2024 14:53:43 +0100

Christopher Baines <mail <at> cbaines.net> skribis:

> Similar to delete-duplicates, but sorts the list first and then compares the
> pairs in the list. This is faster than delete-duplicates for larger lists.

We’re dealing with small lists here though (derivation inputs).  Did you
try to time the benefit?

There’s a complexity/benefit tradeoff and I wonder if it cuts it.

> +(define* (delete-duplicates/sort unsorted-lst less #:optional (equal? eq?))
> +  (if (null? unsorted-lst)
> +      unsorted-lst

This ‘if’ is unnecessary.

> +      (let ((sorted-lst (sort unsorted-lst
> +                              ;; Sort in the reverse order
> +                              (lambda (a b) (eq? #f (less a b))))))

Just: (negate 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)))

Please follow the convention of using ‘match’ rather than car caddr
caddddar (info "(guix) Data Types and Pattern Matching"):

  (match lst
    (()
     result)
    ((head . tail)
     …))

Ludo’.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.