Pythonプログラムが遅い！高速化したい！そんな時は...

Pythonで実装したときに、処理時間が長すぎて要件を満たせないことがあります。そんなときにはこの記事で示す4種類の対策があります。

なお、高速化のために何かをすると別の何かを失います。トレードオフの代表例としては、表現の自由度、可読性、依存度、メモリ使用量、CPU使用量でしょうか。用法・容量を守って正しくお使いください。

また、高速化をする前にはスクリプトのどこが遅いのか、プロファイリングツールなどを使って確かめる必要があります。遅くない処理を頑張って高速化しても、全体の実行時間にはほとんど影響を与えません。この記事ではその手順については説明しません。

4種類の高速化手法

この記事では、下記の4種類の高速化手法について紹介します。

1. 言語仕様・標準ライブラリの範疇でスクリプトを書き直す
2. ライブラリを使う
3. ライブラリを作る
4. バイトコードを最適化する

1. 言語仕様・標準ライブラリの範疇でスクリプトを書き直す

本来は「ライブラリを使う」や「ライブラリを作る」といったほかの対策も「スクリプトを書き直す」に該当します。ここではPythonの言語仕様と標準ライブラリの範疇でできることとして、下記の手法を紹介します。標準ライブラリの範疇でできることなので、依存はあまり増えません(ただし、Pythonのバージョンには依存することがあります)。

• 1-1. Pythonスクリプトの書き方を見直す
• 1-2. アルゴリズムとデータ構造を工夫する
• 1-3. キャッシュを活用する
• 1-4. 並列化する

1-1. Pythonスクリプトの書き方を見直す

Pythonのインタプリタの最適化はそれほど頑張ってくれません。同じことをするにもいろいろな書き方があるので、より高速な書き方を選んで高速化することができます。

ただし、実際のアプリケーションではここで例を挙げる書き方の違いでそんなに差は出ません。書き方の変換が思いつかない場合や遅い処理はほかの場所にあることが多いはずです。

もちろん、ちりも積もればなんとやらです。例えば、Pythonのみでデータベースの実装をしようと思うと、ここで例を挙げるような処理の遅さが効いてきて、全体としても使い物にならないくらい遅くなってしまいます。

例1: 1からnまでの総和

例えば、1からnまでの整数を足す処理を、「(1)forを使って足していく」「(2)ビルトインのsumを使う」「(3)総和の公式を使う」の3通りで実装して、時間を計ってみると下記のようになります。

In [1]: %%timeit
   ...: sum = 0
   ...: for n in range(1000000):
   ...:     sum += n
87.3 ms ± 492 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [2]: %%timeit
   ...: sum(range(1000000))
33.3 ms ± 1.47 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [3]: %%timeit
   ...: ((1000000-1)*1000000)//2
13 ns ± 0.538 ns per loop (mean ± std. dev. of 7 runs, 100000000 loops each)

方式	実行時間	備考
(1)forを使って足していく	87.3 ms ± 492 μs
(2)ビルトインのsumを使う	33.3 ms ± 1.47 ms
(3)総和の公式を使う	13 ns ± 0.538 ns	単位がナノなのでミリにすると1/1000000

この例では、総和公式が高速なのですが、常にこんな変換を思いつくとは限りません。

例2: リストの生成

リストを生成するときに、「(1)リスト内包表記を使う」「(2)forループでappendする」「(3)appendをキャッシュする」「(4)ビルトインのlist関数を使う」の4通りで実装して、時間を計ってみると下記のようになります。

In [1]: %%timeit
   ...: l = [n for n in range(1000000)]
81.7 ms ± 1.31 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [2]: %%timeit
   ...: l = []
   ...: for n in range(1000000):
   ...:     l.append(n)
130 ms ± 2.08 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [3]: %%timeit
   ...: l = []
   ...: l_append = l.append
   ...: for n in range(1000000):
   ...:     l_append(n)
97.9 ms ± 2.01 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [4]: %%timeit
    ...: l = list(range(1000000))
58.1 ms ± 1.49 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

