GNU bug report logs - #50878
[PATCH] union: Resolve collisions by stable-sort'ing them.

Previous Next

Full log

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

From: Maxime Devos <maximedevos <at> telenet.be>
To: Attila Lendvai <attila <at> lendvai.name>
Cc: Liliana Marie Prikler <liliana.prikler <at> gmail.com>, 50878 <at> debbugs.gnu.org
Subject: Re: [bug#50878] [PATCH] union: Resolve collisions by
 stable-sort'ing them.
Date: Thu, 30 Sep 2021 17:18:01 +0200

[Message part 1 (text/plain, inline)]

Attila Lendvai schreef op do 30-09-2021 om 14:12 [+0000]:
> > > the hash also needs to be dropped from the path for sorting to be
> > > useful, but the return value must be the full path, hence the
> > > complexity with sorting the indices, pointing both to the full paths
> > > and the cut parts.
> > 
> > You can replace the 'less' argument of 'stable-sort'.
> > Example sorting by the second character of a string:
> > 
> > (sort '("za" "yb" "xc") (lambda (x y)
> > (char>? (string-ref x 1)
> >                                   (string-ref y 1)))))
> 
> i don't know about the expected size of the collision list here, but
> that would cons much more, because that would cons up two substrings
> at each comparison, i.e. O(n^2) vs O(n) at least in GC load, probably
> in time also.

I don't see any consing here, or any increase in complexity?

> i think it's not worth it, but let me know, and then i can simplify
> the code somewhat at the cost of more consing.
> 
> sorting lists is probably also much slower than sorting vectors, but
> there may be some tricks i don't know about.

I was suggesting replacing the 'less' procedure with a procedure
like (lambda (x y) (char>? (string-ref x 1) (string-ref y 1)))
instead of doing the sorting in two steps.

I wasn't suggesting using lists.  The '("za" "yb" "xc") was only
for demonstration, a vector should work as well.

Greetings,
Maxime.

[signature.asc (application/pgp-signature, inline)]

Previous Next

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