From: Eli Zaretskii <eliz@gnu.org>
To: Dmitry Gutov <dmitry@gutov.dev>
Cc: yuri.v.khan@gmail.com, michael_heerdegen@web.de,
jwiegley@gmail.com, emacs-devel@gnu.org
Subject: Re: master 4b79c80c999 1/2: New function 'sort-on'
Date: Mon, 05 Feb 2024 16:31:02 +0200 [thread overview]
Message-ID: <86le7z0yqh.fsf@gnu.org> (raw)
In-Reply-To: <3ff9d4cf-7b4f-4924-8663-3f43625760bf@gutov.dev> (message from Dmitry Gutov on Mon, 5 Feb 2024 15:25:59 +0200)
> Date: Mon, 5 Feb 2024 15:25:59 +0200
> Cc: Eli Zaretskii <eliz@gnu.org>, Michael Heerdegen
> <michael_heerdegen@web.de>, John Wiegley <jwiegley@gmail.com>,
> emacs-devel@gnu.org
> From: Dmitry Gutov <dmitry@gutov.dev>
>
> On 05/02/2024 07:30, Yuri Khan wrote:
> > On Mon, 5 Feb 2024 at 07:49, Dmitry Gutov <dmitry@gutov.dev> wrote:
> >
> >> The result would make it destructive and consequently faster (not
> >> entirely non-consing, but close to it--while the current sort-on creates
> >> two extra lists of length N), which should fit the original goal: a
> >> faster sorting routine then uses ACCESSOR.
> >
> > Schwartzian transform transforms a sort algorithm that is O(n log n)
> > accessor calls + O(n log n) comparison calls into one that is O(n)
> > accessor calls + O(n log n) comparison calls. Depending on the
> > accessor expensiveness, that may or may not balance out the consing
> > and eventual GC.
>
> Users who don't want to use the transform could inline the accessor
> calls into the comparison function instead (as many have done in the
> past). So if we document this properly, it should be fine.
It's already documented (in the ELisp manual).
next prev parent reply other threads:[~2024-02-05 14:31 UTC|newest]
Thread overview: 38+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <170688047526.14693.2994051491358257471@vcs2.savannah.gnu.org>
[not found] ` <20240202132756.4272CC0EFE7@vcs2.savannah.gnu.org>
2024-02-02 15:00 ` master 4b79c80c999 1/2: New function 'sort-on' Daniel Mendler via Emacs development discussions.
2024-02-02 15:04 ` Eli Zaretskii
2024-02-02 15:26 ` Daniel Mendler via Emacs development discussions.
2024-02-02 15:47 ` Eli Zaretskii
2024-02-02 16:05 ` Daniel Mendler via Emacs development discussions.
2024-02-05 12:14 ` Michael Heerdegen
2024-02-02 15:55 ` Dmitry Gutov
2024-02-02 15:30 ` Michael Heerdegen via Emacs development discussions.
2024-02-02 15:35 ` Daniel Mendler via Emacs development discussions.
2024-02-02 16:08 ` Michael Heerdegen via Emacs development discussions.
2024-02-02 16:23 ` Daniel Mendler via Emacs development discussions.
2024-02-02 16:43 ` Michael Heerdegen via Emacs development discussions.
2024-02-02 15:50 ` Eli Zaretskii
2024-02-02 16:06 ` Eshel Yaron
2024-02-02 16:34 ` Eli Zaretskii
2024-02-02 16:46 ` Michael Heerdegen via Emacs development discussions.
2024-02-02 17:55 ` Emanuel Berg
2024-02-05 0:48 ` Dmitry Gutov
2024-02-05 5:30 ` Yuri Khan
2024-02-05 12:52 ` Eli Zaretskii
2024-02-05 13:25 ` Dmitry Gutov
2024-02-05 14:31 ` Eli Zaretskii [this message]
2024-02-05 14:47 ` Dmitry Gutov
2024-02-05 15:10 ` Eli Zaretskii
2024-02-05 15:29 ` Dmitry Gutov
2024-02-28 7:40 ` Michael Heerdegen
2024-03-01 23:37 ` Dmitry Gutov
2024-03-04 6:45 ` Michael Heerdegen
2024-03-04 16:43 ` Dmitry Gutov
2024-03-05 8:06 ` Michael Heerdegen
2024-03-05 10:21 ` Michael Heerdegen via Emacs development discussions.
2024-03-05 12:39 ` Eli Zaretskii
2024-03-06 3:20 ` Michael Heerdegen
2024-03-06 12:10 ` Eli Zaretskii
2024-03-06 18:34 ` Dmitry Gutov
2024-03-06 20:12 ` John Wiegley
2024-03-07 1:34 ` Dmitry Gutov
2024-03-05 12:44 ` Dmitry Gutov
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=86le7z0yqh.fsf@gnu.org \
--to=eliz@gnu.org \
--cc=dmitry@gutov.dev \
--cc=emacs-devel@gnu.org \
--cc=jwiegley@gmail.com \
--cc=michael_heerdegen@web.de \
--cc=yuri.v.khan@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 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).