Cythonで内部的にC++のvector、unordered_mapを用いて処理を高速化する

概要

Cythonを用いると、Pythonを事前に等価なC/C++コードにコンパイルして利用することができます。Pythonの文法はほぼ全てサポートされており、既存のPythonコードをそのままCythonでコンパイルするだけで、数十％の実行速度が向上するとのことです。

Cythonの面白い点の一つは、CやC++のデータ型を直接Python(Cython)コードから利用できるようになる点です。

今回は、Pythonのdictの代わりに、C++のunordered_map、listの代わりにvectorをCythonコードから直接利用してみます。

実験

それぞれ、配列としてlistとdict、連想配列としてvectorとunordered_mapを使用して、100万回ずつintのキー配列を生成し、それらをキーとして連想配列に代入及び参照することで、パフォーマンスを比較してみます。

Cythonコードでは、.pyの代わりに.pyxを用いるため、ファイル名はcython_stl_experiment.pyxとなっています。

cython_cpp_experiment.pyx

# distutils: language=c++
# -*- coding: utf-8 -*-

import time
from libcpp.vector cimport vector
from unordered_map cimport unordered_map


cdef vector[int] cpp_keys = [k for k in range(1000000)]
keys = [k for k in range(1000000)]

cdef unordered_map[int, bint] cpp_dict
py_dict = {}


cpdef test_python_dict_set():
    for key in keys:
        py_dict[key] = True


cpdef test_python_dict_lookup():
    for key in keys:
        assert py_dict[key] == True


cpdef test_cpp_umap_set():
    cdef int key
    for key in cpp_keys:
        cpp_dict[key] = True


cpdef test_cpp_umap_lookup():
    for key in cpp_keys:
        assert cpp_dict[key] == True


def run():
    start = time.clock()
    test_python_dict_set()
    print 'test_python_dict_set:', time.clock() - start

    start = time.clock()
    test_python_dict_lookup()
    print 'test_python_dict_lookup:', time.clock() - start

    start = time.clock()
    test_cpp_umap_set()
    print 'test_cpp_umap_set:', time.clock() - start

    start = time.clock()
    test_cpp_umap_lookup()
    print 'test_cpp_umap_lookup:', time.clock() - start

上記コードを実行してみます。

In [1]: import cython_cpp_experiment
In [2]: cython_cpp_experiment.run()
test_python_dict_set: 0.116818
test_python_dict_lookup: 0.064986
test_cpp_umap_set: 0.094401
test_cpp_umap_lookup: 0.01363

連想配列への代入時間は2割弱程度の変化しかないものの、ルックアップ処理は約5倍程度高速化できました。

さいごに

Cythonでは、文字列(バイト)型とstd::string、listとstd::vectorなどをコンテクストに応じて自動的に変換してくれる機能が実装されてきており、比較的Python的な記述を保ったまま、C++のデータ型を直接使用することが出来たりして、とても便利です。

上記のコードでも、vectorをfor … in …でPython的なsyntaxで扱っています（内部的にはC++のイテレータが生成されて処理されます)。

参考:
Using C++ in Cython / Standard library: http://docs.cython.org/src/userguide/wrapping_CPlusPlus.html#standard-library

Cでエクステンション書けばいいんじゃない、とか、ctypes使えばいいんじゃない、という声も聞こえてきそうですが、Pythonで繰り返しなどの一部のコードのみ高速化できるCythonは、いろいろ利用しどころがあるのではないかと思います。

また、今回使用したコードはこちらにあります。
https://github.com/ikuyamada/cython-cpp-experiment