[PD] To divide a number in random parts
matju at artengine.ca
Sat Mar 5 04:29:04 CET 2011
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
> 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
More information about the Pd-list