1

次の類似性マトリックスがあるとします。

matrix = [[100.0, 66.666666666666671, 61.539999999999999, 59.260000000000005, 59.260000000000005, 82.61333333333333, 61.539999999999999, 61.539999999999999, 61.539999999999999, 78.259999999999991],
[66.666666666666671, 100.0, 91.306666666666672, 87.5, 87.5, 69.233333333333334, 91.306666666666672, 91.306666666666672, 91.306666666666672, 65.386666666666656],
[61.539999999999999, 91.306666666666672, 100.0, 88.0, 88.0, 70.373333333333335, 91.666666666666671, 91.666666666666671, 100.0, 66.666666666666671],
[59.260000000000005, 87.5, 88.0, 100.0, 84.620000000000005, 74.079999999999998, 95.833333333333329, 95.833333333333329, 88.0, 64.286666666666662],
[59.260000000000005, 87.5, 88.0, 84.620000000000005, 100.0, 67.859999999999999, 88.0, 88.0, 88.0, 64.286666666666662],
[82.61333333333333, 69.233333333333334, 70.373333333333335, 74.079999999999998, 67.859999999999999, 100.0, 76.926666666666662, 76.926666666666662, 76.926666666666662, 87.5],
[61.539999999999999, 91.306666666666672, 91.666666666666671, 95.833333333333329, 88.0, 76.926666666666662, 100.0, 100.0, 91.666666666666671, 66.666666666666671],
[61.539999999999999, 91.306666666666672, 91.666666666666671, 95.833333333333329, 88.0, 76.926666666666662, 100.0, 100.0, 91.666666666666671, 66.666666666666671],
[61.539999999999999, 91.306666666666672, 100.0, 88.0, 88.0, 76.926666666666662, 91.666666666666671, 91.666666666666671, 100.0, 66.666666666666671],
[78.259999999999991, 65.386666666666656, 66.666666666666671, 64.286666666666662, 64.286666666666662, 87.5, 66.666666666666671, 66.666666666666671, 66.666666666666671, 100.0]]

対角線上の値はすべて100.0に等しく、上三角は下三角に等しいことに注意してください。

対角線上にない5つの異なる最高値のインデックスを見つけたいです。

今のところ、私はこのブルートフォース攻撃を行います。

from collections import defaultdict
d = defaultdict(list)
for i in range(len(matrix)):
    for j in range(len(matrix[i])):
      d[matrix[i][j]].append((i,j))

for value in sorted(d.keys(), reverse=True)[1:6]:
    print value, d[value]

これは次のようになります。

95.8333333333 [(3, 6), (3, 7), (6, 3), (7, 3)]
91.6666666667 [(2, 6), (2, 7), (6, 2), (6, 8), (7, 2), (7, 8), (8, 6), (8, 7)]
91.3066666667 [(1, 2), (1, 6), (1, 7), (1, 8), (2, 1), (6, 1), (7, 1), (8, 1)]
88.0 [(2, 3), (2, 4), (3, 2), (3, 8), (4, 2), (4, 6), (4, 7), (4, 8), (6, 4), (7, 4), (8, 3), (8, 4)]
87.5 [(1, 3), (1, 4), (3, 1), (4, 1), (5, 9), (9, 5)]

しかし、これは非効率的です。なぜなら、マトリックス全体を調べながら、マトリックスの半分をトラバースするだけでよいからです。最高値の場合、インデックスと。95.8333333333だけを気にします。(3,6)(3,7)

おそらくnumpyを使用して、これを行うためのより効率的な方法はありますか？

4

2 に答える 2

1

Numpyは速くなります。

import numpy as np

m = np.array(matrix) * np.diag(len(matrix)) # set the upper triangle to zero
for top_value in sorted((np.unique(m)), reverse=True)[1:6]:
    print top_value, zip(*np.where(m == top_value))
于 2012-06-20T08:28:20.507 に答える
1 
from heapq import nlargest
from collections import defaultdict

d = defaultdict(list)

for i in xrange(len(matrix)):
    for j in xrange(i):
      d[matrix[i][j]].append((i, j))

for value, positions in nlargest(5, d.items(), key=lambda item: item[0]):
    print value, positions
  • rangeの代わりにxrangeを使用する
  • jをi-1にのみループします（i = 0の場合、内部ループは実行されません...）
  • 効率的に使用するために、リストを並べ替えないでください。ただし、ヒープデータ構造を使用するため、heapqからnlargestを使用してください。大きな行列の場合は重要です。
于 2012-06-20T08:29:20.460 に答える