Гибридизация векторизации Numpy и простого Python

Question

У меня есть двумерный ndarray, строки которого нужно отсканировать, чтобы проверить, равен ли какой-либо один другому.

Моя первая попытка действительно работает, но я чувствую, что это не оптимальный путь. Требуется время, когда число строк в матрице приближается к 1000.

Мой код следующий. X - это вышеупомянутый массив, Y также является двумерным ndarray.

for i in range(X.shape[0]-1):
    for j in range(i+1,X.shape[0]):
        if (np.all( (X[i,:] == X[j,:] ), axis = 0 )):
            Y[j,:] = Y[i,:]
        #endif
    #enddo
#enddo

Я знаю, что вложенный цикл занимает много времени и его следует избегать, но я не смог найти альтернативу. Понимание списка кажется мне неуместным в том смысле, что нет необходимости сохранять элементы.

Тот факт, что ядром процедуры является операция присваивания Y[j,:] = Y[i,:], которая зависит от индекса , привела бы меня к исключению решения, подобного пониманию списка.

Тогда вопрос : есть ли более эффективный способ кодирования такого поиска, использующий numpy векторизацию?

Answer 1

Подход # 1

Мы могли бы использовать представления строк, чтобы получить попарные совпадения.Затем запустите цикл и назначьте их в Y.Идея состоит в том, чтобы минимизировать работу после запуска цикла.Учитывая, что может быть более одного индекса, совпадающего с другими индексами, будет сложно предложить чисто векторизованный метод.Реализация будет выглядеть примерно так -

# https://stackoverflow.com/a/44999009/ @Divakar
def view1D(a): # a is array
    a = np.ascontiguousarray(a)
    void_dt = np.dtype((np.void, a.dtype.itemsize * a.shape[1]))
    return a.view(void_dt).ravel()

# Get 1D view
a1D = view1D(a)

# Perform broadcasting to get outer equality match
mask = a1D[:,None]==a1D

# Get indices of pairwise matches
n = len(mask)
mask[np.tri(n, dtype=bool)] = 0
idx = np.argwhere(mask)

# Run loop to assign equal rows in Y
for (i,j) in zip(idx[:,0],idx[:,1]):
    Y[j] = Y[i]

Альтернатива # 1: использовать маску для прямого присваивания

Так, с mask, напрямую присваивайте строки в Y, вот так-

for i,m in enumerate(mask):
    if m.any():
        Y[m] = Y[i]

Это было бы полезно, если имеется много совпадений.

Альтернатива # 2: Использовать уменьшенную маску

Если между двумя строками существует более одной общей строки., мы могли бы хотеть уменьшить те, чтобы все они были связаны с первыми встречающимися.Следовательно, мы можем сгенерировать уменьшенную маску и использовать ее вместо более ранней mask -

mask0 = np.zeros_like(mask)
mask0[mask.argmax(0), np.arange(len(mask))] = 1
np.fill_diagonal(mask0,0)

Затем используйте mask0 вместо mask и назначьте.

---

Подход № 2

Другой метод будет начинаться с метода представления 1D и использовать метод на основе сортировки для настройки парно совпадающих индексов, например: *

sidx = a1D.argsort() # a1D from earlier approach
b = a1D[sidx]
m0 = b[:-1] == b[1:]
m1 = np.r_[False,m0,False]
idx = np.flatnonzero(m1[:-1]!=m1[1:]).reshape(-1,2)
for (i,j) in idx:
    row0,row1 = sidx[i],sidx[i+1:j+1]
    Y[row1] = Y[row0]

Answer 2

См. Следующий пример: В качестве иллюстрации рассмотрим одномерный вектор True и False, для которого вы хотите посчитать количество переходов «False to True» в последовательности:

np.random.seed(444)
x = np.random.choice([False, True], size=100000)

В цикле for Python одним из способов сделать это было бы попарно оценить значение истинности каждого элемента в последовательности вместе с элементом, который идет сразу после него:

def count_transitions(x) -> int:
  count = 0
  for i, j in zip(x[:-1], x[1:]):
     if j and not i:
        count += 1
  return count

count_transitions(x)

В векторизованной форме нет явного цикла for или прямой ссылки на отдельные элементы:

np.count_nonzero(x[:-1] < x[1:])

Как эти две эквивалентные функции сравниваются с точки зрения производительности? В этом конкретном случае векторизованный вызов NumPy выигрывает примерно в 70 раз

https://realpython.com/numpy-array-programming/

Answer 3

Я нахожусь на моем телефоне, поэтому я не могу проверить это, но я думаю, что это будет работать

mask = np.all(X[:, None] == X[None], axis=-1)
ind1, ind2 = np.nonzero(mask)
ind1, ind2 = ind1[ind1 < ind2], ind2[ind1 < ind2]
Y[ind2] = Y[ind1]