Slug #862
append has bad complexity
Description
The 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???
Related issues
History
#1 Updated by John Abbott about 8 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 8 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... :-/
#3 Updated by John Abbott about 5 years ago
- Related to Slug #1228: SLUG: filling an array added