Пустые нули в массиве

Я пытаюсь получить максимальную производительность от numpy, и мне было интересно, есть ли лучший способ вычислить точечный продукт с массивом, в котором много нулей, например:

a = np.array([[0, 3, 0], [1, 0, 1]])
print a.dot([1, 2, 5])

это небольшой пример, но если бы у нас был массив гораздо большего масштаба, в котором, скажем, 80% нулей в любом месте массива, мой вопрос был бы в том, есть ли лучший или предпочтительно более быстрый способ вычисления скалярного произведения, когда их так много нули?


python numpy dot-product
person GlacierSG    schedule 17.02.2017    source источник
comment
Возможно, использование разреженных матриц было бы быстрее.   -  person Akavall    schedule 18.02.2017
comment
Существует пакет scipy.sparse, который создает и использует разреженные матрицы. Но по моему опыту матрица должна иметь разреженность ниже 1%, чтобы получить преимущество в скорости над numpy dot (т.е. 99% нулей).   -  person hpaulj    schedule 18.02.2017
comment
Я рассмотрю разреженные матрицы, но вы бы порекомендовали использовать их постоянно или только тогда, когда их значение выше 99% @hpaulj   -  person GlacierSG    schedule 18.02.2017
comment
Существует достаточно кривой обучения и ограничений, которые я бы не переключил только на то, чтобы ускорить несколько продуктов dot. Первоначально они были разработаны для больших задач линейной алгебры (конечный элемент, разность), но теперь также используют машинное обучение. Для чего еще вы используете эти матрицы?   -  person hpaulj    schedule 18.02.2017
comment
Пока просто точечный продукт, мне может понадобиться их транспонировать в будущем, но больше ничего   -  person GlacierSG    schedule 18.02.2017
comment
Почему бы тебе просто не попробовать? Создать разреженную матрицу так же просто, как sparse.csr_matrix(dense_array) транспонировать так же дешево, как и с плотными матрицами, а основные операции имеют тот же синтаксис. Чтобы вернуться, используйте sparse_matrix.todense().A, если только вы действительно не хотите matrix, а не array, и в этом случае пропустите .A.   -  person Paul Panzer    schedule 18.02.2017
comment
Тем не менее, с разреженностью 80% @hpaulj, скорее всего, прав в том смысле, что вам не следует ожидать ускорения.   -  person Paul Panzer    schedule 18.02.2017

Ответы (1)


arrow_upward
1
arrow_downward 

In [269]: from scipy import sparse
In [270]: M=sparse.random(1000,1000,.1, 'csr')
In [271]: MA = M.A
In [272]: timeit M*M.T
10 loops, best of 3: 64 ms per loop
In [273]: timeit [email protected]
10 loops, best of 3: 60.4 ms per loop

Я определил случайную разреженную матрицу с указанной разреженностью, 10%:

In [274]: M
Out[274]: 
<1000x1000 sparse matrix of type '<class 'numpy.float64'>'
    with 100000 stored elements in Compressed Sparse Row format>
In [275]: np.allclose([email protected], (M*M.T).A)
Out[275]: True

@ — это операторная форма dot (см. np.matmul). Таким образом, при этом уровне разреженности 10 % два подхода совпадают по времени (без преобразования в/из разреженности).

Для этой случайной матрицы результат M*M.T является плотным:

In [282]: (M*M.T)
Out[282]: 
<1000x1000 sparse matrix of type '<class 'numpy.float64'>'
    with 999964 stored elements in Compressed Sparse Row format>

Разреженное время сильно зависит от разреженности; плотные времена совсем не

In [295]: M=sparse.random(1000,1000,.01, 'csr'); MA=M.A
In [296]: timeit M*M.T
100 loops, best of 3: 2.44 ms per loop
In [297]: timeit [email protected]
10 loops, best of 3: 56.3 ms per loop
In [298]: M=sparse.random(1000,1000,.2, 'csr'); MA=M.A
In [299]: timeit M*M.T
10 loops, best of 3: 175 ms per loop
In [300]: timeit [email protected]
10 loops, best of 3: 56.3 ms per loop

При круговом переходе в разреженный и обратно время подскакивает с 60 до 100 мс.

In [302]: %%timeit
     ...: M1=sparse.csr_matrix(MA)
     ...: (M1*M1.T).A
     ...: 
10 loops, best of 3: 104 ms per loop
person hpaulj    schedule 18.02.2017
comment
@ у меня не сработало, вместо этого я использовал MA.dot(MA.T) - person GlacierSG; 18.02.2017
comment
Я просто ленился в новом python/numpy. Для таких двумерных массивов результаты должны быть одинаковыми. - person hpaulj; 18.02.2017