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

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. Стандартный способ создания SparseMatrixCSC — через функцию sparse. См. также spzeros, spdiagm и sprand.

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!.

Для дополнительной документации и специализированного драйвера, см. 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][,Type],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.