[PD] To divide a number in random parts

[Mathieu Bouchard]

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