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

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

2015-05-08
書いた人 : バツイチ
カテゴリ : Python | タグ : チューニング

最近プロコン(プログラミング・コンテスト)をはじめました。
基本的にはアルゴリズム勝負なのですが、とにかく速度を競うプロコンです。
小手先の速度チューニングもバカにできません。

何が速くて何が遅いのかはっきりさせるため、ボトルネックになりそうな操作のベンチマークを取りました。

実行環境は下記のとおりです。

  • python2.7.5
  • OS: MacOSX 11
  • CPU: Core i7 2GHz (4core)
  • MEM: 16GB

その1. 配列の初期化を高速化する

まずはプロコンの基本中の基本、配列の初期化です。
下記7つの初期化方法を比較してみます。

  1. 空配列へappendして配列をつくる
  2. for内包表記で配列をつくる
  3. サイズ1(None)の配列を乗算してから値を代入する
  4. サイズ1(None)の配列を乗算する
  5. サイズ1(ゼロ)の配列を乗算する
  6. すべてゼロのarrayをつくる
  7. 0〜nのarrayをつくる

サイズ1,000,000の配列を作成します。


start = time.clock()

"""
1. list append
1000000	0.156414
"""
xs = []
for i in xrange(n):
  xs.append(i)

"""
2. for
1000000	0.0876
"""
xs = [i for i in xrange(n)]

"""
3. [None]
1000000	0.099896
"""
xs = [None] * n
for i in xrange(n):
  xs[i]

"""
4. [None] only
1000000	0.005255
"""
xs = [None] * n

"""
5. [0]
1000000	0.005359
"""
xs = [0] * n

"""
6. array
1000000	0.108973
"""
xs = array('I', [ 0 for _ in xrange(n) ])

"""
7. array
1000000	0.149061
"""
xs = array('I', [ i for i in xrange(n) ])

end = time.clock()
print end - start

# 操作 time(sec)
1 空配列へappend 0.156414
2 for内包表記 0.0876
3 None配列を乗算&代入 0.099896
4 None配列を乗算 0.005255
5 0配列を乗算 0.005359
6 すべてゼロのarrayをつくる 0.108973
7 0〜nのarrayをつくる 0.149061

※サイズはすべて1,000,000

とにかく配列の乗算([None]*nのやつ)が鬼速です。
for内包表記の方が速いと思っていたので意外でした。
固定長の配列をつくるときは[None]*nが( ̄ー ̄)bグッ!

その2. 配列を高速にランダム・リードする

シーケンシャルにではなく、ランダムに配列から値を読み取る場合にどの構造体が速いか比較してみます。

  1. list型
  2. Integerのarray型
  3. Byteのarray型

サイズ1,000,000の配列を作成し、読み取りを行います。


r = Random()
ix = [i for i in xrange(n)]
r.shuffle(ix)

nay = [i for i in xrange(n)]
iay = array('I', [ i for i in xrange(n) ])
bay = array('b', [ 1 for _ in xrange(n) ])

start = time.clock()

"""
1. list
10000000	0.367742
"""
tmp = 0
for i in ix:
  tmp = nay[i]

"""
2. array
10000000	0.263049
"""
tmp = 0
for i in ix:
  tmp = iay[i]

"""
3. 1byte array
10000000	0.232178
"""
tmp = 0
for i in ix:
  tmp = bay[i]

end = time.clock()
print end - start

# 操作 time(sec)
1 list型 0.367742
2 Integerのarray型 0.263049
3 Byteのarray型 0.232178

※サイズはすべて1,000,000

ランダム・リードではByte型のarrayが最速です。

その3. pop – うしろから削除 – 削除するならこれ!

配列の要素を削除します。
まずは計算量の少ない後ろから削除です。

  1. list型
  2. Integer型のarray

サイズ1,000,000の配列を作成し、popします。


nay = [i for i in xrange(n)]
iay = array('I', [i for i in xrange(n)])

start = time.clock()

"""
1. list
10000000	0.205749
"""
for i in xrange(n):
  nay.pop()

"""
2. array
10000000	0.302395
"""
for i in xrange(n):
  iay.pop()

end = time.clock()
print end - start

# 操作 time(sec)
1 list型 0.205749
2 array型 0.302395

※サイズはすべて1,000,000

後ろから削除はarrayよりlistの方が速いです。
どちらにしても1,000,000回の試行でこのくらいの処理速度ならまあ許容範囲でしょうか。

その4. pop – 先頭から削除 – やらない方がよい ※追記あり

配列の要素を先頭から削除します。
3.の後ろから削除に比べると計算量が激増します。

  1. list型
  2. Integer型のarray

サイズ1,000,000の配列を作成し、popします。


nay = [i for i in xrange(n)]
iay = array('I', [i for i in xrange(n)])

start = time.clock()

"""
1. list
10000000	182.47865
"""
for i in xrange(n):
  nay.pop(0)

"""
2. array
10000000	85.623589
"""
for i in xrange(n):
  iay.pop(0)

end = time.clock()
print end - start

# 操作 time(sec)
1 list型 182.47865
2 array型 85.623589

※サイズはすべて1,000,000

こちらはarrayの方が若干速いですが・・・速い方のarrayで1分以上かかっているので、先頭から削除はやったら即死の禁じ手です。
同じpopでも後ろから削除する場合と全然違います。

2015-05-25 追記:
続・あなたのPythonを爆速にする7つの方法に書かせて頂いたのですが、先頭から削除したい場合はdequeを使うと良いです。

その5. insert – 先頭に挿入 – 遅い代表 ※追記あり

