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

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 i is in colptr[i]:(colptr[i+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, 2, 3], [1, 2, 3], [0, 2, 0])
3×3 SparseMatrixCSC{Int64,Int64} with 3 stored entries:
  [1, 1]  =  0
  [2, 2]  =  2
  [3, 3]  =  0

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

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

Разреженные векторы хранятся в аналоге формата 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 быть ненулевым.

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

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

SparseArrays.SparseVectorТип

SparseVector{Tv,Ti<:Integer} <: AbstractSparseVector{Tv,Ti}

Тип вектора для хранения разреженных векторов.

SparseArrays.SparseMatrixCSCТип

SparseMatrixCSC{Tv,Ti<:Integer} <: AbstractSparseMatrix{Tv,Ti}

Тип матрицы для хранения разреженных матриц в формате Compressed Sparse Column.

SparseArrays.sparseФункция

sparse(A)

Преобразовать AbstractMatrix A в разреженную матрицу.

Примеры

julia> A = Matrix(1.0I, 3, 3)
3×3 Array{Float64,2}:
 1.0  0.0  0.0
 0.0  1.0  0.0
 0.0  0.0  1.0

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

sparse(I, J, V,[ m, n, combine])

Создать разреженную матрицу S размеров m x n таким образом, что S[I[k], J[k]] = V[k]. Функция combine используется для объединения дубликатов. Если m и n не указаны, они устанавливаются соответственно в maximum(I) и maximum(J). Если функция combine не указана, combine по умолчанию +, если элементы V не являются булевыми значениями, в этом случае combine по умолчанию |. Все элементы I должны удовлетворять условию 1 <= I[k] <= m, а все элементы J должны удовлетворять условию 1 <= J[k] <= n. Числовые нули в (I, J, V) сохраняются как структурные ненулевые элементы; для удаления числовых нулей используйте dropzeros!.

Дополнительная документация и драйвер эксперта находятся в Base.SparseArrays.sparse!.

Примеры

julia> Is = [1; 2; 3];

julia> Js = [1; 2; 3];

julia> Vs = [1; 2; 3];

julia> sparse(Is, Js, Vs)
3×3 SparseMatrixCSC{Int64,Int64} with 3 stored entries:
  [1, 1]  =  1
  [2, 2]  =  2
  [3, 3]  =  3

SparseArrays.sparsevecФункция

sparsevec(I, V, [m, combine])

Создайте разреженный вектор S длины m таким образом, чтобы S[I[k]] = V[k]. Дубликаты объединяются с помощью функции combine, которая по умолчанию равна +, если аргумент combine не указан, если элементы V являются булевыми значениями, в этом случае combine по умолчанию равно |.

Примеры

julia> II = [1, 3, 3, 5]; V = [0.1, 0.2, 0.3, 0.2];

julia> sparsevec(II, V)
5-element SparseVector{Float64,Int64} with 3 stored entries:
  [1]  =  0.1
  [3]  =  0.5
  [5]  =  0.2

julia> sparsevec(II, V, 8, -)
8-element SparseVector{Float64,Int64} with 3 stored entries:
  [1]  =  0.1
  [3]  =  -0.1
  [5]  =  0.2

julia> sparsevec([1, 3, 1, 2, 2], [true, true, false, false, false])
3-element SparseVector{Bool,Int64} with 3 stored entries:
  [1]  =  true
  [2]  =  false
  [3]  =  true

sparsevec(d::Dict, [m])

Создайте разреженный вектор длины m, где ненулевые индексы являются ключами из словаря, а ненулевые значения — значениями из словаря.

Примеры

julia> sparsevec(Dict(1 => 3, 2 => 2))
2-element SparseVector{Int64,Int64} with 2 stored entries:
  [1]  =  3
  [2]  =  2

sparsevec(A)

Преобразуйте вектор A в разреженный вектор длины m.

Примеры

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

SparseArrays.issparseФункция

issparse(S)

Возвращает true, если S является разреженным, и false в противном случае.

Примеры

julia> sv = sparsevec([1, 4], [2.3, 2.2], 10)
10-element SparseVector{Float64,Int64} with 2 stored entries:
  [1 ]  =  2.3
  [4 ]  =  2.2

julia> issparse(sv)
true

julia> issparse(Array(sv))
false

SparseArrays.nnzФункция

nnz(A)

Возвращает количество хранимых (заполненных) элементов в разреженной матрице.

Примеры

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

julia> nnz(A)
3

SparseArrays.findnzФункция

findnz(A)