方式	実行時間	備考
(1)リスト内包表記を使う	81.7 ms ± 1.31 ms
(2)forループでappendする	130 ms ± 2.08 ms
(3)appendをキャッシュする	97.9 ms ± 2.01 ms
(4)ビルトインのlist関数を使う	58.1 ms ± 1.49 ms

この例では、リストを生成しているだけですが、一般的にはappendする前に「いろいろな処理」をするはずです。この「いろいろな処理」のほうが遅いことが多いので、「いろいろな処理」を高速化したほうが効果があります。

1-2. アルゴリズムとデータ構造を工夫する

アルゴリズムとデータ構造は、大昔から研究されている分野です。計算量がオーダー記法で$O(n)$と$O(n^2)$では、実行時間も全然違います。アルゴリズムとデータ構造を自分で実装することもあれば、標準ライブラリにある便利なクラスを使う場合こともあります。

ここでは、標準ライブラリにあるアルゴリズムとデータ構造について例を挙げます。

例3: データの探索

リストに特定の要素が含まれているかを何回も判定するときは、リストを集合(set)に変換してからinで確かめたほうが早いです。1回しか判定しないのであれば、集合に変換する処理時間が効いてくるでしょう。

In [1]: %%timeit
   ...: l = list(range(10000))
   ...: for n in range(10000):
   ...:     n in l
1.04 s ± 19 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [2]: %%timeit
   ...: l = list(range(10000))
   ...: s = set(l)
   ...: for n in range(10000):
   ...:     n in s
1.45 ms ± 14.5 μs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

方式	実行時間	備考
リストに対してinで判定	1.04 s ± 19 ms
集合に対してinで判定	1.45 ms ± 14.5 μs	単位がミリなのでミリを取ると1/1000

今回は、10000個の要素からなるリストに対して、10000回検索するだけでこの結果となりました。これくらいの量の探索なら、実際のアプリケーションでもよく出てくるのではないでしょうか。

例4: データの操作

リストの先頭に何度も値を追加したい時にはcollections.dequeを使うことができます。

In [1]: from collections import deque

In [2]: %%timeit
   ...: l = []
   ...: for n in range(100000):
   ...:     l.insert(0, n)
6.29 s ± 28.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [3]: %%timeit
   ...: dq = deque()
   ...: for n in range(100000):
   ...:     dq.appendleft(n)
11.7 ms ± 93.1 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

方式	実行時間	備考
リストに対してinsertで先頭に要素を追加	6.29 s ± 28.1 ms
dequeに対してappendleftで先頭に要素を追加	11.7 ms ± 93.1 μs	単位がミリなのでミリを取ると1/1000

Pythonのリストは、可変長配列のようなものです。配列の中身については、型や順序など何の前提もないので汎用性は高いですが、特定の処理では高速化・効率化の余地があります。collections.dequeのほかにもheapqやbisectなどコレクション(データの集まり)を扱う機能が標準ライブラリに用意されています。

1-3. キャッシュを活用する

一度行った計算の結果をメモリ内に格納して再利用したり、データベースからとってきたデータをpickle形式でdumpすることで、高速化することができます。数学的な関数のような引数が一緒ならば常に同じ結果を返すものは、キャッシュすることができます。データベースと通信するよりも、ローカルファイルを読み込んだほうが高速な場合もあります。

例5: 関数のメモ化

Pythonにはfunctools.lru_cacheという関数をメモ化するためのデコレータが標準ライブラリに定義されています。これを使えば一度計算した結果がキャッシュされ、引数が同じであれば再利用されます。

In [1]: from functools import lru_cache

In [2]: def fib(n):
   ...:     return n if n <= 1 else fib(n-2) + fib(n-1)

In [3]: %%timeit
   ...: fib(30)
448 ms ± 4.22 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [4]: @lru_cache()
   ...: def fib(n):
   ...:     return n if n <= 1 else fib(n-2) + fib(n-1)

In [5]: %%timeit -n1 -r1
   ...: fib(30)
