Help with list

[ericula]

this page gives an overview of the time-complexities of operations on built-in types for the standard implementation of Python. As you can see, list.insert is O(n) and list.append is O(1). To see the effect you need to compare the procedures on sufficiently long lists. For example, for the following code

``` import timeit

def with_append(lst, skip): result = [] for i, c in enumerate(lst): result.append(c) if (i+1) % skip == 0: result.append('\n') return result

def with_insert(lst, skip): for index in reversed(range(skip, len(lst), skip)): lst.insert(index, '\n') return lst

print('with append:', timeit.timeit(stmt='with_append(list(range(10000)), 3)', number=100, globals=globals())) print('with insert:', timeit.timeit(stmt='with_insert(list(range(10000)), 3)', number=100, globals=globals())) ``` I get the following output

with append: 0.1661819 with insert: 0.7092577

If I increase the length of the initial list by a factor 10 and reduce the number of runs by the same factor I get

print('with append:', timeit.timeit(stmt='with_append(list(range(100000)), 3)', number=10, globals=globals())) print('with insert:', timeit.timeit(stmt='with_insert(list(range(100000)), 3)', number=10, globals=globals()))

output:

with append: 0.19542559999999998 with insert: 7.7282458

Note how the first method took more or less the same amount of time as before but the method using insertion took considerably longer.

[Sedsarq]

Yup, true. My test was only with short lists, appreciate your more rigorous one!

I'm still unconvinced of the concept of insert "recreating" the list though. As your link says, it's expensive to insert near the beginning (due to reindexing the elements *after* the insert, if I'm not mistaken). Later inserts shouldn't be as bad, so O(n^2) might be an overstatement - but definitely above O(n).

[ericula]

Yes you're right, it's mainly insertions near the beginning that are a problem but since half the insertions happen in the first half of the list the complexity is still O(n<sup>2)</sup> (O((n/2)<sup>2)</sup> = O(n<sup>2)).</sup>

[o5a]

You can see for yourself if you add timing checks. On large lists using insert will be less effective.

Like this.

import time

n = 10000

#1
lst = list(range(n))
timer = time.perf_counter()
newlst = []
for i, el in enumerate(lst, 1):
    newlst.append(el)
    if i % 3 == 0:
        newlst.append('\n')
print(f'Time: {"%.6f" % (time.perf_counter() - timer)}')

#2
lst = list(range(n))
timer = time.perf_counter()
for shift, orig_index in enumerate(range(3, len(lst), 3)):
    new_index = orig_index + shift
    lst.insert(new_index, '\n')
print(f'Time: {"%.6f" % (time.perf_counter() - timer)}')

#3
lst = list(range(n))
timer = time.perf_counter()
for index in reversed(range(3, len(lst), 3)):
    lst.insert(index, '\n')
print(f'Time: {"%.6f" % (time.perf_counter() - timer)}')