バツイチとインケンのエンジニアブログ
プログラムやプログラムじゃないこと

続・あなたのPythonを爆速にする7つの方法

2015-05-25
書いた人 : バツイチ
カテゴリ : Python | タグ : Counter, deque, heapq

以前にあなたのPythonを爆速にする7つの方法を書いた時に、

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は先頭挿入メソッドが存在しないのでベンチマークを取っていません。

  1. list  ・・・list.insert(0, x)
  2. array ・・・array.insert(0, x)
  3. 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件で先頭削除のベンチマークを取りました。

  1. list  ・・・list.pop(0)
  2. array ・・・array.pop(0)
  3. heapq ・・・heapq.heappop()
  4. 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. 配列の初期化

先頭挿入と先頭削除がいくら速くても配列の初期化が遅くては話になりません。
そこで初期化の比較も取りました。

  1. list型: サイズ1(None)の配列を乗算する
  2. list型: for内包表記で配列をつくる
  3. list型: 空配列へappendして配列をつくる
  4. array型: 0〜nのarrayをつくる
  5. deque型: append
  6. 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オブジェクトに項目リストを直接渡す方法の2つを比較しています。


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/

← あなたのPythonを爆速にする7つの方法

このエントリーをはてなブックマークに追加
Tweet

← iOS初心者がSwiftでグノシーみたいなタブ型RSSリーダーを作ってみた
React NativeでTodoアプリを作ってみた →

 

最近書いた記事

  • Ryzen7 3800XT でmini ITXオープンフレームPCを作る
  • Pythonで機械学習入門 競馬予測
  • HP ENVY 15 クリエイターモデルレビューとRAID0解除
  • JRA-VAN データラボを使って、競馬データを収集する
  • Surface Pro 3 にubuntu18.04を入れる

カテゴリー

  • Android
  • Apache Flink
  • API
  • AWS
  • bazel
  • BigQuery
  • Cassandra
  • Docker
  • Druid
  • Elasticsearch
  • Git
  • Golang
  • gradle
  • HDFS
  • JavaScript
  • jvm
  • Linux
  • MongoDB
  • MySQL
  • Nginx
  • Nodejs
  • PaaS
  • PHP
  • Python
  • RabbitMQ
  • Raspberry Pi
  • React Native
  • Redis
  • Riak
  • rust
  • scala
  • Scheme
  • SEO
  • solr
  • Spark
  • spray
  • Sublime Text
  • Swift
  • Tableau
  • Unity
  • WebIDE
  • Wordpress
  • Youtube
  • ひとこと
  • カンファレンス
  • スケジューラ
  • マイクロマウス
  • 広告
  • 技術じゃないやつ
  • 株
  • 機械学習
  • 競馬
  • 自作キーボード
  • 自然言語処理

アーカイブ

  • 2021年4月
  • 2021年2月
  • 2021年1月
  • 2020年3月
  • 2020年2月
  • 2020年1月
  • 2019年10月
  • 2019年9月
  • 2019年8月
  • 2019年7月
  • 2019年6月
  • 2019年5月
  • 2019年4月
  • 2019年2月
  • 2019年1月
  • 2018年12月
  • 2018年11月
  • 2018年9月
  • 2018年5月
  • 2018年3月
  • 2018年2月
  • 2017年9月
  • 2017年8月
  • 2017年6月
  • 2017年4月
  • 2017年3月
  • 2017年1月
  • 2016年10月
  • 2016年9月
  • 2016年8月
  • 2016年6月
  • 2016年5月
  • 2016年4月
  • 2016年3月
  • 2016年2月
  • 2016年1月
  • 2015年12月
  • 2015年11月
  • 2015年10月
  • 2015年9月
  • 2015年8月
  • 2015年6月
  • 2015年5月
  • 2015年2月
  • 2015年1月
  • 2014年12月
  • 2014年11月
  • 2014年9月
  • 2014年6月
  • 2014年5月
  • 2014年3月
  • 2014年2月
  • 2014年1月
  • 2013年12月
  • 2013年11月
  • 2013年10月
  • 2013年9月
  • 2013年8月

書いた人

  • バツイチちゃん
  • インケンくん

このブログについて

エンジニアとしての考え方が間逆な2人がしょーもないこと書いてます。

バツイチ

アイコン

IT業界で働くエンジニアです。名前の通りバツイチです。
理論や抽象的概念が好きだけど人に説明するのが下手。

インケン

アイコン

バツイチちゃんと同じ業界で働いています。
理論とか開発手法とかは正直どうでもよくて、
生活する上で役に立つことに使いたい

Copyright 2025 バツイチとインケンのエンジニアブログ