Open2

listとdequeの違い

masatotezukamasatotezuka

はじめに

「両端キュー（deque）」について初めて学んだので、より理解を深めるために、Pythonを使ってパフォーマンスを調べてみた。

dequeについて

データ構造は、両端からデータを追加や削除することができるようになっている。
先頭・末尾両方に対してO(1)のコストで実施できる。
（listだと先頭に追加する場合にO(n)のコストがかかる）

listとdequeそれぞれの先頭に要素を追加していき、実行時間を計測してみる。
（普段使っている、JavaScriptにはdeque型はないらしい）

検証

実行環境

PyCharm

ソースコード

from collections import deque
import time

start = time.time()
li = []
for i in range(100000):
     li.insert(0, i)
elapsed_time = time.time() - start
print(elapsed_time)
# 2.4549272060394287

start = time.time()
d = deque([])
for i in range(100000):
    d.insert(0,i)
elapsed_time = time.time() - start
print(elapsed_time)
# 0.008011817932128906

実行結果

100000の要素を追加するのに要した時間は下記の通り。
たしかに、deque型のほうが実行速度が速い。

  • list：2.4549272060394287
  • deque： 0.008011817932128906
masatotezukamasatotezuka

dequeをコードで表現してみる。

class Node:
    def __init__(self, data):
        self.prev = None
        self.data = data
        self.next = None


class Deque:
    def __init__(self):
        self.head = None
        self.tail = None

    def peekFront(self):
        if self.head is None:
            return None
        return self.head.data

    def peekBack(self):
        if self.tail is None: return None
        return self.tail.data

    def enqueueFront(self, data):
        if self.head is None:
            self.head = Node(data)
            self.tail = self.head
        else:
            self.head.prev = Node(data)
            self.head.prev.next = self.head
            self.head = self.head.prev

    def enqueueBack(self, data):
        if self.head is None:
            self.head = Node(data)
            self.tail = self.head
        else:
            self.tail.next = Node(data)
            self.tail.next.prev = self.tail
            self.tail = self.tail.next

    def dequeueFront(self):
        if self.head is None:
            return None
        temp = self.head
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        else:
            self.head.prev = None
        return temp

    def dequeueBack(self):
        if self.tail is None:
            return None
        temp = self.tail
        self.tail = self.tail.prev
        if self.tail is None:
            self.head = None
        else:
            self.tail.next = None
        return temp