私は2つの疎な行列AとBを持っています.Aは120000 * 5000でBは30000 * 5000です。私は、Bの各行とAのすべての行との間のユークリッド距離を求め、次にBの選択行までの最短距離を持つAの5行を見つけ出す必要があります。メモリエラー。 Aの各行に対して、（x_b-x_a）^ 2を5000回計算し、それらを合計してsqrtを取得することは明らかです。このプロセスは11日のように非常に長い時間がかかります！私はこれをより効率的に行う方法はありますか？私はちょうどBの各列に最も低い距離で5行が必要です。2つの巨大なCSR行列の行間のユークリッド距離を求める
私はK-Nearest Neighborsを実装しており、Aは私のトレーニングセットであり、Bは私のテストセットです。
まあ、私はあなたがそのコードを「ベクトル化できる」かどうかわからないので、Pythonの代わりにネイティブコードで実行されます。 numpyとscipyをスピードアップするためのトリックは、常にそれを得ています。
1GHz CPUのネイティブコードでこのコードを実行することができ、クロックシークに1FFP命令を使用すると、10時間弱で実行されます。（5000 * 2 * 30000 * 120000）/ 1024 ** 3
これを1.5Ghz x 2 CPUの物理コアx 4ウェイSIMD命令に乗算+ acummulate（Intel AVX拡張、ほとんどのCPUで利用可能）その数字は1時間になるかもしれないが、中程度のコアi5マシンでは2 x 100％である。しかし、それはネイティブコードで完全なSIMD最適化を必要とするでしょう - あなたがこの道を行くことにしたならば、SOに関する更なる質問は、SIMDコーディングで手を濡らす人々の助けを得ることができます:-)） - 例えば、上記の10時間の図になるには、その部分だけが必要です。
今、...アルゴリズムの最適化と、物事のPythonの保持:-)
事実、あなたは完全に計算する必要はありませんすべて Aの行からの距離 - 5つの低い行のソートされたリストを保持するだけで済みます - そして、平方和の累積が5番目に近い行（これまでのところ）、その行の計算を中止するだけです。
あなたはそのためにPythonのheapq操作を使用することができます。全ての乗算の値の高価な検索や比較を避けるために
import heapq
import math
def get_closer_rows(b_row, a):
result = [(float("+inf"), None) * 5]
for i, a_row in enumerate(a):
distance_sq = 0
count = 0
for element_a, element_b in zip(a_row, b_row):
distance_sq += element_a * element_b
if not count % 64 and distance_sq > result[4][0]:
break
count += 1
else:
heapq.heappush(result, (distance, i))
result[:] = result[:5]
return [math.sqrt(r) for r in result]
closer_rows_to_b = []
for row in b:
closer_rows_to_b.append(get_closer_rows(row, a))
注AUXILIAR 『カウント』。 通常のPythonの代わりにpypyを使用してこのコードを実行することができれば、JITtingの利点を最大限に活用できると思います。純粋なPythonでコードを実行していると、/scipyベクトル化コード）。