2

私は2つの配列を持っています。これは次のようになります。

X = np.array([ 157,  262,  368,  472,  577,  682,  786,  891,  996, 1100, 1204,
       1310, 1415, 1520, 1625, 1731, 1879])

Y = np.array([  30,  135,  240,  345,  450,  555,  660,  765,  870,  975, 1080,
       1185, 1290, 1395, 1500, 1605])

アレイは次のようになります。

  • 値を最初から昇順で並べ替えます。
  • 時々不均等な長さである。

Zこれら2つを以下に基づいて新しい配列にインターリーブしたいと思います。

  • 各要素は1回のみ使用できます
  • すべての要素を使用する必要はありません
  • に値の差が小さい要素が他になく、値の距離が。より小さい要素がない要素がある場合にのみ、要素をXi含めることができます。（同じルールがの要素に適用されます。）ZYjYYabs(Xi - Yj)XYjabs(Xi - Yj)Y

ネストされたforループの束でこれを実行できることはわかりますが、これを実行するためのよりスマートで適切な方法があるかどうか疑問に思います。

（私が質問したところ、教科書から切り取ったように聞こえます。そうではありません。しかし、それは古典的な並べ替え関数である可能性がありますが、生物学者としての私にとっては...私が言えるのは効率的で、きちんとした方法でそれを解決する方法として私は途方に暮れています。）

編集：あまりきれいな例ではありません

new_list = list()
for i in X:
    delta_i = np.abs(Y - i)
    delta_reciprocal = np.abs(X - Y[delta_i.argmin()])
    if delta_i.min() == delta_reciprocal.min():
        new_list += sorted([Y[delta_i.argmin()],
        X[delta_reciprocal.argmin()]])
Z = np.array(new_list)

それがすべての基準を満たしているかどうかさえ完全にはわかりませんが、古いコードを書き直すと、たった1つのループになりました...それでももっと良い方法があるはずです！

4

2 に答える 2

5

この例の解決策を考えてみましょう。

In [1]: import numpy as np

In [5]: X = np.array([1879, 1731])

In [6]: Y = np.array([1481, 1691, 1586, 1796])

X内の値と内の値の間のすべての距離を次のYように計算できます。

In [7]: dist = np.abs(np.subtract.outer(X,Y))

In [8]: dist
Out[8]: 
array([[398, 188, 293,  83],
       [250,  40, 145,  65]])

行は値に対応しX、列は値に対応しYます。

Xの要素に最も近い値を見つけるには、 行列の列の最小値に対応する をY探します。各列は特定の に対応するため、列の最小距離は、いくつかのと特定の の間の最小に対応します。XdistYXY

視覚的に言えば、探しているのは、それらが含まれる行と列の両方の最小値distである値です。それらを「行-列の最小値」と呼びましょう。

上記のdist配列では、40 が行と列の最小値です。65 は列の最小値ですが、行の列の最小値ではありません。

各列について、次の方法で列を最小化する X-index を見つけることができます。

In [6]: idx1 = np.argmin(dist, axis = 0)

In [7]: idx1
Out[7]: array([1, 1, 1, 1])

同様に、各行について、次の方法で Y インデックスを見つけることができます。

In [8]: idx2 = np.argmin(dist, axis = 1)

In [9]: idx2
Out[9]: array([3, 1])

ここで、この例を少し忘れて、次のidx1ようになったとします。

        0,1,2,3,4,5   # the index value 
idx1 = (_,_,_,_,_,2,...)

これは、5 列目で、2 行目に最小値があることを示しています。

次に、行 2、列 5 が行と列の最小値に対応する場合、次のidx2 ようになります。

        0,1,2        # index value
idx2 = (_,_,5,...)

この関係を NumPy で次のように表現できます。

idx1[idx2] == np.arange(len(X))
idx2[idx1] == np.arange(len(Y))

したがって、行と列の最小値に対応する X、Y の値は次のとおりです。

X[idx1[idx2] == np.arange(len(X))]

と

Y[idx2[idx1] == np.arange(len(Y))]

