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

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 для повышения производительности и избежания дорогостоящих операций.

Если у вас есть данные в формате 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` генератора случайных чисел

API разреженных массивов

`SparseArrays.AbstractSparseArray`Тип

AbstractSparseArray{Tv,Ti,N}

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

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

SparseArrays.AbstractSparseArrayТип

SparseArrays.AbstractSparseVectorТип

SparseArrays.AbstractSparseMatrixТип

SparseArrays.SparseVectorТип

SparseArrays.SparseMatrixCSCТип

SparseArrays.sparseФункция

SparseArrays.sparse!Функция

SparseArrays.sparsevecФункция

Base.similarМетод

SparseArrays.issparseФункция

SparseArrays.nnzФункция

SparseArrays.findnzФункция

SparseArrays.spzerosФункция

SparseArrays.spzeros!Функция

SparseArrays.spdiagmФункция

SparseArrays.sparse_hcatФункция

SparseArrays.sparse_vcatФункция

SparseArrays.sparse_hvcatФункция

SparseArrays.blockdiagФункция

SparseArrays.sprandФункция

SparseArrays.sprandnФункция

SparseArrays.nonzerosФункция

SparseArrays.rowvalsФункция

SparseArrays.nzrangeФункция

SparseArrays.droptol!Функция

SparseArrays.dropzeros!Функция

SparseArrays.dropzerosФункция

SparseArrays.permuteФункция

Base.permute!Метод

SparseArrays.halfperm!Функция

SparseArrays.ftranspose!Функция

`SparseArrays.AbstractSparseArray`Тип

`SparseArrays.AbstractSparseVector`Тип

`SparseArrays.AbstractSparseMatrix`Тип

`SparseArrays.SparseVector`Тип

`SparseArrays.SparseMatrixCSC`Тип

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

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

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

`Base.similar`Метод

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

`Base.permute!`Метод

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

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