Deque(デック) Double-Ended queue 双方向キュー

Deque

双方向キュー

　メリット

　　indexが貼られていないので、要素削除後に生じるindexの張替えがいらないので、先頭や最後への追加・削除が速い。

　デメリット

　　indexがない分、探索が遅い。そのため先頭、最後以外に対しての処理が遅くなる。

処理の速さ・遅さ

10000個の要素がある配列で処理速度を確認してみる

削除に関しては24倍違う。探索1.5倍違う(iterateでは大差はでないかも)

Deque 削除 O(1) 

List削除 O(n)

from collections import deque

import time

d = deque()

# d = []

[d.append(i) for i in range(10000)]

stratTime = time.time() #プログラムの開始時刻

#処理

for i in range(10000):

d[i]

# d.popleft()

# del d[0]

endTime = time.time() #プログラムの終了時刻

runTime = endTime - stratTime #処理時間

print(runTime)

#Deque(削除)0.0014331340789794922//(探索)0.0013191699981689453

#List(削除)0.03389477729797363//(探索)0.000823974609375