備忘録 blog

Docker/Machine Learning/Linux

Python2を高速化するtips(続)

sharply.hatenablog.com

これの続き。

単純に高速なアルゴリズムを使う

例えば"ham"という文字列がある配列に含まれるか?という問いに対して、

some_list = ["spam", "ham", "eggs"]
if "ham" in some_list

というリスト検索ではO(log(n))ですが、RubyにおけるHashと同様のものがPythonでも辞書(Dictionaly)として提供されており、

some_dict = {"spam":1, "ham":1, "eggs":1}
if "apple" in some_dict

とすればO(1)になります。もちろんこれが使えるのには条件がありますが、これで数秒程度早くなりました。

並列計算する

python律速となっているのはだいたいfor文であり、このfor文の実行回数をいかに減らせるか、ということがポイントとなります。 並列計算には、スレッド並列化(メモリを共有する)とプロセス並列化(メモリを共有しない)の2種類があります。しかしCPythonの実装ではGIL(Global Interpreter Lock)というものがあるので、プロセス並列化ぐらいしかできません。

GILとは、並列実行したときに安全でないコード(例えばグローバル変数を書き換えるような、スレッドセーフでないコード:しばしばCのモジュールに存在する)を実行しないようにするために、そのコードを他のスレッドで呼ばれないようにする排他ロックのことで、pythonrubyといったインタプリタ言語では一般に1つのプロセスに対して1つのGILが存在する。

GILがない実装としてJPython(JAVAによる実装)やIronPython、PypyのSTM版があげられますが、ここでは措きます。

CPythonでプロセス並列化によって高速化するには、for文の区間を分割して部分和を並列で計算し、あとでその総和をとるという手段が用いられます。しかしCのopenMPのように動的にfor文の処理をスレッドに割り当てるといったことは標準では用意されていないので、自分で実装するなりする必要があります。

qiita.com

Boost.pythonを使う

結局pythonで計算させるには限界があるので、C++で書いたコードをコンパイルしたものを共有ライブラリとしてpython側から呼び出す実装にしてみましょう。

#define BOOST_PYTHON_STATIC_LIB
#include <boost/python.hpp>

static void image_putpixel(image &i, const boost::python::tuple &x, const boost::python::tuple &y){
  double point[2] = {boost::python::extract<double>(x[0]), boost::python::extract<double>(x[1])};
  uchar color[3] = {boost::python::extract<uchar>(y[0]), boost::python::extract<uchar>(y[1]),boost::python::extract<uchar>(y[2])};
  i.putpixel(point, color);
}

BOOST_PYTHON_MODULE(brush)
{
    using namespace boost::python;

    class_<image>("image")
        .def("show", &image::show)
        .def("brush", &image_brush)
        .def("putpixel", &image_putpixel)
        .def("load", &image::load)
        .def("get", &image::get);
}

上記でわかるように、C++のクラスをpythonのクラスにみなせたり、pythonのtupleを引数としてとるような関数を定義することができます。

コンパイルオプションは例えばUnix環境ではこんな感じ。

g++ -std=c++11 -O2 -I`python -c 'from distutils.sysconfig import *; print get_python_inc()'` -DPIC -fPIC -shared -o brush.so src/brush.cpp -lboost_python

-Iにインクルードパスを指定したいのですが、そのパスが異なるコンピュータ上でも共通に実行できるように、``でpythonを実行するコードを囲うことでそれをシェル上で評価した結果が返ってきます。

python側からは、soファイルを同じディレクトリに置いてファイル名でimportすればOKです。さらに、openMPで実装したC++のコードをpython側から呼び出すこともでき、さらに速度が上がる可能性もあります。

光学設計者の学習メモ: Boost.pythonでOpenMP