Самый быстрый способ найти показатели наивысшего значения в матрице итеративно и исключительно ⇐ Python

[Anonymous]

Я пытаюсь найти «лучшие хиты» в матрице сходства (то есть матрица MXN, где индекс вдоль каждой оси соответствует позиции ITH в векторе M и JTH Position в векторе N). Самый простой способ объяснить это - найти индексы самых высоких значений в матрице итеративно, исключая ранее выбранные ряды и столбцы. Это приводит к выбранным индексам MIN (M, N).import numpy as np
import pandas as pd

def pairwise_best_hit(sim):
xdim,ydim = np.meshgrid(np.arange(sim.shape[1]),np.arange(sim.shape[0]))
table = np.vstack((sim.ravel(),xdim.ravel(),ydim.ravel())).T
df = pd.DataFrame(table).rename(columns={0:'sim',1:'index2',2:'index1'}).sort_values('sim',ascending=False)
seq1_hits = []
seq2_hits = []
while len(df):
index1 = df.iloc[0]['index1']
index2 = df.iloc[0]['index2']
seq1_hits.append(index1)
seq2_hits.append(index2)
df = df[(df['index1']!=index1)&(df['index2']!=index2)]
return [seq1_hits,seq2_hits]
< /code>
и для матрицы < /p>
sim = np.array([[1,5,6,2],[7,10,3,4],[1,5,3,7]])
pairwise_best_hit(sim)
< /code>
возвращает < /p>
[[1, 2, 0], [1, 3, 2]]
< /code>

Проверка, что редактирование было бы лучшим способом одновременно ответить на все комментарии. Слегка настраивая ответы от Fastduckasted, Жюльен и Аксель Донат, мы имеем: < /p>
def original(sim):
xdim,ydim = np.meshgrid(np.arange(sim.shape[1]),np.arange(sim.shape[0]))
table = np.vstack((sim.ravel(),xdim.ravel(),ydim.ravel())).T
df = pd.DataFrame(table).rename(columns={0:'sim',1:'index2',2:'index1'}).sort_values('sim',ascending=False)
output_list = []
while len(df):
index1 = df.iloc[0]['index1']
index2 = df.iloc[0]['index2']
score = df.iloc[0]['sim']
output_list.append((int(index1),int(index2),score))
df = df[(df['index1']!=index1)&(df['index2']!=index2)]
return output_list

def lastduckstanding(input_matrix):
mat = input_matrix.copy()
idxs = np.argsort(mat, None)
output_list = []
hit_is_set = set()
hit_js_set = set()
num_entries = min(mat.shape[0], mat.shape[1])
for idx in reversed(idxs):
i, j = divmod(idx, mat.shape[1])
if i in hit_is_set or j in hit_js_set:
continue
hit_is_set.add(i)
hit_js_set.add(j)
output_list.append((i,j,mat[i,j]))
if len(output_list) == num_entries:
break
return output_list

def julien(matrix: np.ndarray):
out = []
copy = matrix.copy()
for _ in range(min(copy.shape)):
ij = np.unravel_index(copy.argmax(), copy.shape)
indeces_plus_score = (ij[0],ij[1],copy[ij[0],ij[1]])
out.append(indeces_plus_score)
copy[ij[0], :] = -np.inf
copy[:, ij[1]] = -np.inf
return out

def axeldonath(arr, indices):
"""Find the maximum value in a 2D array recursively."""
if not np.any(np.isfinite(arr)):
return indices

idx_max = np.argmax(arr)
idxs = np.unravel_index(idx_max, arr.shape)
indeces_plus_score = (idxs[0],idxs[1],arr[idxs[0],idxs[1]])
arr[idxs[0], :] = -np.inf
arr[:, idxs[1]] = -np.inf
indices.append(indeces_plus_score)
return axeldonath(arr, indices)

def axeldonath_wrapper(similarity):
testsim = similarity # NEED TO CREATE A COPY OF THE DATA!
return axeldonath(testsim,[])

def timing_test(S,functionlist):
for function in functionlist:
testsim = S['matrix']
print(function)
%timeit function(testsim)
< /code>
С следующими результатами времени: < /p>

293 ms ± 5.53 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

35.6 ms ± 174 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

7.88 ms ± 109 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
# NOT RELIABLE!
25.1 μs ± 126 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)


Подробнее здесь: https://stackoverflow.com/questions/795 ... nd-exclusi