Возвращает кортеж (I, J, V), где I и J — строковые и столбцовые индексы хранимых ("структурно ненулевых") значений в разреженной матрице A, а V — вектор значений.

Примеры

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

julia> findnz(A)
([1, 1, 3, 2], [1, 2, 2, 3], [1, 2, 4, 3])

SparseArrays.spzerosФункция

spzeros([type,]m[,n])

Создайте разреженный вектор длины m или разреженную матрицу размера m x n. Эта разреженная матрица не будет содержать ненулевых значений. При создании не будет выделено памяти для ненулевых значений. Тип по умолчанию — Float64, если не указан другой.

Примеры

julia> spzeros(3, 3)
3×3 SparseMatrixCSC{Float64,Int64} with 0 stored entries

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

SparseArrays.spdiagmФункция

spdiagm(kv::Pair{<:Integer,<:AbstractVector}...)

Постройте квадратную разреженную диагональную матрицу из Pair векторов и диагоналей. Вектор kv.second будет размещен на kv.first диагонали.

Примеры

julia> spdiagm(-1 => [1,2,3,4], 1 => [4,3,2,1])
5×5 SparseMatrixCSC{Int64,Int64} with 8 stored entries:
  [2, 1]  =  1
  [1, 2]  =  4
  [3, 2]  =  2
  [2, 3]  =  3
  [4, 3]  =  3
  [3, 4]  =  2
  [5, 4]  =  4
  [4, 5]  =  1

SparseArrays.blockdiagФункция

blockdiag(A...)

Объединить матрицы по блокам по диагонали. В настоящее время реализовано только для разреженных матриц.

Примеры

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

SparseArrays.sprandФункция

sprand([rng],[type],m,[n],p::AbstractFloat,[rfn])

Создать случайный вектор длины m или m на n разреженную матрицу, в которой вероятность любого элемента быть ненулевым независимо задаётся p (а следовательно, средняя плотность ненулевых элементов также точно равна p). Ненулевые значения выбираются из распределения, заданного rfn, и имеют тип type. Если rfn не указано, используется равномерное распределение. Дополнительный аргумент rng задаёт генератор случайных чисел, см. Случайные числа.

Примеры

julia> sprand(Bool, 2, 2, 0.5)
2×2 SparseMatrixCSC{Bool,Int64} with 2 stored entries:
  [1, 1]  =  true
  [2, 1]  =  true

julia> sprand(Float64, 3, 0.75)
3-element SparseVector{Float64,Int64} with 1 stored entry:
  [3]  =  0.298614

SparseArrays.sprandnФункция

sprandn([rng], m[,n],p::AbstractFloat)

Создайте случайный разреженный вектор длины m или разреженную матрицу размера m на n с заданной (независимой) вероятностью p любого элемента быть ненулевым, где ненулевые значения выбираются из нормального распределения. Дополнительный аргумент rng задаёт генератор случайных чисел, см. Случайные числа.

Примеры

julia> sprandn(2, 2, 0.75)
2×2 SparseMatrixCSC{Float64,Int64} with 2 stored entries:
  [1, 1]  =  0.586617
  [1, 2]  =  0.297336

SparseArrays.nonzerosФункция

nonzeros(A)

Возвращает вектор структурно ненулевых значений в разреженной матрице A. Это включает явным образом хранимые нули в разреженной матрице. Возвращаемый вектор ссылается непосредственно на внутреннее хранилище ненулевых значений A, и любые изменения в возвращаемом векторе изменят A тоже. См. rowvals и nzrange.

Примеры

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

julia> nonzeros(A)
3-element Array{Int64,1}:
 2
 2
 2

SparseArrays.rowvalsФункция

rowvals(A::SparseMatrixCSC)

Возвращает вектор строковых индексов A. Любые изменения в возвращаемом векторе изменят A тоже. Доступ к внутреннему хранению строковых индексов может быть полезен в сочетании с итерацией по структурно ненулевым значениям. См. также nonzeros и nzrange.

Примеры

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

julia> rowvals(A)
3-element Array{Int64,1}:
 1
 2
 3

SparseArrays.nzrangeФункция

nzrange(A::SparseMatrixCSC, col::Integer)

Возвращает диапазон индексов структурно ненулевых значений столбца разреженной матрицы. В сочетании с nonzeros и rowvals это позволяет удобно итерироваться по разреженной матрице:

A = sparse(I,J,V)
rows = rowvals(A)
vals = nonzeros(A)
m, n = size(A)
for i = 1:n
   for j in nzrange(A, i)
      row = rows[j]
      val = vals[j]
      # perform sparse wizardry...
   end
