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

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

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

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

struct SparseMatrixCSC{Tv,Ti<:Integer} <: AbstractSparseMatrixCSC{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 из другого приложения или библиотеки и вы хотите импортировать их в 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:
 0  ⋅  1
 ⋅  2  ⋅
 ⋅  ⋅  0

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

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

Разреженные векторы хранятся в аналоге сжатого столбца для разреженных матриц. В 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:
⠀⠈⠀⡀⠀⠀⠀⠀⠠
⠀⠀⠀⠀⠁⠀⠀⠀⠀

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 Vector{CartesianIndex{2}}:
 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 Vector{Int64}:
 1
 3
 4
 5

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

julia> sparse(Matrix(1.0I, 5, 5))
5×5 SparseMatrixCSC{Float64, Int64} with 5 stored entries:
 1.0   ⋅    ⋅    ⋅    ⋅
  ⋅   1.0   ⋅    ⋅    ⋅
  ⋅    ⋅   1.0   ⋅    ⋅
  ⋅    ⋅    ⋅   1.0   ⋅
  ⋅    ⋅    ⋅    ⋅   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 единичную матрицу.
`sparse(A)`	`Array(S)`	Преобразует между плотными и разреженными форматами.
`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!`Метод