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

[Maxime Devos]

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
Description: This is a digitally signed message part