Project

General

Profile

Slug #862

append has bad complexity

Added by John Abbott about 8 years ago. Updated about 8 years ago.

Status:
New
Priority:
Normal
Assignee:
-
Category:
enhancing/improving
Target version:
CoCoA-5.?.?
Start date:
05 Apr 2016
Due date:
% Done:

0%

Estimated time:
Spent time:
0.60 h

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

Related to CoCoA-5 - Slug #1228: SLUG: filling an arrayIn Progress2018-09-30

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 almost 5 years ago

  • Related to Slug #1228: SLUG: filling an array added

Also available in: Atom PDF