5

私はアルゴリズムにPythonのネイティブbignumを使用しており、C++に変換して高速化することにしました。ロングロングを使用した場合、C ++はPythonよりも約100倍高速でしたが、C ++でGMPバインディングを使用した場合、Pythonよりもわずか10倍高速でした（ロングロングに適合する同じケースの場合）。

多数の小さな追加を行うためのより良いbignum実装はありますか？たとえば、大きな数Nがあり、小さな+ 1、+ 21、+ 1などをたくさん追加し、ときどき別の大きな数Mを追加しますか？

4

3 に答える 3

2

GMP ライブラリ自体には、MPZ ルーチンへの高速な短整数の追加があります。

void mpz_add_ui (mpz_t rop, mpz_t op1, unsigned long int op2)

gmpy がそれを使用しているかどうかはわかりませんが、使用している場合は、通常の python int を mpz に追加するのに対して、mpz を mpz に追加して、より速いかどうかを確認してください。

編集

ベンチマークを少し試しましたが、違いはありませんでした

$ python -m timeit -c 'from gmpy import mpz
> a=mpz(10**1000)' 'a+1'
100000 loops, best of 3: 5.4 usec per loop

$ python -m timeit -c 'from gmpy import mpz
a=mpz(10**1000); b=mpz(1)' 'a+b'
100000 loops, best of 3: 5.5 usec per loop

したがって、gmpyは使用しないと思いmpz_add_uiます。実際には、はるかに高速になると予想されます。

于 2009-12-02T07:48:04.007 に答える
0

プロファイリングを行いましたか？PythonおよびC++のアプリケーション全体。そのため、本当にその追加の速度が必要であることがわかります。

Python 3kを試してみてください。これで、任意の長さの整数が実装されます。

于 2009-12-02T07:51:30.130 に答える
0

(注: 私は GMPY の維持に協力しており、最新のリリースではかなりの数の最適化を実装しています。)

GMPY v1.11 はmpz_add_ui、mpz に小さな数を追加するときに使用します。また、GMPY の最新バージョンは、小さい数を処理する場合、以前のバージョンよりも約 25% 高速です。

With GMPY 1.04
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000)" "a+1"
10000000 loops, best of 3: 0.18 usec per loop
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000);b=gmpy.mpz(1)" "a+b"
10000000 loops, best of 3: 0.153 usec per loop

With GMPY 1.11
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000)" "a+1"
10000000 loops, best of 3: 0.127 usec per loop
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000);b=gmpy.mpz(1)" "a+b"
10000000 loops, best of 3: 0.148 usec per loop

Python int を long に変換して呼び出すmpz_add_ui方が、Python int を mpz に変換するよりも高速であるため、中程度のパフォーマンス上の利点があります。long long でネイティブ操作に対して GMP 関数を呼び出すと、パフォーマンスが 10 倍低下しても驚かないでしょう。

いくつかの小さな数を 1 つの長い長い数に累積し、それらを一度に大きな数に追加できますか?

于 2009-12-04T08:16:28.223 に答える