I got a good question when using deque in the D question of "At Coder Beginner Contest 158" held the other day, so I would like to summarize how to use it in Python.
D - String Formation https://atcoder.jp/contests/abc158/tasks/abc158_d
A type of Python container data type. Data can be added at the cost of O (1) for both the beginning and the end. If it is a normal list, it can be implemented at the cost of O (n) when adding it to the beginning.
This is useful when you want to add data not only at the end but also at the beginning.
Use the "append" method as you would a List.
Use the "append left" method. List uses the "insert" method.
from collections import deque
d = deque('a')
d.append('b')
d.appendleft('c')
print(d)
# -> deque(['c', 'a', 'b'])
print(''.join(d))
# -> cab
Make a shallow copy of the deque. See below for shallow copies.
copy --- Shallow copy and deep copy operations https://docs.python.org/ja/3/library/copy.html
from collections import deque
d1 = deque([1, 2, 3, 4, 5])
d2 = d1.copy()
print(d1)
# -> deque([1, 2, 3, 4, 5])
print(d2)
# -> deque([1, 2, 3, 4, 5])
d1.append(6)
print(d1)
# -> deque([1, 2, 3, 4, 5, 6])
print(d2)
# -> deque([1, 2, 3, 4, 5])
Count the number of values equal to the arguments in the deque.
Returns a position with a value equal to the argument in the deque. If not found, raise a ValueError.
Deletes the element to the right of pop: deque and returns it. Deletes the element on the left side of popleft: deque and returns it.
Remove the first value equal to the argument in the deque. If not found, raise a ValueError.
Invert the order of the elements in the deque.
from collections import deque
d = deque([1, 2, 3, 4, 5])
d.insert(2, 5)
print(d)
# -> deque([1, 2, 5, 3, 4, 5])
print(d.count(5))
# -> 2
print(d.index(2))
# -> 1
print(d.index(5))
# -> 2
print(d.index(5, 4, 6))
# -> 5
print(d.pop())
# -> 5
print(d)
# -> deque([1, 2, 5, 3, 4])
print(d.popleft())
# -> 1
print(d)
# -> deque([2, 5, 3, 4])
d.remove(5)
print(d)
# -> deque([2, 3, 4])
d.reverse()
print(d)
# -> deque([4, 3, 2])
Add an interactive element to the right.
Add an interactive element to the left.
Moves the element to the right by the value of the argument. Elements beyond the end move to the beginning. If you specify a negative number, it moves to the left.
from collections import deque
d = deque([1, 2, 3, 4, 5])
li = [6,7,8,9]
d.extend(li)
print(d)
# -> deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
d.extendleft(li)
print(d)
# -> deque([9, 8, 7, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9])
d.rotate(1)
print(d)
# -> deque([9, 9, 8, 7, 6, 1, 2, 3, 4, 5, 6, 7, 8])
d.rotate(-1)
print(d)
# -> deque([9, 8, 7, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9])
d.clear()
print(d)
# -> deque([])
Specify the maximum number of elements of deque. If you add more than the maximum number of elements, the element on the opposite side will be deleted.
from collections import deque
li = [1, 2, 3, 4, 5]
d = deque(li, 3)
print(d)
# ->deque([3, 4, 5], maxlen=3)
d2 = deque([], 3)
for i in range(10):
d2.append(i)
print(d2)
# -> deque([7, 8, 9], maxlen=3)
(I am doing it with the feeling of trying it) The performance was compared by simply adding the value to the right if it was an even number and to the left if it was an odd number 1,000,000 times. List was about 147 seconds and deque was about 0.3 seconds.
from collections import deque
import time
start = time.time()
li = []
for i in range(1000000):
if i % 2 == 0:
li.append(i)
else:
li.insert(0, i)
elapsed_time = time.time() - start
print(elapsed_time)
# -> 147.49888038635254
start = time.time()
d = deque([])
for i in range(1000000):
if i % 2 == 0:
d.append(i)
else:
d.appendleft(i)
elapsed_time = time.time() - start
print(elapsed_time)
# -> 0.3092050552368164
I didn't know the deque in the contest, so I created a List with twice the maximum number of elements and added the first element in the middle to handle it. I think it would be easier to solve if I knew the deque, so I wanted to learn the data structure well.
Even if I understand the amount of calculation, I thought that there would be no difference when actually comparing the processing times.
collections --- container data type https://docs.python.org/ja/3/library/collections.html#collections.deque
Data type collections.deque that can be used as a "double-ended queue" in Python https://kakakakakku.hatenablog.com/entry/2019/01/04/214907
[Python] Measures and displays the time required for processing https://qiita.com/fantm21/items/3dc7fbf4e935311488bc
Recommended Posts