以前にあなたのPythonを爆速にする７つの方法を書いた時に、
collections.deque とheapq.heappop の存在にも触れておくべきだと思う
というご指摘を頂きましたので、新たにcollections.dequeとheapq、プラスcollections.Counterのベンチマークを追加しました。
1. heapqとdequeについて
heapq
まずheapqですがPythonの公式ドキュメントによると、下記のように記されています。
このモジュールではヒープキューアルゴリズムの一実装を提供しています。優先度キューアルゴリズムとしても知られています。
ヒープとは、全ての親ノードの値が、その全ての子の値以下であるようなバイナリツリーです。この実装は、全ての k に対して、ゼロから要素を数えていった際に、 heap[k] <= heap[2*k+1] かつ heap[k] <= heap[2*k+2] となる配列を使っています。
要はバイナリツリーを表現するモジュールとして設計されており、値を追加したときも削除したときも常に値の順番が維持されます。
よって使いどころは「順番（挿入順ではなく値の大きさの順序）を意識する必要があるとき」になります。
deque
次にdequeですが、こちらもPythonの公式ドキュメントに寄ると、下記のように記されています。
Deque とは、スタックとキューを一般化したものです。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。
list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。
pop(0) や insert(0, v)に関してはlistよりも相当高速に動作するよう設計されています。
前回、
- 配列の先頭削除は激遅
- 配列の先頭挿入も激遅
やったら即死の禁じ手・・・と書きましたが、dequeを使うことで解決できそうです。
早速ベンチマークを取ってみました。
2. insert – 先頭に挿入 – O(1)の実力
計算量O(n)とO(1)の違いを見るために、10,000件と1,000,000件で先頭挿入のベンチマークを取りました。
※heapqは先頭挿入メソッドが存在しないのでベンチマークを取っていません。
- list ・・・list.insert(0, x)
- array ・・・array.insert(0, x)
- deque ・・・deque.appendleft(x)
まずは10,000件のデータを先頭に挿入するベンチマークです。
import sys
from array import array
from benchmarker import Benchmarker
from collections import deque
n = int(sys.argv[1]) if len(sys.argv) > 1 else 1000*1000
with Benchmarker(n, width=20) as bench:
nay = []
iay = array('I', [])
day = deque()
@bench("list")
def _(bm):
for i in xrange(n):
nay.insert(0, i)
@bench("array")
def _(bm):
for i in xrange(n):
iay.insert(0, i)
@bench("deque")
def _(bm):
for i in bm:
day.appendleft( i )
まずは10,000件のデータを先頭に挿入するベンチマークです。
10,000件ではarrayが一番速くdequeが一番遅いので、肩透かしをくったような気持ちです。
| # | 操作 | time(sec) |
| 1 | array.insert(0, x) | 0.0083 |
| 2 | list.insert(0, x) | 0.0260 |
| 3 | deque.appendleft(x) | 0.1191 |
ところが1,000,000件のデータでは順位が一変します。
| # | 操作 | time(sec) |
| 1 | deque.appendleft(x) | 0.1176 |
| 2 | array.insert(0, x) | 86.6021 |
| 3 | list.insert(0, x) | 240.1593 |
dequeではデータ量が100倍になっても速度は一定なのに対し、array, listは爆発的に遅くなっています。
これが計算量O(1)の実力ですね。
3. pop – 先頭から削除 – O(1)の実力
先頭から削除でも先頭に挿入と同様、10,000件と1,000,000件で先頭削除のベンチマークを取りました。
- list ・・・list.pop(0)
- array ・・・array.pop(0)
- heapq ・・・heapq.heappop()
- deque ・・・deque.popleft()
n = int(sys.argv[1]) if len(sys.argv) > 1 else 1000*1000
with Benchmarker(n, width=20) as bench:
nay = [i for i in xrange(n)]
iay = array('I', [i for i in xrange(n)])
day = deque(nay)
hay = []
for i in xrange(n):
heapq.heappush(hay, i)
@bench("list")
def _(bm):
for i in bm:
nay.pop(0)
@bench("array")
def _(bm):
for i in bm:
iay.pop(0)
@bench("heappop")
def _(bm):
for i in bm:
heapq.heappop(hay)
@bench("deque")
def _(bm):
for i in bm:
day.popleft()
まずは10,000件を先頭から削除するベンチマークです。
10,000件ですでにdequeが一番速いですが、まあこのくらいなら許容範囲です。
| # | 操作 | time(sec) |
| 1 | deque.popleft() | 0.0011 |
| 2 | array.pop(0) | 0.0083 |
| 3 | list.pop(0) | 0.0149 |
| 4 | heapq.heappop() | 0.0462 |
次は1,000,000件です。
dequeはやはり一定です。
heapqのheappopもそこそこ速いですが、データ量の100倍増加に伴い速度も100倍強かかるようになったので、heappopの計算量は少なくともO(1)ではないことがわかります。
| # | 操作 | time(sec) |
| 1 | deque.popleft() | 0.0011 |
| 2 | heapq.heappop() | 6.3716 |
| 3 | array.pop(0) | 85.2537 |
| 4 | list.pop(0) | 180.3090 |
4. 配列の初期化
先頭挿入と先頭削除がいくら速くても配列の初期化が遅くては話になりません。
そこで初期化の比較も取りました。
- list型: サイズ1(None)の配列を乗算する
- list型: for内包表記で配列をつくる
- list型: 空配列へappendして配列をつくる
- array型: 0〜nのarrayをつくる
- deque型: append
- heapq型: heappush
1〜4までは前回と同じです。前回ではlist型のNone配列の乗算がもっとも高速でした。
サイズ1,000,000の配列を作成します。
import sys
from array import array
from benchmarker import Benchmarker
from collections import deque
import heapq
n = int(sys.argv[1]) if len(sys.argv) > 1 else 1000*1000
with Benchmarker(n, width=20) as bench:
@bench("list append")
def _(bm):
xs = []
for i in bm:
xs.append(i)
@bench("for")
def _(bm):
xs = [i for i in bm]
@bench("[None] only")
def _(bm):
xs = [None] * n
@bench("array")
def _(bm):
xs = array('I', [ i for i in bm ])
@bench("heappush")
def _(bm):
xs = []
for i in bm:
heapq.heappush(xs, i)
@bench("deque")
def _(bm):
xs = deque()
for i in bm:
xs.append( i )
やはり配列の乗算([None]*nのやつ)がもっとも高速です。
dequeやheapqも決して遅くはないのですが、強みはここではないですね。
| # | 操作 | time(sec) |
| 1 | list型: サイズ1(None)の配列を乗算する | 0.0073 |
| 2 | list型: for内包表記で配列をつくる | 0.0411 |
| 3 | list型: 空配列へappendして配列をつくる | 0.0989 |
| 4 | array型: 0〜nのarrayをつくる | 0.1047 |
| 5 | deque型: append | 0.1107 |
| 6 | heapq型: heappush | 0.4908 |
5. カウントする(おまけ)
Word-Countを代表に、文字の数を数えたり、数値の数を数えたりすることは良くあります。
dict型（連想配列）のキーを数えたい文字、値を個数にして計算したりしますが、Pythonのcollectionsには便利はCounterというオブジェクトが用意されています。
その名の通り、何かをカウントするためのオブジェクトです。
こちらも従来のdictを使ったやり方とCounterの速度を比較してみました。
Counterに関しては、Counterオブジェクトのキーを加算する方法とCounterオブジェクトに項目リストを直接渡す方法の２つを比較しています。
import string, sys
from benchmarker import Benchmarker
from collections import Counter
from random import Random
n = int(sys.argv[1]) if len(sys.argv) > 1 else 1000*1000
with Benchmarker(n, width=20) as bench:
ix = [ i for i in xrange(n) ]
r = Random()
r.shuffle(ix)
chs = list(string.ascii_letters)
ws = []
for i in ix:
m = i % 52
ws.append( chs[m] )
@bench("dict")
def _(bm):
dt = dict()
for i in bm:
key = ws[i]
v = dt.setdefault( key, 0 )
dt[key] += 1
@bench("Counter1")
def _(bm):
dt = Counter()
for i in bm:
key = ws[i]
dt[key] += 1
@bench("Counter2")
def _(bm):
dt = Counter( ws )
Counter、別に速くはないです^^;
ただ、dt = Counter( ws )のように一瞬にして数え上げができるのはすごく便利です。
| # | 操作 | time(sec) |
| 1 | dict | 0.2395 |
| 2 | Counterに項目リスト | 0.2940 |
| 3 | Counterのキーを加算 | 0.3784 |
6. まとめ
- 配列への先頭挿入や先頭削除をしたいときはdeque一択
- 値の大きさ順を維持したいときはheapqが便利
- 固定長配列を使うときは[None]*nが鬼速
- Word-CountにはCounterが便利
ここに掲載したソースコードは下記にあります。
https://github.com/x1-/codeforces/blob/master/time/
