* Re: [elpa] externals/emms e9fa4c095d: * emms.el: reverse the order players are collected
[not found] ` <20220906220156.5255DC0088A@vcs2.savannah.gnu.org>
@ 2022-09-07 1:50 ` Stefan Monnier
2022-09-07 20:16 ` Yoni Rabkin
0 siblings, 1 reply; 4+ messages in thread
From: Stefan Monnier @ 2022-09-07 1:50 UTC (permalink / raw)
To: Yoni Rabkin; +Cc: emacs-devel
> --- a/emms.el
> +++ b/emms.el
> @@ -1511,7 +1511,7 @@ If the track can be played by more than one player, call
> (mapc
> #'(lambda (player)
> (when (funcall (emms-player-get player 'playablep) track)
> - (push player players)))
> + (setq players (append players `(,player)))))
> emms-player-list)
> (if (< 1 (length players))
> (emms-players-preference track players)
This changes the code's complexity from O(N) to O(N²) in the number of
players. Maybe it's not a very big deal, but the standard way to avoid
this is to use `push` inside the loop followed by `nreverse` at the of
the loop.
Stefan
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [elpa] externals/emms e9fa4c095d: * emms.el: reverse the order players are collected
2022-09-07 1:50 ` [elpa] externals/emms e9fa4c095d: * emms.el: reverse the order players are collected Stefan Monnier
@ 2022-09-07 20:16 ` Yoni Rabkin
2022-09-07 20:26 ` Stefan Monnier
0 siblings, 1 reply; 4+ messages in thread
From: Yoni Rabkin @ 2022-09-07 20:16 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> --- a/emms.el
>> +++ b/emms.el
>> @@ -1511,7 +1511,7 @@ If the track can be played by more than one player, call
>> (mapc
>> #'(lambda (player)
>> (when (funcall (emms-player-get player 'playablep) track)
>> - (push player players)))
>> + (setq players (append players `(,player)))))
>> emms-player-list)
>> (if (< 1 (length players))
>> (emms-players-preference track players)
>
> This changes the code's complexity from O(N) to O(N²) in the number of
> players.
Is this because append has to traverse the list all of the way to the
last cdr every time?
> Maybe it's not a very big deal,
Indeed. Since the list of players is a constant (about 7), this ends up
being constant-time. I tend to ignore how short lists are processed, and
I indeed didn't think about big-O of anything when I made this change.
> but the standard way to avoid this is to use `push` inside the loop
> followed by `nreverse` at the of the loop.
Doing it the Right Way (TM) feels better regardless of if it makes any
actual sense(*). Programming is about elegance as much as anything
else. I'll change it to use push and nreverse.
* We've probably spent more time in this conversation than the sum total
processing time of all of the machines which will ever run this code.
--
"Cut your own wood and it will warm you twice"
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [elpa] externals/emms e9fa4c095d: * emms.el: reverse the order players are collected
2022-09-07 20:16 ` Yoni Rabkin
@ 2022-09-07 20:26 ` Stefan Monnier
2022-09-08 4:26 ` tomas
0 siblings, 1 reply; 4+ messages in thread
From: Stefan Monnier @ 2022-09-07 20:26 UTC (permalink / raw)
To: Yoni Rabkin; +Cc: emacs-devel
>> This changes the code's complexity from O(N) to O(N²) in the number of
>> players.
>
> Is this because append has to traverse the list all of the way to the
> last cdr every time?
Yup.
> * We've probably spent more time in this conversation than the sum total
> processing time of all of the machines which will ever run this code.
Indeed :-)
Stefan
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2022-09-08 4:26 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
[not found] <166250171605.12534.6807904164286037648@vcs2.savannah.gnu.org>
[not found] ` <20220906220156.5255DC0088A@vcs2.savannah.gnu.org>
2022-09-07 1:50 ` [elpa] externals/emms e9fa4c095d: * emms.el: reverse the order players are collected Stefan Monnier
2022-09-07 20:16 ` Yoni Rabkin
2022-09-07 20:26 ` Stefan Monnier
2022-09-08 4:26 ` tomas
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.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.