On Fri, 4 Mar 2011, Matt Barber wrote:
Check out [list-sort] for short lists, [list-shellsort] for much longer ones (I don't remember at what point the shellsort starts beating the other one -- maybe if the list has 50 or more entries; but at any rate they do the same thing).
It vastly depends on the implementation, the interpreter it runs in, and the computer that the interpreter runs on.
However, from a short test of running time, it looks like [list-shellsort] runs much slower than what its theory calls the worst case. It probably takes O(n) time to perform stuff that usually takes O(1), probably because it avoids using [tabread] and such.
Actually, on my old computer, [list-shellsort] sorts an already-sorted list of size 1000 in 280 ms, and of size 4000 in 5530 ms. That's a 20-fold difference, whereas O(n^2) would be 16-fold, and shellsort's theoretical worst-case would be 8-fold, that is, O(n^1½).
[#sort] runs vastly faster than that. For the already-sorted list of size 1000, it does it in something like 0,22 ms, whereas for size 4000 it does it in about 0,90 ms. This means over a thousand times faster than [list-shellsort].
Also, if you're going to be doing something like this a ton in real time with long lists, it might be more productive to do all this manipulation with tables
Yes, you would be able to get speeds that are consistently about 10-20 times slower than [#sort] for any table size, which would be a vast improvement over [list-shellsort].
_______________________________________________________________________ | Mathieu Bouchard ---- tél: +1.514.383.3801 ---- Villeray, Montréal, QC
_______________________________________________ Pd-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
