[PD] List delete carnage - 2 questions

Frank Barknecht fbar at footils.org
Tue Mar 29 15:52:31 CEST 2011

On Tue, Mar 29, 2011 at 09:27:03AM -0400, Mathieu Bouchard wrote:
> On Sun, 27 Mar 2011, Matt Barber wrote:
>> number to the end of the last list -- but we need to store the last
>> list as the thing to prepend, so it has to go back into the right
>> inlet, and the only good way of doing that is [t a] (you could just
>> use a [list] object, too, but [t a] seems more reliable and what
>> people use most).
> I don't see what you mean about reliability. I only know that going  
> through a [list append] is taking O(n) time, while going through a [t a]  
> takes O(1) time.
> Also, adding n elements to a list individually using [list]x[list] takes  
> O(n^2) time, with [list]x[t a] it takes O(n^2) time too, and using a  
> messagebox's add-method you can lower it to O(n). It's faster if you hide 
> the messagebox in a subpatch.
> From what I remember, the list-abs library does not use messageboxes, 
> only [list]x[t a], and thus several things are still O(n^2) even though 
> they could be O(n), and even though I upgraded [list-drip] from O(n^2) to 
> O(n) two years ago.

Your list-drip.pd was included in [list]-abs at about that time. Message boxes
are used in a handful of objects to speed things up, but probably some more
places would be useful. I don't remember ATM if message box storage works fine
with pointers as well, but there are objects where only floats would be allowed

 Frank Barknecht            Do You RjDj.me?          _ ______footils.org__

More information about the Pd-list mailing list