0

長さの異なる 2 つの大きなベクトル (~133000 値) があります。小さい値から大きい値までそれぞれソートされています。特定の許容範囲内で類似する値を見つけたい。これは私の解決策ですが、非常に遅いです。これをスピードアップする方法はありますか？

import numpy as np

for lv in range(np.size(vector1)):
    for lv_2 in range(np.size(vector2)):
        if np.abs(vector1[lv_2]-vector2[lv])<.02: 
            print(vector1[lv_2],vector2[lv],lv,lv_2)
            break
4

3 に答える 3

0

次のコードは、数値の密度に応じてパフォーマンスを大幅に向上させます。0〜100の間で均一にサンプリングされた1000個の乱数のセットを使用すると、実装の約30倍の速度で実行されます。

pos_1_start = 0

for i in range(np.size(vector1)):
    for j in range(pos1_start, np.size(vector2)):
        if np.abs(vector1[i] - vector2[j]) < .02:
            results1 += [(vector1[i], vector2[j], i, j)]
        else:
            if vector2[j] < vector1[i]:
                pos1_start += 1
            else:
                break

タイミング：

time new method: 0.112464904785
time old method: 3.59720897675

これは、次のスクリプトによって生成されます。

import random
import numpy as np
import time

# initialize the vectors to be compared
vector1 = [random.uniform(0, 40) for i in range(1000)]
vector2 = [random.uniform(0, 40) for i in range(1000)]

vector1.sort()
vector2.sort()

# the arrays that will contain the results for the first method
results1 = []

# the arrays that will contain the results for the second method
results2 = []

pos1_start = 0

t_start = time.time()
for i in range(np.size(vector1)):
    for j in range(pos1_start, np.size(vector2)):
        if np.abs(vector1[i] - vector2[j]) < .02:
            results1 += [(vector1[i], vector2[j], i, j)]
        else:
            if vector2[j] < vector1[i]:
                pos1_start += 1
            else:
                break

t1 = time.time() - t_start
print "time new method:", t1

t = time.time()
for lv1 in range(np.size(vector1)):
    for lv2 in range(np.size(vector2)):
        if np.abs(vector1[lv1]-vector2[lv2])<.02: 
            results2 += [(vector1[lv1], vector2[lv2], lv1, lv2)]
t2 = time.time() - t_start

print "time old method:", t2
# sort the results

results1.sort()
results2.sort()

print np.allclose(results1, results2)
于 2012-10-10T11:47:37.703 に答える
0

あなたのアルゴリズムは最適とはほど遠いものです。あまりにも多くの値を比較します。の特定の位置にいvector1て、現在の の値vector2がすでに0.02大きくなっているとします。の残りの部分を比較する理由は何vector2ですか?

次のようなものから始めます

pos1 = 0
pos2 = 0

ベクトル内のそれらの位置の値を比較します。差が大きすぎる場合は、小さい方のフォワードの位置をずらして再度確認してください。1 つのベクトルの最後に到達するまで続行します。

于 2012-10-10T08:58:57.200 に答える
0

テストしていませんが、次のように動作するはずです。アイデアは、ベクトルがソートされているという事実を利用することです

lv_1, lv_2 = 0,0
while lv_1 < len(vector1) and lv_2 < len(vector2):
  if np.abs(vector1[lv_2]-vector2[lv_1])<.02:
     print(vector1[lv_2],vector2[lv_1],lv_1,lv_2)
     lv_1 += 1
     lv_2 += 1
  elif vector1[lv_1] < vector2[lv_2]: lv_1 += 1
  else: lv_2 += 1
于 2012-10-10T09:00:16.190 に答える