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

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

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

Разреженные векторы хранятся в формате, близком к Compressed Sparse Column для разреженных матриц. В 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!`Метод