Разреженные массивы

В Julia есть поддержка разреженных векторов и разреженных матриц в модуле SparseArrays stdlib. Разреженные массивы — это массивы, содержащие достаточно нулей, что хранение их в специальной структуре данных приводит к экономии памяти и времени выполнения по сравнению с плотным массивом.

Хранение разреженной матрицы в формате Compressed Sparse Column (CSC)

В Julia разреженные матрицы хранятся в формате Compressed Sparse Column (CSC). Разреженные матрицы Julia имеют тип SparseMatrixCSC{Tv,Ti}, где Tv — тип хранимых значений, а Ti — целочисленный тип для хранения указателей на столбцы и индексов строк. Внутреннее представление SparseMatrixCSC таково:

struct SparseMatrixCSC{Tv,Ti<:Integer} <: AbstractSparseMatrix{Tv,Ti}
    m::Int                  # Number of rows
    n::Int                  # Number of columns
    colptr::Vector{Ti}      # Column j is in colptr[j]:(colptr[j+1]-1)
    rowval::Vector{Ti}      # Row indices of stored values
    nzval::Vector{Tv}       # Stored values, typically nonzeros
end

Хранение в формате Compressed Sparse Column (CSC) позволяет легко и быстро получить доступ к элементам столбца разреженной матрицы, в то время как доступ к разреженной матрице по строкам значительно медленнее. Операции, такие как вставка ранее не хранимых элементов по одному в структуру CSC, как правило, медленны. Это связано с тем, что все элементы разреженной матрицы, которые находятся за точкой вставки, должны быть смещены на одну позицию.

Все операции над разреженными матрицами тщательно реализованы для использования структуры данных CSC с целью повышения производительности и избегания дорогостоящих операций.

Если у вас есть данные в формате CSC из другого приложения или библиотеки и вы хотите импортировать их в Julia, убедитесь, что вы используете индексирование с началом с 1. Индексы строк в каждом столбце должны быть отсортированы. Если ваш SparseMatrixCSC объект содержит неотсортированные индексы строк, один быстрый способ отсортировать их — выполнить двойное транспонирование.

В некоторых приложениях удобно хранить явные нулевые значения в SparseMatrixCSC. Эти значения принимаются функциями в Base (но нет гарантии, что они будут сохранены в операциях изменения). Такие явно хранимые нули рассматриваются как структурные ненулевые элементы многими процедурами. Функция nnz возвращает количество элементов, явно хранимых в структуре разреженных данных, включая структурные ненулевые элементы. Для подсчета точного количества числовых ненулевых элементов используйте count(!iszero, x), которая проверяет каждый хранимый элемент разреженной матрицы. dropzeros и ин-место операция dropzeros! могут использоваться для удаления хранимых нулей из разреженной матрицы.

julia> A = sparse([1, 1, 2, 3], [1, 3, 2, 3], [0, 1, 2, 0])
3×3 SparseMatrixCSC{Int64,Int64} with 4 stored entries:
  [1, 1]  =  0
  [2, 2]  =  2
  [1, 3]  =  1
  [3, 3]  =  0

julia> dropzeros(A)
3×3 SparseMatrixCSC{Int64,Int64} with 2 stored entries:
  [2, 2]  =  2
  [1, 3]  =  1

Хранение разреженных векторов

Разреженные векторы хранятся в аналоге сжатого разреженного столбцового формата для разреженных матриц. В Julia разреженные векторы имеют тип SparseVector{Tv,Ti}, где Tv — тип хранимых значений, а Ti — целочисленный тип для индексов. Внутреннее представление таково:

struct SparseVector{Tv,Ti<:Integer} <: AbstractSparseVector{Tv,Ti}
    n::Int              # Length of the sparse vector
    nzind::Vector{Ti}   # Indices of stored values
    nzval::Vector{Tv}   # Stored values, typically nonzeros
end

Как и для SparseMatrixCSC, тип SparseVector также может содержать явно хранящиеся нули. (См. Хранение разреженных матриц.).

