unofficial mirror of emacs-devel@gnu.org 
 help / color / mirror / code / Atom feed
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).



  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).