Как эффективно сравнивать каждую пару строк в 2D-матрице?

Я работаю над подпрограммой, в которой мне нужно обработать каждую строку матрицы и найти, какие другие строки содержатся в текущей строке. Для иллюстрации того, когда строка содержит другую, рассмотрим матрицу 3x3, как показано ниже:

[[1, 0, 1], 

 [0, 1, 0], 

 [1, 0, 0]]

Здесь строка 1 содержит строку 3, поскольку каждый элемент в строке 1 больше или равен строке 3, но строка 1 не содержит строку 2.

Я придумал следующее решение, но оно очень медленное из-за цикла for (размер матрицы составляет около 6000x6000).

for i in range(no_of_rows):
    # Here Adj is the 2D matrix 
    contains = np.argwhere(np.all(Adj[i] >= Adj, axis = 1))

Не могли бы вы сообщить мне, возможно ли сделать это более эффективно?


python numpy numpy-ndarray vectorization array-broadcasting
person randomprime    schedule 01.05.2019    source источник
comment
Попробуйте начать с np.triu_indices и проверьте этот stackoverflow.com/questions/52690963/   -  person kvitaliy    schedule 01.05.2019
comment
Вы хотите признать, что каждый элемент содержит сам себя? Кроме того, вы пометили это broadcasting. Вы можете попробовать (a >= a[:, None]).all(-1), но это быстро взорвет вашу память большими массивами.   -  person user3483203    schedule 01.05.2019
comment
@kvitaliy Спасибо! Я уже посмотрел тот пост. В моем случае triu_indices приводят к действительно большим (размером 25715206) векторам R и C, и это занимает много времени.   -  person randomprime    schedule 01.05.2019
comment
@ user3483203 Спасибо! Слово «содержит» означает сравнение каждой строки с каждой другой строкой по элементам.   -  person randomprime    schedule 01.05.2019
comment
Да, поэтому первая строка по определению содержит первую строку. Вы хотите, чтобы они были включены?   -  person user3483203    schedule 01.05.2019
comment
@user3483203 user3483203 Да, включение сравнения строки с самой собой — это нормально, потому что на следующем этапе проблемы мне нужно обнулить строки, содержащиеся в текущей строке. В этом случае я могу просто пропустить обнуление текущей строки.   -  person randomprime    schedule 01.05.2019
comment
Что вы делаете с результатом. Каков желаемый результат для вашей базовой матрицы 3x3 выше?   -  person user3483203    schedule 01.05.2019
comment
@ user3483203 Также спасибо за решение для трансляции. Я только что попробовал, но, как вы сказали, это привело к проблемам с памятью с матрицей, с которой я работаю (размер 6000x6000).   -  person randomprime    schedule 01.05.2019
comment
@user3483203 user3483203 Для матрицы 3x3, поскольку строка 3 содержится в строке 1, на следующем шаге я установлю все элементы в строке 3 равными нулю. Чтобы дать больше контекста проблемы, предполагая, что строки представляют электростанции, а столбцы представляют потребителей, это шаг предварительной обработки, в котором говорится, что если есть какая-то электростанция x, которая покрывает всех потребителей, которые покрывает какая-то другая электростанция y и, возможно, больше, то станция y не требуется.   -  person randomprime    schedule 01.05.2019
comment
Таким образом, любая строка, которая содержится в другой, должна быть установлена ​​​​на 0?   -  person user3483203    schedule 01.05.2019
comment
@user3483203 user3483203 Да, верно!   -  person randomprime    schedule 01.05.2019

Ответы (2)


arrow_upward
1
arrow_downward

Из-за размера ваших матриц и требований вашей проблемы я думаю, что итерация неизбежна. Вы не можете использовать вещание, так как оно взорвет вашу память, поэтому вам нужно работать с существующим массивом построчно. Однако вы можете использовать numba и njit, чтобы значительно ускорить это по сравнению с подходом на чистом Python.

import numpy as np
from numba import njit


@njit
def zero_out_contained_rows(a):
    """
    Finds rows where all of the elements are
    equal or smaller than all corresponding
    elements of anothe row, and sets all
    values in the row to zero

    Parameters
    ----------
    a: ndarray
      The array to modify

    Returns
    -------
    The modified array

    Examples
    --------
    >>> zero_out_contained_rows(np.array([[1, 0, 1], [0, 1, 0], [1, 0, 0]]))
    array([[1, 0, 1],
            [0, 1, 0],
            [0, 0, 0]])
    """
    x, y = a.shape

    contained = np.zeros(x, dtype=np.bool_)

    for i in range(x):
        for j in range(x):
            if i != j and not contained[j]:
                equal = True
                for k in range(y):
                    if a[i, k] < a[j, k]:
                        equal = False
                        break
                contained[j] = equal

    a[contained] = 0

    return a

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

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

a = np.random.randint(0, 2, (6000, 6000))

%timeit zero_out_contained_rows(a)
1.19 s ± 1.87 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Я обновлю тайминги, как только ваша попытка завершится (в настоящее время ~ 10 минут).

person user3483203    schedule 01.05.2019

arrow_upward
0
arrow_downward

Если у вас матрица 6000x6000, то вам нужно (6000*6000 - 6000)/2 = 17997000 вычислений.

Вместо использования np.triu_indices вы можете попробовать использовать генератор для верхнего треугольника вашей матрицы - это должно уменьшить потребление памяти. Попробуй, может поможет..

def indxs(lst):
   for i1, el1 in enumerate(lst):
      for el2 in lst[i1:][1:]:
         yield (el1, el2)
person kvitaliy    schedule 01.05.2019