Is there a way to remove elements from the start of a long list of numbers? Right now I am doing del arr[i:i+x] but it is slow since it has to move everything past that point to the left, which is time-consuming for large lists.
I looked into deques but not sure if those apply here. Could use some direction!
Yes deques do apply here, you should use them, it will be very fast if they are very near the front but slower if the start index is located towards the middle.
Indexed access is O(1) at both ends but slows to O(n) in the middle.
>>> from collections import deque
>>> def delete_slice(d, start, stop):
d.rotate(-start)
for i in range(stop-start): # use xrange on Python 2
d.popleft()
d.rotate(start)
>>> d = deque(range(15))
>>> delete_slice(d, 5, 10)
>>> d
deque([0, 1, 2, 3, 4, 10, 11, 12, 13, 14])
Note: Rotating past the middle, as previously stated, will be slow, if you want to support fast deletions from the right side you can extend the code like so:
def delete_slice(d, start, stop):
stop = min(stop, len(d)) # don't go past the end
start = min(start, stop) # don't go past stop
if start < len(d) // 2:
d.rotate(-start)
for i in range(stop-start): # use xrange on Python 2
d.popleft()
d.rotate(start)
else:
n = len(d) - stop
d.rotate(n)
for i in range(stop - start):
d.pop()
d.rotate(-n)
Of course there is some other error checking you will need to do but I'll leave that out of here for simplicity's sake. Unfortunately these methods are not already provided by deque itself, so you have to implement them like this.
To implement deque slicing, use a similar approach applying
rotate()to bring a target element to the left side of thedeque. Remove old entries withpopleft(), add new entries withextend(), and then reverse the rotation. With minor variations on that approach, it is easy to implement Forth style stack manipulations such as dup, drop, swap, over, pick, rot, and roll.