----- Original Message -----
From: Mathieu Bouchard matju@artengine.ca To: Frank Barknecht fbar@footils.org Cc: pd-list@iem.at 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 _______________________________________________ Pd-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list