24.2 μs ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

方式	実行時間	備考
キャッシュなし	448 ms ± 4.22 ms
lru_cacheデコレータによるキャッシュあり	24.2 μs ± 0 ns	単位がマイクロなのでミリにすると1/1000,最終結果fib(30)がキャッシュされてしまうのでtimtitマジックコマンドでは繰り返せない

@lru_cacheデコレータを付ければいいだけなのでお手軽ですね。実際にフィボナッチ数列を計算したいことはあまりないですし、計算したいとしても別の実装にするかもしれません。機械学習で積分を計算したい時などが代表的な応用例でしょうか。

1-4. 並列化する

標準ライブラリのthreadingやmultiprocessingを使ったり、Python3.2で追加されたconcurrentを使って並列化することで高速化します。CPUがボトルネックでなければthreading、そうでなければmultiprocessingを使います。threadingのほうがデータの共有が簡単ですがGIL(Global Interpreter Lock)によりのCPU100%の壁を越えられないため、マルチコアCPUを使い切りたいのであればmultiprocessingを使うことになります。

例6: concurrentライブラリ

concurrent.futureを使うのが簡単です。ProcessPoolExecutorを使えば、マルチプロセスで並列実行できます。マルチスレッドで実行するThreadPoolExecutorもあります。

from time import sleep
from random import uniform
def f(x):
    sleep(uniform(0, 1) * 10)
    return x

from concurrent.futures import ProcessPoolExecutor, Future, wait
with ProcessPoolExecutor(max_workers=10) as executor:
    futures = [executor.submit(f, x) for x in range(10)]
    done, not_done = wait(futures)
    results = [future.result() for future in futures]

並列化したい処理を関数化して、ワーカー数を指定して呼び出すだけです。定型句として覚えてしまいましょう。

例7: splitコマンド + Pythonスクリプト

マルチプロセスにするのであれば、Pythonではなくshellで頑張ることもできます。前述の関数fをコマンドラインから実行可能にして、shellから並列に呼び出してあげることでマルチプロセスが実現できます。

例えば、入力ファイルが下記(input)だとします。

input

0
1
2
3
4
5
6
7
8
9

splitコマンドで適当に分割します。

$ split -l 1 input

分割したファイルを入力として、Pythonスクリプトを実行します。

$ for file in `ls x*`; do python f.py ${file}&; done

分割された実行結果を、結合します。

$ cat x*.result > result

Pythonの中で全部実現することもできますが、shellで&を付けるだけで気楽にマルチプロセスにするのも状況によってはありだと思います。

2. ライブラリを使う

Pythonには標準ライブラリがたくさんありますし、サードパーティのライブラリはもっとたくさんあります。サードパーティのライブラリは、PyPIで公開されており、pipコマンドで簡単にインストールすることができます。

• 2-1. ライブラリを使う
• 2-2. ライブラリの環境変数やコンパイル条件を見直す

2-1. ライブラリを使う

NumPyのような数値計算に特化したライブラリを使えば高速に数値計算できます。数値計算に限らず、特定の計算に対して最適化されたライブラリがあります。CuPyは、CUDAを使ってGPUによる計算をPythonから簡単に実行できるようにしてくれます。

例8: NumPy

NumPyを使うと行列やベクトルの計算が高速化できます。高速化できるだけでなく、コードが簡略になってわかりやすくなります。ここでは、100×1000の行列をイメージして100000個の要素からなるリストの各要素を足しています。

In [1]: import numpy as np

In [2]: %%timeit
   ...: X = range(100000)
   ...: Y = range(100000)
   ...: Z = [x + y for x, y in zip(X, Y)]
13.7 ms ± 140 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [3]: %%timeit
   ...: X = np.arange(100000)
   ...: Y = np.arange(100000)
   ...: Z = X + Y
416 μs ± 2.33 μs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

方式	実行時間	備考
リストで計算	13.7 ms ± 140 μs
numpyで計算	416 μs ± 2.33 μs	単位がマイクロなのでミリにすると1/1000

