append has bad complexity
append function seems to have quite bad complexity.
N := 25000; L := ; t0 := CpuTime(); for i := 1 to N do append(ref L, i); endfor; println "Time to make list: ", TimeFrom(t0);
The above code takes about 1.2s on my computer; with
N doubled, it takes about 5.3s; and with
N multiplied by 4 it takes over 40s.
What is going on???
#1 Updated by John Abbott about 2 years ago
The C++ STL offers an operation (
pushback) much like
append which guarantees linear complexity for a loop like the one I tried in CoCoA.
A naive implementation would have quadratic complexity: each call to
append makes a copy of the whole list.
How can CoCoA-5 have worse than quadratic complexity???
#2 Updated by John Abbott about 2 years ago
Just out of curiosity I ran the example with
N=20000; the time taken was about 210s... so still worse than quadratic behaviour, but not an increase by a factor of almost 8 as observed when increasing
N from 50000 to 100000.
Mysterious! Time to do some (painful) profiling... :-/