高速化のためのPython Tips

皆さんこんにちは
お元気ですか？私は元気です。

Pythonにおける高速化手法を掲載してみます。
簡単なコード並びに索引のような感じで引けるようなイメージで作成しました。

本日の目次です。

Pythonにおける高速化の必要性

PythonはC++やJavaと比較すると非常に遅い言語です。
しかし、最近はPythonで書く用途も増えてきており、個人的にも
世間的にも（多分）需要が増えつつあります。
が、計算機に負荷をかける処理を書くことが多いので、（私だけ？）いつも速度に悩まされます。

そんなわけで、今回の記事です。

Pythonの高速化

高速化の手順

基本的にPythonの高速化は次の手順で行われます。
（参考：PythonSpeed/PerformanceTips - Python Wiki）

1. テスト（実行）
2. 遅ければプロファイル取る
3. 最適化する
4. 繰り返す

基本的には遅い部分や期待通りに動いていない箇所を割り出し、その箇所に対して
対策を打つのが基本です。で、その動いていない箇所を割り出すために、Profilingをする作業があります。

Profiling

Pythonのコードにかぎらず、
基本的にはProfilingを取得することから始めます。
つまり、どこが遅いのかを特定するためです。

実行手順は簡単で、オプションを追加して実行すれば、勝手に取得できます。
以下は今回実行した例です。着目ポイントはcumtimeやncallsです。

cumtimeが高ければ実行時間が長いので、その部分に遅い処理を入れている可能性が高いです。
ncallsが高い場合は無駄に関数を呼んでいる可能性があります。

それらの可能性を踏まえながらProfileを見ると高速化の手立てを発見できるかもしれません。
※-s は時間でソートするといった意味です。

python -m cProfile -s time import_cost.py

         10012657 function calls (10012536 primitive calls) in 9.465 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    7.273    7.273    7.777    7.777 import_cost.py:14(list_append_import)
        1    1.298    1.298    1.612    1.612 import_cost.py:6(list_append)
 10001436    0.642    0.000    0.642    0.000 {method 'append' of 'list' objects}
        1    0.076    0.076    9.465    9.465 import_cost.py:1(<module>)
        3    0.053    0.018    0.225    0.075 __init__.py:1(<module>)
        1    0.010    0.010    0.011    0.011 __init__.py:88(<module>)
        1    0.009    0.009    0.013    0.013 __init__.py:15(<module>)
        1    0.009    0.009    0.176    0.176 __init__.py:106(<module>)
        2    0.008    0.004    0.020    0.010 __init__.py:45(<module>)
        1    0.006    0.006    0.016    0.016 utils.py:4(<module>)
        1    0.005    0.005    0.009    0.009 __init__.py:41(<module>)
        1    0.005    0.005    0.005    0.005 npyio.py:1(<module>)
        1    0.004    0.004    0.009    0.009 numeric.py:1(<module>)
        1    0.004    0.004    0.007    0.007 index_tricks.py:1(<module>)
        1    0.003    0.003    0.012    0.012 _internal.py:6(<module>)
        1    0.003    0.003    0.004    0.004 case.py:1(<module>)
        1    0.003    0.003    0.008    0.008 tempfile.py:18(<module>)
        1    0.003    0.003    0.019    0.019 decorators.py:15(<module>)

基本的な条件

計測コード

計測時間が書いてある者については次のような方式で行いました。
非常によくあるコードかと思われます。

start = time.time()
#処理 Ex.list_append_local_val()
print time.time() - start

Pythonの基本的な書き方部分

rangeよりxrangeを（Python2.7）

Pythonはループを2通りの記載の仕方をすることができます。
xrangeはメモリに持たないので、rangeよりも高速にループを回すことができます。

# 遅い
def sum_range():
    result = 0
    for i in range(100):
        result += i

# 早い
def sum_xrange():
    result = 0
    for i in xrange(100):
        result += i

詳しい速度比較はこちらに記載しています。

nonbiri-tereka.hatenablog.com

リストの生成

リストは内包表記で生成するのが高速です。
内包表記をするとメモリに保存する必要がないからです。
実際には次のように記載します。

# 通常の書き方
list = []
for i in xrange(1000000):
   list.append(i)

# リスト内包表記
list  = [i for i in xrange(1000000)]

文字列結合

joinを使えば簡単に結合することができ、なおかつ高速なコードを記述することができます。

def string_operator_join(join_words):
    denominator = ""
    words = ""
    for word in join_words:
        words = denominator + word
        denominator = ","
    return words


def string_join(join_words):
    return ",".join(join_words)

Import文のコスト

Pythonはimport文を関数の中に書くことができます。
しかし、importをするコストが必要となるので、importを関数内で記載する時には注意が必要です。
例えば、以下のような関数を２つ用意しました。違いは関数の途中にimport numpy as npを追加しているかどうかです。