NumPyのほうが圧倒的に早いことがわかります。リストでは、要素の型やリストのメソッドが変わってしまうことを考慮しますが、NumPyでは型が固定されているのとBLASなどのライブラリを使えるため高速化できます。

例9: pickleとcPickle

ライブラリが何で実装されているかでも、速度に差ができます。まもなくサポートが終了するPython 2系ではpickle化にはpickleとcPickleという二つのライブラリがありました。どちらを使うかで実行時間に結構な差が出ます。Python 3系では、cPickleは_pickleライブラリという名前に代わってpickleをインポートしたときにcPickleが利用可能であれば内部的に呼び出されるようになりました。

In [1]: import pickle
In [2]: import cPickle
In [3]: l = range(1000000)

In [4]: %%timeit
   ...: with open("pickle.pkl", "wb") as f:
   ...:     pickle.dump(l, f)
1 loops, best of 3: 3.75 s per loop

In [5]: %%timeit
   ...: with open("cPickle.pkl", "wb") as f:
   ...:     cPickle.dump(l, f)
1 loops, best of 3: 376 ms per loop

方式	実行時間	備考
pickleでシリアライズ	3.75 s
cPickleでシリアライズ	376 ms	単位がミリなのでミリを取ると1/1000

Python 2系のIPythonなので表示が他と違いますが、10倍くらいの実行時間比ですね。

2-2. ライブラリの環境変数やコンパイル条件を見直す

最近のCPUにはいろいろな高速化機能があります。高速化機能自身が有効になっているか、高速化機能をうまく使えるライブラリを呼んでいるかで、実行時間に差ができます。下記のページに解説があります。

• Numpyに使われるBLASによって計算速度が変わるらしい【Python】 - In-slico Notebook

3. ライブラリを作る

すでにPythonライブラリがあればインストールして使うだけでいいのですが、やりたいことに対応するPythonライブラリが必ずしもあるとは限りません。また、Pythonで書いたのではどうしても解消できない無駄な処理も結構あります。それでも高速化したい場合は、下記のいずれかの手法をとることになります。
この章では速度の比較を省略しますが、The Performance of Python, Cython and C on a Vector — Cython def, cdef and cpdef functions 0.1.0 documentationによると最大で100倍程度速くなることもあるようです。
標準ライブラリの例で挙げた例9: pickleとcPickleでは、10倍速くなっていました。

• 3-1. C言語で処理を実装し、ctypesで呼び出す
• 3-2. C言語でPythonライブラリを作る
• 3-3. Boost.Python(C++のライブラリ)を使う
• 3-4. Cython を使う

3-1. C言語で処理を実装しctypesで呼び出す

Pythonには、WindowsのdllファイルやLinuxのsoファイルからライブラリを読み込んで、ライブラリ内の関数を実行する機能(ctypes)が標準ライブラリあります。Pythonで書くと遅い処理を高速に実行する実装がすでにあるけれど、Pythonから呼び出せるようになっていない場合に使うことができます。

例10: ctypes

Pythonのmathライブラリには、立方根を求めるcbrt関数はありませんが、libmには定義されています。これを呼び出すには下記のようにします。

In [1]: from ctypes import cdll, c_double
In [2]: libm = cdll.LoadLibrary("libm.so.6")
In [3]: libm.cbrt.restype = c_double
In [4]: libm.cbrt.argtypes = (c_double,)
In [5]: libm.cbrt(8.0)
Out[5]: 2.0

この例では嬉しさはわかりませんが、簡単に呼べることだけはおわかりいただけたかと思います。Python側でforを回すと遅いので、forで回す処理も実行してくれるような関数を呼び出せると高速化できます。

3-2. C言語でPythonライブラリを作る

PythonのC拡張を使うと、C言語やC++言語を使ってPythonから呼び出せるライブラリを作ることができます。PythonはそもそもC/C++で作られたライブラリのラッパみたいなものなので、ラッパに呼び出される側を作ろうということです。

例11: C言語でPythonから呼び出せる足し算関数を実装する

