Как найти индексы ненулевых элементов в большой разреженной матрице?

Question

У меня есть две квадратные матрицы (a, b) размера порядка 100000 X 100000. Я должен взять разницу этих двух матриц (c = a-b). Результирующая матрица 'c' является разреженной матрицей. Я хочу найти индексы всех ненулевых элементов. Я должен сделать эту операцию много раз (> 100).

Самый простой способ - использовать два для циклов. Но это требует больших вычислительных ресурсов. Можете ли вы сказать мне какой-нибудь алгоритм или пакет / библиотеку, предпочтительно в R / python / c, чтобы сделать это как можно быстрее?

Answer 1

Поскольку у вас есть две плотные матрицы, двойной цикл for - это единственный вариант, который у вас есть. Вам вообще не нужен класс разреженных матриц, поскольку вы хотите знать только список индексов (i,j), для которых a[i,j] != b[i,j].

В таких языках, как R и Python, двойной цикл for будет работать плохо. Я, вероятно, написал бы это в нативном коде для двойного цикла for и добавил бы индексы к объекту списка. Но, без сомнения, мастера интерпретируемого кода (например, R, Python и т. Д.) Знают эффективные способы сделать это, не прибегая к нативному кодированию.

Answer 2

В R, если вы используете пакет Matrix и sparseMatrix для преобразования из списка координат в разреженную матрицу, вы можете преобразовать обратно в столбец 3 с помощью:

TmpX <- as(M, "dgTMatrix")
X3col <- matrix(c(TmpX@i, TmpX@j, TmpX@val), ncol = 3)

Это даст вам координаты и значения в разреженной матрице.

В зависимости от расположения ненулевых записей в A и B, вам может оказаться гораздо лучше работать со списком координат, чем с разреженным матричным представлением (между прочим, существуют десятки разреженных матричных представлений), так как вы можете напрямую использовать векторизованные операции вместо того, чтобы полагаться на свой разреженный матричный пакет для оптимальной работы. Я склонен чередовать использование COO или поддержку разреженных матриц на разных языках, в зависимости от того, как я получу самую быструю производительность для интересующего алгоритма.

---

Обновление 1: я не знал, что ваши две матрицы, A и B, плотные. Таким образом, самое простое решение для поиска ненулевых записей в C состоит в том, чтобы сначала просто не вычитать, а просто сравнить записи A и B. Логическое сравнение должно быть быстрее, чем вычитание. Сначала найдите записи A и B, где A != B, затем вычтите только эти записи. Далее вам просто нужно перейти от векторизации индексов в A и B к их (row, col) представлению. Это похоже на ind2sub и sub2ind Matlab - посмотрите на эту ссылку R для расчетов.

Answer 3

Я не рассчитал это, но самый простой код -

all.indices<- which (C>0, arr.ind=T)

Answer 4

Этот код занимает менее 0,1 с.

m <- matrix(rpois(1000000,0.01),ncol=1000)
m0 <- lapply(seq(NCOL(m)),function(x) which(m[,x] != 0))

EDIT: Для разреженных матриц любого размера (который подходит памяти).

DATA

library(data.table)

N <- 1e+5
n <- 1e+6

ta <- data.table(r=sample(seq(N), n,replace=TRUE),
                 c=sample(seq(N), n,replace=TRUE),
                 a=sample(1:20,n,replace=TRUE))
tb <- data.table(r=sample(seq(N), n,replace=TRUE),
                 c=sample(seq(N), n,replace=TRUE),
                 b=sample(1:20,n,replace=TRUE))
setkey(ta,r,c)
setkey(tb,r,c)

КОД

system.time(tw <- ta[tb][is.na(a)|is.na(b)|(a-b != 0),list(r=r,c=c)])

Answer 5

Вы можете использовать метод c.nonzero():

>>> from scipy.sparse import lil_eye
>>> c = lil_eye((4, 10)) # as an example
>>> c
<4x10 sparse matrix of type '<type 'numpy.float64'>'
        with 4 stored elements in LInked List format>
>>> c.nonzero()
(array([0, 1, 2, 3], dtype=int32), array([0, 1, 2, 3], dtype=int32))
>>> import numpy as np
>>> np.ascontiguousarray(c)
array([  (0, 0) 1.0
  (1, 1)        1.0
  (2, 2)        1.0
  (3, 3)        1.0], dtype=object)

Вам не нужно вычислять матрицу c, чтобы найти индексы ненулевых элементов в c = a - b;Вы могли бы сделать (a != b).nonzero():

>>> a = np.random.random_integers(2, size=(4,4))
>>> b = np.random.random_integers(2, size=(4,4))
>>> (a != b).nonzero()
(array([0, 0, 1, 1, 1, 2, 3]), array([1, 2, 1, 2, 3, 2, 0]))
>>> a - b
array([[ 0,  1,  1,  0],
       [ 0,  1, -1, -1],
       [ 0,  0,  1,  0],
       [-1,  0,  0,  0]])

Answer 6

посмотрите на numpy в нем есть все, о чем вы просите, и даже больше!

См. this для поддержки разреженной матрицы