N = 10000000

def list_append():
    result = []
    for i in xrange(N):
        if i % 2 == 0:
            result.append(i)
    return result


def list_append_import():
    result = []
    for i in xrange(N):
        import numpy as np #numpyを何度もimportする。
        if i % 2 == 0:
            result.append(i)
    return result

上記を比較すると次のようになります。

関数名	かかった時間(s)
list_append	1.25
list_append_import	7.43

関数呼び出しのコスト

関数を呼び出すのにもコストがかかります。そのため、あまりにコストが高い呼び出しは避けましょう。
追加しながらリストを生成するlist_append関数を変更してみました。

def append_number(i, number_list):
    if i % 2 == 0:
        number_list.append(i)


def list_append_local_val():
    result = []
    for i in xrange(N):
        append_number(i, result)

関数名	かかった時間（s）
list_append	1.48743391037
list_append_local_val	2.39971590042

ドットを避ける

ドットを避けることで、若干のスピード向上をすることができます。
具体的なこんなコードになります。

N = 10000000

def list_append_local_val():
    result = []
    append = result.append
    for i in xrange(N):
        if i % 2 == 0:
            append(i)
    return result

yieldを使う

最後にyieldを使います。
元々C++を使った実装をメインとしていたので
使う機会というより馴染みがなかったのですが、使ってみるととても使いやすい。

昔はあまりに馴染みがないので利用していませんでしたが、
Deep LearningのアルゴリズムのReal Time Data Augmentationや一定の処理を実施する時に特に使います。

①メモリを消耗しない
yieldのメリットは、処理を一定の間隔（yield）で元の関数で返すので、メモリを消費しにくい
②直感的にループを書ける。
Pythonだと、ループの中でyieldを呼び出す処理を書くだけなので非常にわかりやすく、使いやすい。
（これぐらいならばもっと別の書き方しそうですが・・・）

#yield なし
list = [i * 2 for i in xrange(100)]
for i in xrange(list):
    print i + 10

#yield あり
def iterate(number):
    for i in xrange(number):
        yield i * 2

for j in iterate(100):
    print j + 10

Numpyに関するTips

Numpyはいくつか高速化並びに注意する点があります。

Numpyを使用して基本演算を高速化する

Numpyは基本的にCで記述され、実行速度も非常に高速です。
そのため、Numpyで書けるところはNumpyで書くと、高速になる計算となります。
例えば、合計値を求める演算は次のようになります。

# 通常のリストでの書き方
def number_element_sum(number_list):
    result = 0.0
    for i in xrange(len(number_list)):
         result += number_list[i]
    return result

# Numpyを使うので、高速に書ける。
def numpy_sum(numpy_list):
    return np.sum(numpy_list)

Numpyの要素にアクセスする演算をしない

Numpyは通常のリスト構造と同じく、アクセスはできます。
しかし、アクセスする速度が異様に遅いため、極力アクセスは阻止し、numpyを使って演算するようにします。

import numpy as np

# アクセスを繰り返すので非常に低速
def numpy_element_sum(numpy_list):
    result = 0.0
    for i in xrange(len(numpy_list)):
         result += numpy_list[i]
    return result

#こちらが高速
def numpy_sum(numpy_list):
    return np.sum(numpy_list)

詳しくは過去の記事を参考にしてください。

Numbaで手早く高速化

Numbaを使うとアノテーションを使うのみでコードを高速化できます。
以下のコードを用いて、私の実行環境で検証してみました。

yutori-datascience.hatenablog.com

numbaを適用したいメソッドに@jit（パッケージはnumba）を付与することで
勝手に適用するすぐれものです。詳しい使い方は別途、試していたいと思います。

python: 3.78625607491
numba: 0.206073999405

その他高速化ツール

Cython

Cythonは、Pythonで書かれたコードをC、C++のようにコンパイルすることで高速化するツールです。
詳しくは以下の記事を御覧ください。

Dask

Daskは柔軟な並列分散ライブラリです。

シンプルに記述できて、非常に良い感じです。
しかし、ある程度大規模にならないと、高速化しないように感じられるので
ある程度対応する規模を見積もる必要があると思います。

Dask — dask 0.11.0 documentation

PyPy

Pythonを高速に実装したのがPyPyです。但し、簡単に実行ができる代わりに
numpy, scipy周りが動かないようなものも出ます。（そのため使っておりません・・）
詳しくは以下をご覧ください。
nonbiri-tereka.hatenablog.com

公式ページ
pypy.org

感想並びに展望

今回はPythonにおける高速化といった観点で記事を書きました。
もっとこんな便利なのがありますといった話があれば、ぜひ。

参考文献

PythonSpeed/PerformanceTips - Python Wiki