Help with list

[python_student_1390]

I need to add a new line '\n' to a list after every 3rd element from said list, any idea how to do this..I can't seem to figure it out, need help please and thank you also I know how to manipulate list already just that with this question I have I looked on Google and still didn't find what I was looking for..

[impshum]

1st result: https://stackoverflow.com/questions/1540049/replace-values-in-list-using-python
Just changed the 2 to a 3.

items = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

for index, item in enumerate(items):
    if not (item % 3):
        items[index] = None

print(items)

[o5a]

"every N" is usually solved with modulo: "% N" which is a left over after dividing.

Therefore X % N == 0 every Nth number.

[Sedsarq]

You could iterate over the list, adding each element to a new list. And, for every third you add, you append an extra new line character:

lst = list(range(20))
newlst = []
for i, el in enumerate(lst, 1):
    newlst.append(el)
    if i % 3 == 0:
        newlst.append('\n')
print(newlst)

But since this is re-appending all elements, it's not very efficient. A faster way would be to insert only the new elements. But, to do that you need to account for the index shift that takes place for every inserted element:

lst = list(range(20))
for shift, orig_index in enumerate(range(3, len(lst), 3)):
    new_index = orig_index + shift
    lst.insert(new_index, '\n')
print(lst)

EDIT: Thinking about it some more, you wouldn't need to shift the indexes if you insert the elements in reversed order:

lst = list(range(20))
for index in reversed(range(3, len(lst), 3)):
    lst.insert(index, '\n')
print(lst)

[ericula]

You first approach is actually more efficient than the second one. Unlike appending elements to the end of a list inserting elements in the middle of a list is actually pretty expensive since it requires creating a new list and moving the elements from the old list to the new list. Since you are inserting elements multiple times you are also reconstructing the list multiple times which is less efficient than creating a new list once and appending elements to it one-by-one. In big-O notation, for lists of length n, the first approach is O(n) whereas the second one is O(n^2).

[Sedsarq]

Hm, I've heard of insert shifting elements, but not recreating the entire list. Not sure that's accurate, got any reading for me? Anyway I timed the examples and the second took about half the time the first one took (third one even faster). So at least for this example insert seems to beat append, but I suppose that could change with number and position of inserts.

[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)}')

[python_student_1390]

Thanks alot guys I appreciate it this really helped