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

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

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

В 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

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

Разреженные векторы хранятся в аналоге сжатого столбца (CSC) для разреженных матриц. В 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}...)

Построение квадратной разреженной диагональной матрицы из векторов и диагоналей. Вектор 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.