C拡張で足し算関数を作ってみます。まずは、C言語で下記のソースコードを書きます。

samplemodule.c

#include <Python.h>

static PyObject * sample_add(PyObject *self, PyObject *args) {
    int x, y, z;

    if (!PyArg_ParseTuple(args, "ii", &x, &y)) {
        return NULL;
    }

    z = x + y;
    return PyLong_FromLong(z);
}

static PyObject *SampleError;

static PyMethodDef SampleMethods[] = {
    {"add",  sample_add, METH_VARARGS, "Sum x and y then return the sum."},
    {NULL, NULL, 0, NULL}
};

static struct PyModuleDef samplemodule = {
    PyModuleDef_HEAD_INIT, "sample", NULL,  -1, SampleMethods
};

PyMODINIT_FUNC PyInit_sample(void) {
    PyObject *m;

    m = PyModule_Create(&samplemodule);
    if (m == NULL) {
        return NULL;
    }

    SampleError = PyErr_NewException("sample.error", NULL, NULL);
    Py_XINCREF(SampleError);
    if (PyModule_AddObject(m, "error", SampleError) < 0) {
        Py_XDECREF(SampleError);
        Py_CLEAR(SampleError);
        Py_DECREF(m);
        return NULL;
    }

    return m;
}

Pythonのヘッダファイルを指定して、gccでコンパイルします。

$ gcc -I`python -c 'from distutils.sysconfig import *; print(get_python_inc())'` -DPIC -shared -fPIC -o sample.so samplemodule.c

sample.soが出来上がるので、Pythonインタプリタ(IPython)を起動して読み込んでみます。

In [1]: import sample
In [2]: sample.add(1, 2)
Out[2]: 3

3-3. Boost.Python(C++のライブラリ)を使う

Boost.Pythonを使うと、少ないコードでPythonライブラリを実装できます。Pythonのバージョン差異もあまり気にしなくてよくなります。その代わり、Boostライブラリに依存してしまうため、Boostライブラリがない環境ではPythonライブラリが読み込みません。Boost.Pythonを使って作られたライブラリは、実装の方法にもよりますがC言語で実装した場合と同じくらい高速です。

例12: BoostでPythonから呼び出せる足し算関数を実装する

Boost.Pythonで足し算関数を作ってみます。まずは、C++言語で下記のソースコードを書きます。たったこれだけです。

#include <boost/python.hpp>

int add(int x, int y) {
    return x + y;
}

BOOST_PYTHON_MODULE(sample) {
    using namespace boost::python;
    def("add", &add);
}

PythonのヘッダファイルやBoost.Pythonを指定して、g++でコンパイルします。

$ g++ -I`python -c 'from distutils.sysconfig import *; print(get_python_inc())'` -lboost_python -DPIC -shared -fPIC -o sample.so sample.cpp

sample.soが出来上がるので、Pythonインタプリタ(IPython)を起動して読み込んでみます。

In [1]: import sample
In [2]: sample.add(1, 2)
Out[2]: 3

C言語で一から書くのに比べてとてもコード量が短くなりました。素敵ですね。

3-4. Cythonを使う

Cythonを使えば、Pythonをちょっと改造した言語でソースコードを書いて、C言語で書いたものと同じくらい高速なライブラリを生成することができます。手順は、Pythonライクな言語でpyxファイルを作成し、C言語のソースコードを生成し、それをコンパイルするという流れになります。

例13: Cythonでフィボナッチ関数を実装する

フィボナッチ数列を計算する関数をCythonで作ってみます。まずは、pyxファイルを作成します。ちょっと型の情報があるくらいで、ほぼPythonと同じ文法です。

fib.pyx

def fib(int n):
    return n if n <= 1 else fib(n-2) + fib(n-1)

cythonコマンドでpyxファイルをC言語のソースコードに変換します。そして、gccでコンパイルします。

$ cython fib.pyx
$ gcc -I`python -c 'from distutils.sysconfig import *; print(get_python_inc())'` -DPIC -shared -fPIC -o fib.so fib.c

