From: Lars Ingebrigtsen <larsi@gnus.org>
To: Andrew Cohen <acohen@ust.hk>
Cc: 54532@debbugs.gnu.org
Subject: bug#54532: [PATCH] sorting
Date: Wed, 23 Mar 2022 13:02:26 +0100 [thread overview]
Message-ID: <87ils4ancd.fsf@gnus.org> (raw)
In-Reply-To: <87k0clr12o.fsf@ust.hk> (Andrew Cohen's message of "Wed, 23 Mar 2022 07:59:11 +0800")
Andrew Cohen <acohen@ust.hk> writes:
> | | oldlist | oldvec | tim |
> | (make-random-list 10000) | 2790 | 2123 | 1557 |
> | (nreverse (make-sorted-list 10000)) | 1417 | 987 | 118 |
> | (make-sorted-list 10000) | 1310 | 899 | 116 |
> | (make-swapped-list 10000 3) | 1457 | 1019 | 122 |
> | (make-plus-list 10000) | 1309 | 899 | 119 |
> | (make-onepercent-list 10000) | 1764 | 1272 | 183 |
> | (make-constant-list 10000) | 1292 | 888 | 116 |
> | (make-evil-list 10000) | 1374 | 946 | 398 |
> | (make-block-list 10000 100) | 2235 | 1646 | 919 |
> | (make-block-list 10000 10) | 2598 | 1962 | 1451 |
Wow, great! A tenfold speed increase on (mostly-)sorted lists (which is a
common use case in my experience) is impressive.
Reading the code, I don't really have any comments (but then again, I
don't really understand the timsort algorithm anyway).
--
(domestic pets only, the antidote for overdose, milk.)
bloggy blog: http://lars.ingebrigtsen.no
next prev parent reply other threads:[~2022-03-23 12:02 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-03-22 23:59 bug#54532: [PATCH] sorting Andrew Cohen
2022-03-23 12:02 ` Lars Ingebrigtsen [this message]
2022-03-23 13:30 ` Eli Zaretskii
2022-03-23 23:43 ` Andrew Cohen
2022-03-23 13:46 ` Eli Zaretskii
2022-03-23 23:31 ` Andrew Cohen
2022-03-23 20:24 ` Mattias Engdegård
2022-03-24 6:42 ` Eli Zaretskii
2022-03-24 7:22 ` Andrew Cohen
2022-03-24 8:55 ` Eli Zaretskii
2022-03-24 9:17 ` Andrew Cohen
2022-03-24 9:55 ` Mattias Engdegård
2022-03-24 9:36 ` Mattias Engdegård
2022-03-31 12:03 ` Lars Ingebrigtsen
2022-03-31 13:58 ` Eli Zaretskii
2022-03-31 23:47 ` Andrew Cohen
2022-04-01 6:26 ` Eli Zaretskii
2022-06-07 7:06 ` Stefan Kangas
[not found] ` <877d5tgd11.fsf@ust.hk>
2022-06-07 9:07 ` Stefan Kangas
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
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87ils4ancd.fsf@gnus.org \
--to=larsi@gnus.org \
--cc=54532@debbugs.gnu.org \
--cc=acohen@ust.hk \
/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 public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).