----- Original Message ----- > From: Mathieu Bouchard <[email protected]> > To: Frank Barknecht <[email protected]> > Cc: [email protected] > Sent: Friday, February 24, 2012 1:26 PM > Subject: Re: [PD] sigmund list sort > > Le 2012-02-24 à 09:02:00, Frank Barknecht a écrit : >> On Sat, Feb 18, 2012 at 01:14:22PM -0500, Mathieu Bouchard wrote: >>> the [list-sort] abstraction uses a high-constant O(n²) algorithm that >>> breaks once you try to sort more than 125 values. >> Actually [list-sort] since quite some time uses the "sort" method > borrowed from >> Pd's data-structures for sorting. > > I have Pd-extended 42.5 that contains Michał Seta's sort, which used to be > cubic (O(n³)) and with even lower sorting limits, until I made you replace > the > O(n²) [list-drip] that used O(n) stack, by one that runs in O(n) and uses > O(log > n) stack. > > I don't know any more recent version of list-abs. > >> The problem here is not so much the sorting algorithm, which is very fast > and can sort way more than 125 items. > > Indeed, it's a slow version of mergesort written using linkedlists in C, > which is still faster than nearly anything one could possibly come up with in > pure Pd. > >> However copying the list to a data structure and back - this currently > indeed has a problem with stack-overflows, as I'm now aware. Have to think > about a fix ...
Use an iterative loop instead of a recursive one and you will avoid the stack overflows. > > Make sure that your algos take less than O(n) stack space... If it's not a > 125 element limit, it's 500 or 1000, and it can't get higher without > recompiling Pd to be more indulgent. > > ______________________________________________________________________ > | Mathieu BOUCHARD ----- téléphone : +1.514.383.3801 ----- Montréal, QC > _______________________________________________ > [email protected] mailing list > UNSUBSCRIBE and account-management -> > http://lists.puredata.info/listinfo/pd-list > _______________________________________________ [email protected] mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
