Re: [elpa] externals/emms e9fa4c095d: * emms.el: reverse the order players are collected

Re: [elpa] externals/emms e9fa4c095d: * emms.el: reverse the order players are collected

[Stefan Monnier]

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

Re: [elpa] externals/emms e9fa4c095d: * emms.el: reverse the order players are collected

[Yoni Rabkin]

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"

Re: [elpa] externals/emms e9fa4c095d: * emms.el: reverse the order players are collected

[Stefan Monnier]

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

Re: [elpa] externals/emms e9fa4c095d: * emms.el: reverse the order players are collected

[tomas]

[-- Attachment #1: Type: text/plain, Size: 388 bytes --]

On Wed, Sep 07, 2022 at 04:26:56PM -0400, Stefan Monnier wrote:

[...]

> > * 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 :-)

Wait until the code goes viral. Never underestimate Internet Scale (TM).

Cheers

[Yes, tongue-in-cheek: here it is ;-P ]

-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]