From: Maxime Devos <maximedevos@telenet.be>
To: Attila Lendvai <attila@lendvai.name>
Cc: Liliana Marie Prikler <liliana.prikler@gmail.com>, 50878@debbugs.gnu.org
Subject: [bug#50878] [PATCH] union: Resolve collisions by stable-sort'ing them.
Date: Thu, 30 Sep 2021 17:18:01 +0200 [thread overview]
Message-ID: <57b644a0b8accceed5d390cd82b2f69d427c464d.camel@telenet.be> (raw)
In-Reply-To: <RG7heiLAiSf93kpl3Y4Iml-x5Ons2p1WfXXD5ZkTkaD_wpkBOmzNnS21fmUIT_MBCZxRilDPOUEE58qHChZKE_1_HmtMZFKHKzxN7-CrJmw=@lendvai.name>
[-- Attachment #1: Type: text/plain, Size: 1431 bytes --]
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.
[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 260 bytes --]
next prev parent reply other threads:[~2021-09-30 15:33 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-09-28 21:40 [bug#50878] [PATCH] union: Resolve collisions by stable-sort'ing them Attila Lendvai
2021-09-29 13:48 ` Maxime Devos
2021-09-29 16:03 ` Attila Lendvai
2021-09-29 21:00 ` Maxime Devos
2021-09-29 17:42 ` Liliana Marie Prikler
2021-09-30 8:10 ` Attila Lendvai
2021-09-30 8:42 ` Maxime Devos
2021-09-30 14:00 ` Ludovic Courtès
2021-09-30 14:12 ` Attila Lendvai
2021-09-30 15:18 ` Maxime Devos [this message]
2021-09-30 18:13 ` Liliana Marie Prikler
2021-09-30 18:52 ` Liliana Marie Prikler
2021-10-03 12:43 ` [bug#50878] [PATCH 1/4] guix: build: Promote local define-inline to a define-constant util Attila Lendvai
2021-10-03 12:43 ` [bug#50878] [PATCH 2/4] guix: build: Avoid using magic literals in the code for hash length Attila Lendvai
2021-10-03 12:43 ` [bug#50878] [PATCH 3/4] guix: build: Factor out and export default-collision-resolver Attila Lendvai
2021-10-03 12:43 ` [bug#50878] [PATCH 4/4] WIP guix: build: Add resolve-collision/alphanumeric-last for union Attila Lendvai
2021-10-03 12:59 ` [bug#50878] (No Subject) Attila Lendvai
2022-09-02 16:04 ` Liliana Marie Prikler
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=57b644a0b8accceed5d390cd82b2f69d427c464d.camel@telenet.be \
--to=maximedevos@telenet.be \
--cc=50878@debbugs.gnu.org \
--cc=attila@lendvai.name \
--cc=liliana.prikler@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/guix.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.