On Wed, 2007-04-18 at 01:23 -0400, sen1 at math.msu.edu wrote:
> Following a suggestion from RJF to use the builtin function 'map', I
> rewrote the program 'sublist.mac' which is attached. It has both
> Jaime's routine, called 'j_sublist' and two other routines, called
> 'opp_1' and 'same_1'.
You should not use the routine I wrote (j_sublist), but use Stavros'
version instead (signrun, reproduced at the end). Using your xrl(n)
random list generator, look at the running times and memory usage of the
two approaches:
n t(signrun) t(j_sublist) mem(signrun) mem(j_sublist)
----------------------------------------------------------------------
5000 0.02 s 2.83 s 79 KB 2.94 MB
10000 0.03 s 8.14 s 157 KB 5.87 MB
20000 0.05 s 27.67 s 313 KB 11.75 MB
30000 0.11 s 59.77 s 470 KB 17.64 MB
for n=100 000 signrun was still fast (0.36 s) while with j_sublist I
gave up after a few minutes. For the data on the table, signum scales as
n^0.899, and j_sublist as n^1.70
Regards,
Jaime
===================== signrun ========================================
signrun(l):=
if l=[] then [] else
block([acc:[],nextl:rest(l)],
while nextl#[] do
(if sign(first(l))=sign(first(nextl)) then
acc:cons(first(l),acc),
l: nextl, nextl:rest(l) ),
reverse(acc) )$