5

Vantage Point Tree を Python で実装したいのですが、C++ で std::nth_element を使用しています。

したがって、Pythonまたはnumpyで同等の「nth_element」関数を見つけたいと思います。

nth_element は配列を半順序付けするだけで、O(N) であることに注意してください。

int the_array[10] = {4,5,7,3,6,0,1,2,9,8};
std::vector<int> the_v(the_array,the_array+10);
std::nth_element (the_v.begin()+0, the_v.begin()+5, the_v.begin()+10);

そして今、ベクトルは次のようになります。

3,0,2,1,4,5,6,7,9,8

そして、n番目の要素を取得したいだけでなく、リストの2つの部分[3,0,2,1,4]と[6,7,9,8]を再配置したいと考えています。

さらに、nth_element サポートは、2 つの要素を比較できる関数を受け入れます。たとえば、以下のように、ベクトルはベクトル op DataPoint であり、DistanceComparator 関数は 2 つのポイントの距離を the_v.begin() と比較します。

vector<DataPoint> the_v;
for(int n = 0; n < N; n++) the_v[n] = DataPoint(D, n, X + n * D);
std::nth_element (the_v.begin()+0, the_v.begin()+5, the_v.begin()+10,
    DistanceComparator(the_v.begin()));

編集：

私はbhuvan-venkateshの回答を使用し、テストするコードをいくつか書きました。

partition_timer = timeit.Timer("numpy.partition(a, 10000)",
    "import numpy;numpy.random.seed(2);"+
    "a = numpy.random.rand(10000000)")
print(partition_timer.timeit(10))

sort_timer = timeit.Timer("numpy.sort(a)",
    "import numpy;numpy.random.seed(2);"+
    "a = numpy.random.rand(10000000)")
print(sort_timer.timeit(10))

sorted_timer = timeit.Timer("sorted(a)",
    "import numpy;numpy.random.seed(2);"+
    "a = numpy.random.rand(10000000)")
print(sorted_timer.timeit(10))

そして結果：

2.2217168808
17.0386350155
281.301710844

そして、C++ コードを使用してさらにテストを行います。

しかし、問題があります。numpy を使用すると、常に新しい配列が返され、配列が巨大な場合に多くのメモリが浪費されます。どうすればそれを処理できますか。または、Python 用の C++ エクステンドを作成する必要があります。

EDIT2：

@bhuvan-venkateshパーティション機能をお勧めいただきありがとうございます。

以下のようなパーティションを使用します。

import numpy

@profile
def for_numpy():
    numpy.random.seed(2)
    a = numpy.random.rand(1e7)
    for i in range(100):
        a.partition(numpy.random.randint(1e6))

if __name__ == '__main__':
    for_numpy()

プロファイラーを次のように実行しました。

python -m memory_profiler profiler_test.py

結果は次のとおりです。

Line #    Mem usage    Increment   Line Contents
================================================
    25   23.613 MiB    0.000 MiB   @profile
    26                             def for_numpy():
    27   23.613 MiB    0.000 MiB       numpy.random.seed(2)
    28   99.934 MiB   76.320 MiB       a = numpy.random.rand(1e7)
    29  100.004 MiB    0.070 MiB       for i in range(100):
    30  100.004 MiB    0.000 MiB           a.partition(numpy.random.randint(1e6))

そして、次のように配列全体をコピーすることはありません: numpy.partition(a, 3)

結論: numpy.ndarray.partition は、私が見つけたいものです。

4

1 に答える 1

1

http://docs.scipy.org/doc/numpy/reference/generated/numpy.partition.html

numpy パーティションが 2 つの新しい配列を作成することを確認してください。つまり、多くの新しい配列をすばやく作成できます。それらは Python のリストよりも効率的ですが、c++ とまったく同じことを行うわけではありません。

正確な要素が必要な場合は、引き続き O(n) になるフィルター検索を行うことができます

array = np.array(...)
partition = np.partition(array, 5) # O(n)
element = np.where(partition==array[5]) # O(n)
left, right = partition[:element], partition[element+1:] # O(n)

したがって、新しいコードは遅くなりますが、それが python-y の方法です。

編集：

では、コンパレータが必要ですか？独自の小さな関数を書く以外に方法はありません-キーワードとして純粋なnumpyで-各numpy操作は高度に最適化されたcコードで実装されているため、python関数またはpythonラムダを渡すとnumpyが強制的に実行されます毎回オブジェクトレベルに移動して評価します。

numpy.vectorizeはオブジェクト レベルになりますが、最終的には独自のコードを記述する必要があります。より「最適化されたアルゴリズム」を作成したい場合、Rosetta コードには実装があります。(Pythonオブジェクトを使用すると、オブジェクトレベルのアクセスのためにcまたはnumpyコードよりもはるかに遅くなるため、引用符で囲みます)。速度が真の関心事であるが、python の読みやすさが必要な場合は、cython で拡張機能を作成することを検討してください。

于 2016-08-04T02:40:13.953 に答える