Быстрый способ найти индексы ненулевых записей для каждой строки в матрице CS C в Python - PullRequest
Новая
       19

Быстрый способ найти индексы ненулевых записей для каждой строки в матрице CS C в Python

0 голосов
/ 12 июля 2020

Вот текущая реализация: 

def nonzero_indexes_by_row(input):
    return [
        np.nonzero(row)[1] 
        for row in csr_matrix(input.T)
    ]

Матрица очень большая (1,5M, 500K), так как я обращаюсь к строкам, мне сначала нужно преобразовать CS C в CSR. Результатом будет 2d список, каждый из которых содержит список ненулевых индексов, соответствующих строке в исходной матрице.

Текущий процесс занимает 20 минут. Есть ли способ быстрее?

Ответы [ 2 ]

2 голосов
/ 20 июля 2020

Конечно. Вы довольно близки к идеальному решению, но выделяете ненужные массивы. Вот более быстрый способ: 

from scipy import sparse
import numpy as np

def my_impl(csc):
    csr = csc.tocsr()
    return np.split(csr.indices, csr.indptr[1:-1])

def your_impl(input):
    return [
        np.nonzero(row)[1] 
        for row in sparse.csr_matrix(input)
    ]

## Results

# demo data
csc = sparse.random(15000, 5000, format="csc")

your_result = your_impl(csc)
my_result = my_impl(csc)

## Tests for correctness

# Same result
assert all(np.array_equal(x, y) for x, y in zip(your_result, my_result))
# Right number of rows
assert len(my_result) == csc.shape[0]

## Speed

%timeit my_impl(csc)
# 31 ms ± 1.26 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit your_impl(csc)
# 1.49 s ± 19.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Дополнительный вопрос, почему вы транспонируете матрицу? Разве тогда вы не получили бы ненулевые записи столбцов? Если это то, что вы хотите, вам даже не нужно конвертировать в csr, и вы можете просто запустить: 

np.split(csc.indices, csc.indptr[1:-1])
1 голос
/ 12 июля 2020

Интересной альтернативой вашему коду является преобразование массива в формат COOrdinate , а затем чтение его атрибутов row и col : 

def nonzero_indices_by_coo(input):
    cx = input.T.tocoo()
    res = [ [] for i in range(cx.shape[0]) ]
    for i, j in zip(cx.row, cx.col):
        res[i].append(j)
    return res

Он возвращает список простых списков pythoni c вместо массивов Numpy, но это не должно быть важной разницей.

Я заметил, что ваш код использует внутреннее транспонирование исходного массива (оператор T ), поэтому я сделал то же самое в своем коде.

Чтобы сравнить скорость выполнения, я создал следующий разреженный массив ( 2000 по 300 ): 

r = 2000; c = 300
x = scipy.sparse.lil_matrix( (r,c) )
for _ in range(r):
    x[np.random.randint(0,r-1), np.random.randint(0,c-1)] = np.random.randint(1,100)

и мой код работал примерно в 12 раз быстрее, чем ваш.

Еще более быстрое решение (в другом формате)

Или, может быть, будет лучше сгенерировать массив 2-D (Numpy) с 2 строками:

  • первая строка - индексы строк из последовательных ненулевых элементов,
  • вторая строка - индексы столбцов.

Для получения такого результата вы можете использовать e следующий код: 

def nonzero_indices_2d(input):
    cx = input.T.tocoo()
    return np.array([cx.row, cx.col])

, который работает в 4 раза быстрее, чем мое первое решение.

Конечно, тогда другие части вашего кода должны быть переработаны, чтобы использовать индексы, указанные в другом формат.

Разреженные массивы также имеют свой собственный ненулевой метод: 

arr.nonzero()

создание 2-строчного Numpy массив индексов. Эта функция работает еще на несколько процентов быстрее.

Итак, если предположить, что формат результата 2-D приемлем (вместо списка списков), возможно, вам не нужен собственный функция для получения этих индексов.

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

...