end

SparseArrays.dropzeros!Функция

dropzeros!(A::SparseMatrixCSC; trim::Bool = true)

Удаляет хранимые числовые нули из A, необязательно обрезая лишнее пространство в A.rowval и A.nzval при trim равном true.

Для варианта без модификации исходного объекта см. dropzeros. Для информации об алгоритме см. fkeep!.

dropzeros!(x::SparseVector; trim::Bool = true)

Удаляет хранимые числовые нули из x, необязательно обрезая лишнее пространство в x.nzind и x.nzval при trim равном true.

Для варианта без модификации исходного объекта см. dropzeros. Для информации об алгоритме см. fkeep!.

SparseArrays.dropzerosФункция

dropzeros(A::SparseMatrixCSC; trim::Bool = true)

Создает копию A и удаляет хранимые числовые нули из этой копии, необязательно обрезая лишнее пространство в массивах rowval и nzval при trim равном true.

Для варианта модификации исходного объекта см. dropzeros!.

Примеры

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

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

dropzeros(x::SparseVector; trim::Bool = true)

Создаёт копию x и удаляет числовые нули из этой копии, необязательно обрезая лишнее пространство в массивах nzind и nzval при trim равном true.

Для варианта модификации исходного объекта см. dropzeros!.

Примеры

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

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

SparseArrays.permuteФункция

permute(A::SparseMatrixCSC{Tv,Ti}, p::AbstractVector{<:Integer},
        q::AbstractVector{<:Integer}) where {Tv,Ti}

Взаимно переставляет A, возвращая PAQ (A[p,q]). Длина столбцовой перестановки q должна совпадать с количеством столбцов A (length(q) == A.n). Длина строчной перестановки p должна совпадать с количеством строк A (length(p) == A.m).

Для опытных пользователей и дополнительной информации см. permute!.

Примеры

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

julia> permute(A, [4, 3, 2, 1], [1, 2, 3, 4])
4×4 SparseMatrixCSC{Int64,Int64} with 7 stored entries:
  [4, 1]  =  1
  [3, 2]  =  2
  [4, 2]  =  5
  [2, 3]  =  3
  [3, 3]  =  6
  [1, 4]  =  4
  [2, 4]  =  7

julia> permute(A, [1, 2, 3, 4], [4, 3, 2, 1])
4×4 SparseMatrixCSC{Int64,Int64} with 7 stored entries:
  [3, 1]  =  7
  [4, 1]  =  4
  [2, 2]  =  6
  [3, 2]  =  3
  [1, 3]  =  5
  [2, 3]  =  2
  [1, 4]  =  1

Base.permute!Метод

permute!(X::SparseMatrixCSC{Tv,Ti}, A::SparseMatrixCSC{Tv,Ti},
         p::AbstractVector{<:Integer}, q::AbstractVector{<:Integer},
         [C::SparseMatrixCSC{Tv,Ti}]) where {Tv,Ti}

Взаимно переставляет A, сохраняя результат PAQ (A[p,q]) в X. Сохраняет промежуточный результат (AQ)^T (transpose(A[:,q])) в необязательном аргументе C при его наличии. Требует, чтобы ни X, ни A, и, если присутствует, ни C не были ссылками друг на друга; для сохранения результата PAQ обратно в A, используйте следующий метод без X:

permute!(A::SparseMatrixCSC{Tv,Ti}, p::AbstractVector{<:Integer},
         q::AbstractVector{<:Integer}[, C::SparseMatrixCSC{Tv,Ti},
         [workcolptr::Vector{Ti}]]) where {Tv,Ti}

Размеры X должны совпадать с размерами A (X.m == A.m и X.n == A.n), и X должен иметь достаточно места для размещения всех выделенных элементов в A (length(X.rowval) >= nnz(A) и length(X.nzval) >= nnz(A)). Длина столбцовой перестановки q должна совпадать с количеством столбцов A (length(q) == A.n). Длина строчной перестановки p должна совпадать с количеством строк A (length(p) == A.m).

Размеры C должны совпадать с размерами transpose(A) (C.m == A.n и C.n == A.m), и C должен иметь достаточно места для размещения всех выделенных элементов в A (length(C.rowval) >= nnz(A) и length(C.nzval) >= nnz(A)).

Для дополнительной (алгоритмической) информации и для версий этих методов, которые отказываются от проверки аргументов, см. (неэкспортированные) родительские методы unchecked_noalias_permute! и unchecked_aliasing_permute!.

См. также: permute.