fib.soが出来上がるので、Pythonインタプリタ(IPython)を起動して読み込んでみます。

In [1]: from fib import fib

In [2]: %%timeit
   ...: fib(30)
304 ns ± 2.53 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Pythonですべて書いた場合が、「448 ms ± 4.22 ms」だったのでかなり改善されました。

4. バイトコードを最適化する

ここまでは、C言語でライブラリを作成して高速化していました。ライブラリを作成するにはC言語やCythonによるPythonを拡張した言語の知識が必要で、Python以外の言語を学ぶ必要がありました。しかし、新しい言語を学ぶのはなかなか大変です。ここでは既存のPythonプログラムをできるだけそのままで拡張できる下記の手法を紹介します。

• 4-1. Numbaを使う
• 4-2. PyPyを使う

4-1. Numbaを使う

NumbaはLLVMを使ってLLRM IRからバイトコードを生成して高速化します。Pythonスクリプトが実行されるまでにできるもの - Qiitaにあるように、PythonはVM型のスクリプト言語で中間命令(バイトコード)を愚直に実行することで処理を実現します。

本家サイトのガイドによると、バイトコードを最適化するだけでなくマシン命令を生成し関数呼び出しを置き換えるようです。すごいですね...。

例14: Numbaのjitデコレータ

In [1]: @jit
   ...: def fib(n):
   ...:     return n if n <= 1 else fib(n-2) + fib(n-1)
In [9]: %%timeit
   ...: fib(30)
12.6 ms ± 187 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

4-2. PyPyを使う

PyPyは、Pythonで書かれたPython処理系です。 RPythonという、Pythonより少し機能が制限されていて最適化がしやすいPythonが動作します。 RPythonで実装されており、Python2.7とPython3.6と互換性があります。Python compatibility - PyPyによるとDjangoやFlaskといった著名なライブラリは動作確認しているとのことですし、PyPy Speedによると実行速度もなかなか優秀なようです。

※ コメントに基づき一部文言を修正しました。

最後に

この記事では下記の高速化手法を紹介しました。

1. 言語仕様・標準ライブラリの範疇でスクリプトを書き直す
   • 1-1. Pythonスクリプトの書き方を見直す
   • 1-2. アルゴリズムとデータ構造を工夫する
   • 1-3. キャッシュを活用する
   • 1-4. 並列化する
2. ライブラリを使う
   • 2-1. ライブラリを使う
   • 2-2. ライブラリの環境変数やコンパイル条件を見直す
3. ライブラリを作る
   • 3-1. C言語で処理を実装し、ctypesで呼び出す
   • 3-2. C言語でPythonライブラリを作る
   • 3-3. Boost.Python(C++のライブラリ)を使う
   • 3-4. Cython を使う
4. バイトコードを最適化する
   • 4-1. Numbaを使う
   • 4-2. PyPyを使う

遅いと感じた処理への対応としてどの手法が適切かは時と場合によります。いろいろな選択肢を考慮したうえで、最適な手法を適用できると素敵ですね。

フィボナッチ数列の例ばかり出していますが、フィボナッチ数列を求めるのがアプリケーションの一般的なタスクではありません。高速化したい処理によってはNumbaよりCythonのほうが早いこともあるでしょう。
今回フィボナッチ数列を求めるのに再起を使っていますが、そもそも再起を除去すればもっと高速になりますね...。

皆様のQuality of Python Lifeが素晴らしいものになりますように。

参考

この記事を書くにあたって下記の記事を参考にしました。

• Python言語仕様
• Python標準ライブラリ
• Numpyに使われるBLASによって計算速度が変わるらしい【Python】 - In-slico Notebook

なお、私がこれまでPythonを学ぶにあたっては、上記以外の素敵な記事や書籍にお世話になっています。ここで紹介しきれないことを大変申し訳なく思っています。素晴らしい情報を公開・出版してくださり、ありがとうございます。その素晴らしい情報が、これからPythonを学ぶ方々の役に立つと信じています。