popの次はinsert、先頭に挿入です。
これも先頭から削除と同様コストのかかる処理です。

  1. list型
  2. Integer型のarray

サイズ1,000,000の配列を作成し、insertします。


nay = []
iay = array('I', [])

start = time.clock()

"""
list
1000000	241.515497
"""
for i in xrange(n):
  nay.insert(0, i)

"""
array
1000000	86.058389
"""
for i in xrange(n):
  iay.insert(0, i)

end = time.clock()
print end - start

# 操作 time(sec)
1 list型 241.515497
2 array型 86.058389

※サイズはすべて1,000,000

popと同様arrayの方が若干速いですが、先頭挿入の繰り返しは極力避けたほうがよいです。
appendするか、最初に挿入すべきサイズを確保した配列を作成した方が速いです。

2015-05-25 追記:
popと同様続・あなたのPythonを爆速にする7つの方法に書かせて頂いたのですが、先頭挿入したい場合はdequeを使うと良いです。

その6. 文字列検索を高速化する

文字列検索もいくつかやり方があります。
下記の4つを比較しました。

  1. findメソッド
  2. in
  3. reモジュール
  4. 事前コンパイルしたreモジュール

長さ1,000,000の文字列を作成し、検索します。


search = '_SEARCH_'

ix = [ i for i in xrange(n) ]
r = Random()
r.shuffle(ix)
sp = int(n * 4 / 5)

chs = list(string.ascii_letters)
t = ''
for i in ix[0:sp]:
  m = i % 52
  t += chs[m]

t += search
for i in ix[sp:]:
  m = i % 52
  t += chs[m]

start = time.clock()

"""
1. find
1000000	322.414854
"""
for i in xrange(n):
  idx = t.find(search)

"""
2. in
1000000	314.847081
"""
for i in xrange(n):
  idx = search in t

"""
3. re
1000000	674.792997
"""
for i in xrange(n):
  m = re.search(search, t)
  idx = m.start()

"""
4. re 事前にコンパイル
1000000	674.394229
"""
p = re.compile(search)
for i in xrange(n):
  m = p.search(t)
  idx = m.start()

end = time.clock()
print end - start

# 操作 time(sec)
1 find 322.414854
2 in 314.847081
3 re 674.792997
4 re 事前にコンパイル 674.394229

1,000,008byteの文字列から_SEARCH_という文字列を検索しています

正規表現モジュールreを使うより、in(またはfind)を使った方が圧倒的に速いです。
このあたりは多言語と同じですね。
正規表現を使わなくて実現できる検索であればinを使った方が高速です。

その7. 標準入力&標準出力

これは完全にプロコン向けなのですが。
標準入力を受け取りながら、計算し、出力したほうが速いのか
標準入力をすべて受け取ってしまってから計算&出力したほうが速いのかを検証しました。

  1. raw_input で 標準入力を受け取りながら出力
  2. raw_input で 標準入力を受け取りながら結果をバッファリング
  3. raw_input で 標準入力をすべて受け取ってから出力
  4. raw_input で 標準入力をすべて受け取りバッファリングした結果を出力

1,000,000個の標準入力を受け取り、1,000,000の出力を行います。


start = time.clock()
"""
1. raw_input で 標準入力を受け取りながら出力
1000000	3.504401
"""
for i in xrange(n):
  x = int(raw_input()) / 10
  print x

"""
2. 結果をバッファリング
1000000	3.268692
"""
res = []
for i in xrange(n):
  res.append( int(raw_input()) / 10 )
for i in res:
  print i

"""
3. raw_input で 標準入力をすべて受け取ってから出力
1000000	3.22516
"""
xs = [ int(raw_input()) for _ in xrange(n) ]
for i in xs:
  x = i / 10
  print x

"""
4. raw_input で 標準入力をすべて受け取りバッファリングした結果を出力
1000000	3.125762
"""
xs = [ int(raw_input()) / 10 for _ in xrange(n) ]
for i in xs:
  print i

end = time.clock()
print end - start

# 操作 time(sec)
1 標準入力を受け取りながら出力 3.504401
2 標準入力を受け取りながら結果をバッファリング 3.268692
3 標準入力をすべて受け取ってから出力 3.22516
4 標準入力をすべて受け取りバッファリングした結果を出力 3.125762

※1,000,000件の標準入力を受け取り1,000,000件の出力を行っています

標準入力をすべて受け取ってから計算を行ったほうが速いです。
体感的にはもっと速かったんだけどな(・・;)


まとめ

  • 配列作成は[None]*nが高速
  • ランダム・リードはarrayが強い
  • 配列の先頭削除は激遅※
  • 配列の先頭挿入も激遅※
  • 正規表現reは遅い
  • 文字列検索はinが速い
  • 標準入力は一旦バッファしてから処理すると良い

※配列の先頭削除、先頭挿入はdequeを使いましょう。
レッツ・プロコンv( ̄Д ̄)v イエイ

ここに掲載したソースコードは下記にあります。
https://github.com/x1-/codeforces/blob/0.0.1/time/bench.py


2015-05-14 追記:
@mathhunさんにプルリクエストを頂き、Benchmarkerを利用したコードに変更しました。

https://github.com/x1-/codeforces/blob/master/time/


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

← JSで株のローソク足チャートを生成するためのjQueryプラグイン jqPlot
iOS初心者がSwiftでグノシーみたいなタブ型RSSリーダーを作ってみた →

 

最近書いた記事

  • 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 バツイチとインケンのエンジニアブログ