Конструкторы разреженных векторов и матриц

Самый простой способ создать разреженную матрицу — использовать функцию, эквивалентную функции zeros, которую Julia предоставляет для работы с плотным массивом. Для получения разреженного массива можно использовать то же имя с префиксом sp:

julia> spzeros(3)
3-element SparseVector{Float64,Int64} with 0 stored entries

Функция sparse часто является удобным способом построения разреженных массивов. Например, чтобы построить разреженную матрицу, мы можем ввести вектор I строчных индексов, вектор J столбцовых индексов и вектор V хранимых значений (это также известно как формат COO (координат)). sparse(I,J,V) затем строит разреженную матрицу так, что S[I[k], J[k]] = V[k]. Эквивалентный конструктор разреженного вектора — sparsevec, который принимает вектор (строчных) индексов I и вектор V сохранённых значений и строит разреженный вектор R так, что R[I[k]] = V[k].

julia> I = [1, 4, 3, 5]; J = [4, 7, 18, 9]; V = [1, 2, -5, 3];

julia> S = sparse(I,J,V)
5×18 SparseMatrixCSC{Int64,Int64} with 4 stored entries:
  [1,  4]  =  1
  [4,  7]  =  2
  [5,  9]  =  3
  [3, 18]  =  -5

julia> R = sparsevec(I,V)
5-element SparseVector{Int64,Int64} with 4 stored entries:
  [1]  =  1
  [3]  =  -5
  [4]  =  2
  [5]  =  3

Обратной функцией для функций sparse и sparsevec является findnz, которая извлекает входные данные, используемые для создания разреженного массива. findall(!iszero, x) возвращает декартовы индексы ненулевых элементов в x (включая сохранённые элементы, равные нулю).

julia> findnz(S)
([1, 4, 5, 3], [4, 7, 9, 18], [1, 2, 3, -5])

julia> findall(!iszero, S)
4-element Array{CartesianIndex{2},1}:
 CartesianIndex(1, 4)
 CartesianIndex(4, 7)
 CartesianIndex(5, 9)
 CartesianIndex(3, 18)

julia> findnz(R)
([1, 3, 4, 5], [1, -5, 2, 3])

julia> findall(!iszero, R)
4-element Array{Int64,1}:
 1
 3
 4
 5

Ещё один способ создания разреженного массива — преобразовать плотный массив в разреженный массив, используя функцию sparse:

julia> sparse(Matrix(1.0I, 5, 5))
5×5 SparseMatrixCSC{Float64,Int64} with 5 stored entries:
  [1, 1]  =  1.0
  [2, 2]  =  1.0
  [3, 3]  =  1.0
  [4, 4]  =  1.0
  [5, 5]  =  1.0

julia> sparse([1.0, 0.0, 1.0])
3-element SparseVector{Float64,Int64} with 2 stored entries:
  [1]  =  1.0
  [3]  =  1.0

Вы можете двигаться в обратном направлении, используя конструктор Array. Функция issparse может использоваться для проверки, является ли матрица разреженной.

julia> issparse(spzeros(5))
true

Операции с разреженными матрицами

Арифметические операции с разреженными матрицами также работают так же, как и с плотно заполненными матрицами. Индексирование, присваивание и конкатенация разреженных матриц работают так же, как и для плотных матриц. Операции индексирования, особенно присваивание, являются ресурсоемкими, если выполняются по одному элементу за раз. Во многих случаях может быть лучше преобразовать разреженную матрицу в формат (I,J,V) с помощью findnz, манипулировать значениями или структурой в плотных векторах (I,J,V), а затем восстановить разреженную матрицу.

Соответствие плотных и разреженных методов

В следующей таблице приведено соответствие встроенных методов для разреженных матриц и их соответствующих методов для плотных матриц. В общем случае методы, генерирующие разреженные матрицы, отличаются от своих плотных аналогов тем, что результирующая матрица следует тому же шаблону разреженности, что и заданная разреженная матрица S, или что результирующая разреженная матрица имеет плотность d, т.е. каждый элемент матрицы имеет вероятность d быть ненулевым.

