35


14

私の問題:STLマップとベクトルを使用して生のCで大きなデータセットを処理することはCythonを使用するよりかなり速い(そしてより少ないメモリフットプリントで)ことが多いことがわかった。

私は、このスピードのペナルティの一部はPythonのリストと辞書の使用によるものであり、Cythonで邪魔にならないデータ構造を使用するためのトリックがあるかもしれないと思います。 例えば、このページ(http://wiki.cython.org/tutorials/numpy)は、ND配列のサイズとタイプを事前定義することによって、Cythonでテンキー配列を非常に高速にする方法を示しています。

質問:リストや辞書と似たようなことをする方法はありますか? おおまかにいくつの要素、または(キー、値)のペアをそれらに含めることを期待していますか つまり、Cythonでリスト/辞書を(高速)データ構造に変換する慣用的な方法はありますか?*

そうでないなら、私はそれをCで書いてCythonのインポートでラップするだけでよいと思います。

5 回答


33


Cythonは現在テンプレートをサポートしており、いくつかのSTLコンテナの宣言が付属しています。

これが彼らが与える例です:

libcpp.vector cimportベクトルから

cdef vector [int] vect cdef int iの範囲(10)内のi:vect.push_back(i)の範囲内のi(10):print vect [i]


30


PythonでもCと同じような操作をすると、遅くなることがよくあります。 list`と dict`は実際には非常によく実装されていますが、Pythonオブジェクトを使うとたくさんのオーバーヘッドが生じます。これはCオブジェクトより抽象的で、実行時にもっと多くの検索が必要です。

ちなみに、 `std

vector`は` list`とほぼ同じ方法で実装されています。 しかし、 std :: map`は実際にはサイズが大きくなるにつれて多くの操作が dict`より遅くなるように実装されています。 それぞれ適切な大きさの例では、 dict`は std :: map`より遅いという定数の要素を克服し、実際には検索、挿入などの操作を行います。 もっと早く。

`std

map`と` std :: vector`を使いたいのであれば、何も邪魔をすることはありません。 Pythonに公開したい場合は、それらを自分でラップする必要があります。 この包装があなたが救いを望んでいた時間の全部または大部分を消費してもショックを受けないでください。 私はあなたのためにこれを自動にするツールを知りません。

オブジェクトの作成を詳細に制御するためのC API呼び出しがあります。 「少なくともこれだけの要素を使ってリストを作成する」と言うことはできますが、これはリストの作成および入力操作の全体的な複雑さを改善するものではありません。 あなたがあなたのリストを変更しようとしても、それは確かにそれほど後に変わることはありません。

私の一般的なアドバイスは

  • 固定サイズの配列が欲しい(リストのサイズを指定することについて話している)のであれば、実際には派手な配列のようなものが欲しいかもしれません。

  • 私はあなたがあなたのコードの_一般的な置き換えのために list`の上に std :: vector`を使うことからあなたが望むどんなスピードアップも得ようとしているのではないでしょうか。 あなたが舞台裏でそれを使用したいならば、それはあなたに満足のいくサイズとスペースの改善を与えるかもしれません(もちろん私は測定せずに知らないし、あなたもしません)。 ;))。

  • dict`は実際にその仕事を本当にうまくやっています。 私は間違いなく `std :: map`をベースにしたPython用の新しい汎用型を導入しようとは思わないでしょう。 `dict`がすでに持っているユーザー もう少し `std :: map`のように動作するものが欲しいのなら、おそらくデータベースを使うでしょう。 これは一般的に `dict`に保存したいもの(あるいはそのために list`に保存したいもの)が大きくなりすぎて快適にメモリに保存できなくなった場合に行います。 Pythonのstdlibには `sqlite3`があり、他のすべての主要なデータベース用のドライバがあります。


9


Cは、ベクトルとそれに入る要素の静的宣言のためだけではなく、テンプレート/総称を使用すると、ベクトルが特定の型の要素のみを含むことを指定するため、決定的に高速です。 3つの要素のタプルを持つベクトル。 Cythonはこの最後のことを行うことができず、それは自明ではないように思えます - どういうわけかコンパイル時に強制されなければならないでしょう(実行時の型検査はPythonが既にしていることです)。 そのため、Cythonでリストから何かをポップするときに、それがどんな型であるかを事前に知ることはできません。 これは、この点ではPythonインタプリタを迂回する方法がないことを意味し、それは私には数値以外のタスクに対するCythonの最も重大な欠点であるように思われます。

これを手動で解決する方法は、特定のタイプの要素またはキーと値の組み合わせに対して、cdefクラスを使ってpython list / dict(またはおそらくstd

vector)をサブクラス化することです。 これはテンプレートが生成しているコードと同じことになります。 結果のクラスをCythonコードで使用している限り、改善されるはずです。

データベースや配列を使用することは別の問題を解決するだけです。なぜならこれは任意のオブジェクトを(しかし特定の型、そしてできればcdefクラスを使って)コンテナに入れることです

そしてstd

mapはdictと比較してはいけません。 std :: mapはバランスのとれたツリーなのでソート順にキーを保持します。dictは別の問題を解決します。 より良い比較は口述とグーグルのハッシュテーブルでしょう。


2


Cythonの設定に適しているのであれば、Python用の標準の arrayモジュールを見てください。 私はCythonを使ったことがないので、よくわかりません。


1


ネイティブのPythonリストをCマップ/ベクトルの速度まで、あるいはそれに近い場所まで表示する方法はありません。 割り当てや型宣言とは何の関係もありませんが、インタプリタのオーバーヘッドを払います。 あなたが(numpy)言及した例はCの拡張であり、まさにこの理由でCで書かれています。