replace every item in a list with their previous item?

Question

For example,

ls = [8, 5, 2, 17]

I want to replace every item the with their previous item, and add a new value to the last item.

The expected result is:

ls = [5, 2, 17, new_value]

What is the best way to reach this in the perspective of time complexity?

My implementation detail:

I'm implementing AlphaZero algorithm on a board game, called "Abalone", and I need to handle the input data.

Example for the input data is,

ls_3d = [
[board_before_2_last_board],
[board_before_last_board],
[last_board],
[current_board]
]
*each board is a 2d array

And I have to keep handling this 3d list every moves. I think I'll do this many times in order to training the model, so I want it as fast as possible.

After seeing the answer, I think the method is same in 1d list. Like this:

ls = ls[1:,:,:]+[new_board]

Is it correct?

What's your current implementation and what's the problem with it? — jonrsharpe, Jul 05 '20 at 22:35
Wait a minute, and I'll update detail implementation for you :) — HLM, Jul 05 '20 at 22:38
Does this answer your question? [Understanding slice notation](https://stackoverflow.com/questions/509211/understanding-slice-notation) — Nicolas Gervais, Dec 03 '20 at 14:09

score 5 · Answer 1 · answered Jul 05 '20 at 22:34

5

Easy:

ls = [8, 5, 2, 17]
ls = ls[1:]+[new_value]

answered Jul 05 '20 at 22:34

Red

26,798
7
36
58

1

Sorry, I'm a beginner for python, so I ask a dumb question like this. Your answer looks good :) – HLM Jul 05 '20 at 22:36

alani · Accepted Answer · 2020-07-05T23:30:13.650

3

If you want to do an in-place modification of the list (which could be important if you also have other references to it), then you can do:

ls = [8, 5, 2, 17]
ls.pop(0)  # remove first element
ls.append(new_value)  # put new value on the end

The append is quick, but the pop from the start of the list is O(n) time complexity.

Nonetheless, it is quicker than reassigning the list to a new object (i.e. anything that starts ls = ...).

In timing tests with a list of size 1000, and 100000 iterations (here I am using the loop variable i as the new element to append):

import time

ls = list(range(1000))

t0 = time.time()

for i in range(100000):
    ls.pop(0)
    ls.append(i)
    
t1 = time.time()
print(t1 - t0)

took about 0.031 seconds on my machine.

Some alternatives, involving reassigning the list:

for i in range(100000):
    ls = ls[1:]
    ls.append(i)

took 0.221 seconds,

and the slowest:

for i in range(100000):
    ls = ls[1:] + [i]

took 0.433 seconds.

In the last of these, in every iteration you construct a new temporary list of size n-1, and then you construct a list of size n, which is why it takes nearly twice as long as the previous one (construct a list of size n-1 and then append an element).

edited Jul 05 '20 at 23:30

answered Jul 05 '20 at 23:19

alani

12,573
2
13
23

I'll try pop and append. Looks very helpful! – HLM Jul 05 '20 at 23:29
@HLM It is still not great to have to pop from the start of a list. The really much quicker method would be not to do this at all, but instead just reassign one of the elements (e.g. `ls[i % n] = new_value` where `i` is the current iteration number and `n` is the length of the list, and `%` means modulo), then when you want to index it you will have to add an offset to the index to allow for this - does that make sense? – alani Jul 05 '20 at 23:41
@HLM Essentially if you have just assigned at location `index` (=`i%n`) instead of at the end of the list, and then you would want to look up the `j`th element, then instead you look up element `(index + j) % n`, so it is slightly more complicated to get the item you want, but the big gain is that you never have to shift all the values along (which is what the pop will have to do), you just keep writing to a different position each time (and when you reach the end you go back to position 0 and loop round again). – alani Jul 05 '20 at 23:52

replace every item in a list with their previous item?

2 Answers2