Scipy разреженная треугольная матрица?

Question

Я использую Scipy для построения большой, разреженной (250k x 250k) матрицы совпадений, используя scipy.sparse.lil_matrix. Матрицы совместного вхождения являются треугольными; то есть M [i, j] == M [j, i]. Поскольку было бы крайне неэффективно (а в моем случае невозможно) хранить все данные дважды, в настоящее время я храню данные по координатам (i, j), где i всегда меньше j. Другими словами, у меня есть значение, хранящееся в (2,3), и нет значения, хранящегося в (3,2), даже если (3,2) в моей модели должно быть равно (2,3). (См. Таблицу ниже для примера)

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

M = 
    [1 2 3 4
     0 5 6 7
     0 0 8 9
     0 0 0 10]

Итак, учитывая вышеприведенную матрицу, я хочу иметь возможность выполнить запрос типа M[1] и получить обратно [2,5,6,7]. У меня два вопроса:

1) Есть ли более эффективный (желательно встроенный) способ сделать это, чем сначала запрос строки, а затем столбца, а затем их объединение? Это плохо, потому что, независимо от того, использую ли я внутреннее представление CSC (на основе столбцов) или CSR (на основе строк), один из двух запросов крайне неэффективен.

2) Я даже использую правую часть Сципи? Я видел несколько функций в библиотеке Scipy, которые упоминают треугольные матрицы, но они, кажется, вращаются вокруг получения треугольных матриц из полной матрицы. В моем случае (я думаю) у меня уже есть треугольная матрица, и я хочу ею манипулировать.

Большое спасибо.

Answer 1

Я бы сказал, что у вас не может быть торта и есть его: если вы хотите эффективного хранения, вы не можете хранить полные ряды (как вы говорите);если вам нужен эффективный доступ к строкам, я бы сказал, что вам нужно хранить полные строки.

Хотя реальная производительность зависит от вашего приложения, вы можете проверить, работает ли для вас следующий подход:

1. Вы используете разреженные матрицы Сципи для эффективного хранения.

2. Вы автоматически симметризируете свою матрицу (существует небольшой рецепт в StackOverflow, который работает, по крайней мере, на обычных матрицах).

3. После этого вы можете получить доступ к его строкам (или столбцам);Эффективность этого зависит от реализации разреженных матриц ...