import numpy as np
tests = [
    (np.array([1879, 1731]),
     np.array([1481, 1691, 1586, 1806])), 
    (np.array([1879, 1731]),
     np.array([1481, 1691, 1586, 1796])),
    (np.array([ 157,  262,  368,  472,  577,  682,  786,  891,  996, 1100, 1204]),
     np.array([  30,  135,  240,  345,  450,  555,  660,  765,  870,  975])),
    (np.array([ 157, 262, 368, 472, 577, 682, 786, 891, 996, 1100, 1204, 1310,
                1415, 1520, 1625, 1731, 1879]),
     np.array([ 221, 326, 431, 536, 641, 746, 851, 956, 1061, 1166, 1271, 1376,
                1481, 1586, 1691, 1796]))]

def find_close(X,Y):
    new_list = list()
    for i in X:
        delta_i = np.abs(Y - i)
        # print(delta_i)
        delta_reciprocal = np.abs(X - Y[delta_i.argmin()])
        if delta_i.min() == delta_reciprocal.min():
            new_list += sorted([Y[delta_i.argmin()],
                                X[delta_reciprocal.argmin()]])
    Z = np.array(new_list)
    return Z

def alt_find_close(X,Y):
    dist = np.abs(np.subtract.outer(X,Y))
    idx1 = np.argmin(dist, axis = 0)
    idx2 = np.argmin(dist, axis = 1)
    Z = np.r_[X[idx1[idx2] == np.arange(len(X))], Y[idx2[idx1] == np.arange(len(Y))]]
    return Z

for X, Y in tests:
    assert np.allclose(sorted(find_close(X,Y)), sorted(alt_find_close(X,Y)))

Timeit の結果:

% python -mtimeit -s'import test' 'test.find_close(test.X, test.Y)'
1000 loops, best of 3: 454 usec per loop
% python -mtimeit -s'import test' 'test.alt_find_close(test.X, test.Y)'
10000 loops, best of 3: 40.6 usec per loop

Soalt_find_closeは よりも大幅に高速ですfind_close。

于 2012-12-11T15:57:59.690 に答える
2

使用したいと思うかもしれませんscipy.spatial.cKDTree（numpysを使用して自分でそのようなものを構築できますが、searchsorted等距離の問題をより詳細に制御しない限り、あまり意味がありません）。

ただし、一般的には注意が必要です。あなたの例は整数配列であり、見つかった出現に応じて問題が発生する可能性があります（argminは常に最初のものを見つけるため、問題ではないかもしれませんが、距離が等しい場合はポイントを削除できます）。

import numpy as np
from scipy.spatial import cKDTree

def find_close_fast(X, Y):
    kX = cKDTree(X[:,None]) # needs to be 2D
    kY = cKDTree(Y[:,None])

    nearest_X = kX.query(Y[:,None], p=1)[1] # might as well use 1-norm

    # Which Y corresponds the other way around?
    nearest_Y = kY.query(X[nearest_X][:,None], p=1)[1]

    w = nearest_Y == np.arange(len(Y))
    result = np.concatenate((X[nearest_X[w]], Y[w]))
    return result

配列が大きくなった場合 (おそらくそれぞれ数百程度)、これははるかに高速になります。例えば：

In [121]: X = np.random.random(5000)

In [122]: Y = np.random.random(5000)

In [123]: %timeit alt_find_close(X, Y)
1 loops, best of 3: 1.03 s per loop

In [124]: %timeit find_close_fast(X, Y)
10 loops, best of 3: 23.3 ms per loop

In [125]: np.all(np.sort(find_close_fast(X,Y)) == np.sort(alt_find_close(X, Y))) 
Out[125]: True

ただし、ここでは理由により浮動小数点数を使用しました。距離が等しい場合、結果は保証されません。並べ替えは異なりますが、正確な理由を理解しようとはしませんでした。

編集:実際には、両方の配列を 1 つに並べ替えて (どちらがどのクラスに属しているかを覚えておいてください)、そこから異なるクラスの 2 つが隣り合っている場所を確認することもできます。また、ポイントに他のクラスの隣接ポイントが 2 つある場合は、近い方を手動で選択します。それはおそらくさらに高速で、numpy のみを使用します。

于 2012-12-11T22:21:15.947 に答える