Python3エンジニア認定基礎試験の勉強中です。
今日は問題を解いていて、あれ？となったスタックとキューについて、そこから派生して調べたcollections.dequeの処理が効率的な理由を簡単にメモを残します。
スタック
LIFO : 後入れ先だし = 最後に追加したものが最初に出てくる
push : スタックにデータを追加すること
pop : スタックからデータを取り出すこと
# 簡単な例
stack = []
stack.append(1) # pythonではpushをappend()を使用
stack.append(2)
stack.append(3)
print(stack) # [1, 2, 3]
print(stack.pop()) # pythonではpop()を使用 -> 最後に追加した 3 が取り出される
キュー
FIFO : 先入れ先出し = 先に追加したものが先に出てくる
enqueue : キューにデータを追加する
dequeue : キューからデータを取り出す
# 簡単な例
# 効率的にキューを使うために collections.dequeを使用する
from collections. import deque
queue = deque()
queue.append('a') # enqueueはappend()を使う
queue.append('b')
queue.append('c')
print(queue) # deque(['a', 'b', 'c'])
queue.popleft() # dequeueはpopleft()を使う: 'a' が取り出される
厳密にはcollections.dequeは両端キューというデータ構造
キューは先述の通り「先入れ先出し」だが、
collections.dequeでは実際は両端でデータの追加、削除ができる。(両端キュー)
- 末尾に要素を追加 :
append() - 先頭の要素を取り出す :
popleft() - 先頭に要素を追加 :
appendleft() - 末尾の要素を取り出す :
pop()
なぜcollections.dequeは効率的なのか？
リストは一列にデータが並んでいるのに対して、両端キューでは各要素が独立したノードとして存在していて、相互にリンクしあっているイメージ(ポインタ)。
n個の要素を持つリストにpop(0)を実行したときにかかる時間はO(n)なのに対し、
n個の要素を持つdequeにpopleft()を実行したときにかかる時間は0(1)。
nの値が大きくなるほど、dequeのpopleft()を使用した効率化のメリットは大きくなる。
リストでの処理時間
pop(0)で先頭の要素を取り出すと、残った要素のインデックスを一つずつ前にシフトする操作も発生する。
この時、リストの要素数をn個とすると処理にかかる時間は？
(1) pop(0)でO(1)
(2)残りのn-1個の要素をインデックスを前方にシフトするためO(n-1)
∴ O(1) + O(n-1) = O(n)
dequeでの処理時間
dequeではpopleft()を実行すると、先頭の要素Aのポインタが削除(Aの参照しているメモリが解放)され新たな先頭になる要素Bのポインタが更新される。これにかかる時間は定数時間でO(1)。
💡間違いがないように調べながら掲載するようにしていますが、
万が一間違いなどお気づきの点がありましたらコメントにてご指摘いただけますと幸いです🙇♂️