Подробности можно найти в разделе «Разреженные векторы и матрицы» справочника стандартной библиотеки.

Разреженный	Плотный	Описание
`spzeros(m,n)`	`zeros(m,n)`	Создаёт матрицу размера m×n, заполненную нулями. (`spzeros(m,n)` пуста.)
`sparse(I, n, n)`	`Matrix(I,n,n)`	Создаёт единичную матрицу размера n×n.
`Array(S)`	`sparse(A)`	Преобразует между плотным и разреженным форматами.
`sprand(m,n,d)`	`rand(m,n)`	Создаёт случайную матрицу размера m×n (с плотностью d) с независимыми и одинаково распределёнными ненулевыми элементами, равномерно распределёнными на полуоткрытом интервале $[0, 1)$.
`sprandn(m,n,d)`	`randn(m,n)`	Создаёт случайную матрицу размера m×n (с плотностью d) с независимыми и одинаково распределёнными ненулевыми элементами, распределёнными по стандартному нормальному (гауссову) распределению.
`sprandn(rng,m,n,d)`	`randn(rng,m,n)`	Создаёт случайную матрицу размера m×n (с плотностью d) с независимыми и одинаково распределёнными ненулевыми элементами, сгенерированными с помощью `rng` генератора случайных чисел

Разреженные массивы

`SparseArrays.AbstractSparseArray`Тип

AbstractSparseArray{Tv,Ti,N}

Базовый тип для N-мерных разреженных массивов (или похожих на массивы типов) с элементами типа Tv и индексы типа Ti. SparseMatrixCSC, SparseVector и SuiteSparse.CHOLMOD.Sparse являются подтипами этого.

Разреженные массивы

Хранение разреженной матрицы в формате Compressed Sparse Column (CSC)

Хранение разреженных векторов

Конструкторы разреженных векторов и матриц

Операции с разреженными матрицами

Соответствие плотных и разреженных методов

Разреженные массивы

SparseArrays.AbstractSparseArrayТип

SparseArrays.AbstractSparseVectorТип

SparseArrays.AbstractSparseMatrixТип

SparseArrays.SparseVectorТип

SparseArrays.SparseMatrixCSCТип

SparseArrays.sparseФункция

SparseArrays.sparsevecФункция

SparseArrays.issparseФункция

SparseArrays.nnzФункция

SparseArrays.findnzФункция

SparseArrays.spzerosФункция

SparseArrays.spdiagmФункция

SparseArrays.blockdiagФункция

SparseArrays.sprandФункция

SparseArrays.sprandnФункция

SparseArrays.nonzerosФункция

SparseArrays.rowvalsФункция

SparseArrays.nzrangeФункция

SparseArrays.droptol!Функция

SparseArrays.dropzeros!Функция

SparseArrays.dropzerosФункция

SparseArrays.permuteФункция

Base.permute!Метод

`SparseArrays.AbstractSparseArray`Тип

`SparseArrays.AbstractSparseVector`Тип

`SparseArrays.AbstractSparseMatrix`Тип

`SparseArrays.SparseVector`Тип

`SparseArrays.SparseMatrixCSC`Тип

`SparseArrays.sparse`Функция

`SparseArrays.sparsevec`Функция

`SparseArrays.issparse`Функция

`SparseArrays.nnz`Функция

`SparseArrays.findnz`Функция

`SparseArrays.spzeros`Функция

`SparseArrays.spdiagm`Функция

`SparseArrays.blockdiag`Функция

`SparseArrays.sprand`Функция

`SparseArrays.sprandn`Функция

`SparseArrays.nonzeros`Функция

`SparseArrays.rowvals`Функция

`SparseArrays.nzrange`Функция

`SparseArrays.droptol!`Функция

`SparseArrays.dropzeros!`Функция

`SparseArrays.dropzeros`Функция

`SparseArrays.permute`Функция

`Base.permute!`Метод