Sparse Arrays

تدعم جوليا المتجهات النادرة و sparse matrices في وحدة SparseArrays القياسية. المصفوفات النادرة هي مصفوفات تحتوي على عدد كافٍ من الأصفار بحيث يؤدي تخزينها في هيكل بيانات خاص إلى توفير في المساحة ووقت التنفيذ، مقارنةً بالمصفوفات الكثيفة.

يمكن العثور على حزم خارجية تقوم بتنفيذ أنواع تخزين متفرقة مختلفة، ومصفوفات متفرقة متعددة الأبعاد، والمزيد في Noteworthy External Sparse Packages

Compressed Sparse Column (CSC) Sparse Matrix Storage

في جوليا، يتم تخزين المصفوفات النادرة في Compressed Sparse Column (CSC) format. تحتوي مصفوفات جوليا النادرة على النوع 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

تجعل تخزين الأعمدة المتفرقة المضغوطة من السهل والسريع الوصول إلى العناصر في عمود مصفوفة متفرقة، بينما يكون الوصول إلى المصفوفة المتفرقة عن طريق الصفوف أبطأ بكثير. العمليات مثل إدخال إدخالات غير مخزنة مسبقًا واحدة تلو الأخرى في هيكل CSC تميل إلى أن تكون بطيئة. وذلك لأن جميع عناصر المصفوفة المتفرقة التي تتجاوز نقطة الإدخال يجب أن تُنقل مكانًا واحدًا.

تم تنفيذ جميع العمليات على المصفوفات النادرة بعناية لاستغلال بنية بيانات CSC من أجل الأداء، ولتجنب العمليات المكلفة.

إذا كان لديك بيانات بتنسيق CSC من تطبيق أو مكتبة مختلفة، وترغب في استيرادها في جوليا، تأكد من أنك تستخدم الفهرسة التي تبدأ من 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  ⋅
 ⋅  ⋅  ⋅

Sparse Vector Storage

تُخزَّن المتجهات النادرة في تنسيق مشابه جدًا لتنسيق العمود النادر المضغوط للمصفوفات النادرة. في جوليا، تمتلك المتجهات النادرة النوع 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 أيضًا على أصفار مخزنة بشكل صريح. (انظر Sparse Matrix Storage.)

Sparse Vector and Matrix Constructors

أبسط طريقة لإنشاء مصفوفة متفرقة هي استخدام دالة تعادل دالة zeros التي توفرها جوليا للعمل مع المصفوفات الكثيفة. لإنتاج مصفوفة متفرقة بدلاً من ذلك، يمكنك استخدام نفس الاسم مع بادئة sp:

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

تعتبر دالة sparse وسيلة مفيدة غالبًا لبناء المصفوفات المتناثرة. على سبيل المثال، لبناء مصفوفة متناثرة يمكننا إدخال متجه I لمؤشرات الصفوف، ومتجه J لمؤشرات الأعمدة، ومتجه V للقيم المخزنة (وهذا يُعرف أيضًا بـ COO (coordinate) format). تقوم 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

Sparse matrix operations

تعمل العمليات الحسابية على المصفوفات المتناثرة كما تعمل على المصفوفات الكثيفة. يعمل الفهرسة، والتعيين، والدمج للمصفوفات المتناثرة بنفس الطريقة كما في المصفوفات الكثيفة. تعتبر عمليات الفهرسة، وخاصة التعيين، مكلفة، عندما يتم تنفيذها عنصرًا واحدًا في كل مرة. في العديد من الحالات، قد يكون من الأفضل تحويل المصفوفة المتناثرة إلى تنسيق (I,J,V) باستخدام findnz، ومعالجة القيم أو الهيكل في المتجهات الكثيفة (I,J,V)، ثم إعادة بناء المصفوفة المتناثرة.

Correspondence of dense and sparse methods

الجدول التالي يوضح العلاقة بين الطرق المدمجة على المصفوفات المتناثرة والطرق المقابلة لها على أنواع المصفوفات الكثيفة. بشكل عام، تختلف الطرق التي تولد مصفوفات متناثرة عن نظيراتها الكثيفة في أن المصفوفة الناتجة تتبع نفس نمط التشتت لمصفوفة متناثرة معينة S، أو أن المصفوفة المتناثرة الناتجة لها كثافة d، أي أن كل عنصر في المصفوفة لديه احتمال d أن يكون غير صفري.

يمكن العثور على التفاصيل في قسم Sparse Vectors and Matrices من مرجع مكتبة المعايير.

Sparse	Dense	Description
`spzeros(m,n)`	`zeros(m,n)`	Creates a m-by-n matrix of zeros. (`spzeros(m,n)` is empty.)
`sparse(I,n,n)`	`Matrix(I,n,n)`	Creates a n-by-n identity matrix.
`sparse(A)`	`Array(S)`	Interconverts between dense and sparse formats.
`sprand(m,n,d)`	`rand(m,n)`	Creates a m-by-n random matrix (of density d) with iid non-zero elements distributed uniformly on the half-open interval $[0, 1)$.
`sprandn(m,n,d)`	`randn(m,n)`	Creates a m-by-n random matrix (of density d) with iid non-zero elements distributed according to the standard normal (Gaussian) distribution.
`sprandn(rng,m,n,d)`	`randn(rng,m,n)`	Creates a m-by-n random matrix (of density d) with iid non-zero elements generated with the `rng` random number generator

Sparse Linear Algebra

تستدعي حلول المصفوفات المتناثرة دوال من SuiteSparse. التحققات التالية متاحة:

Type	Description
`CHOLMOD.Factor`	Cholesky and LDLt factorizations
`UMFPACK.UmfpackLU`	LU factorization
`SPQR.QRSparse`	QR factorization

تتم مناقشة هذه التحليلات بمزيد من التفصيل في Sparse Linear Algebra API section:

SparseArrays API

SparseArrays.AbstractSparseArray — Type

AbstractSparseArray{Tv,Ti,N}

نوع أعلى لمصفوفات متفرقة ذات N أبعاد (أو أنواع مشابهة للمصفوفات) مع عناصر من نوع Tv ونوع فهرس Ti. SparseMatrixCSC، SparseVector و SuiteSparse.CHOLMOD.Sparse هي أنواع فرعية من هذا.

المكون	الوصف
`L`	الجزء `L` (مثلث سفلي) من `LU`
`U`	الجزء `U` (مثلث علوي) من `LU`
`p`	تبديل يميني `Vector`
`q`	تبديل يساري `Vector`
`Rs`	`Vector` من عوامل التوسيع
`:`	مكونات `(L,U,p,q,Rs)`

المكون	الوصف
`F.L`	`L` (جزء مثلث سفلي) من `LU`
`F.U`	`U` (جزء مثلث علوي) من `LU`
`F.p`	(يمين) تبديل `Vector`
`F.P`	(يمين) تبديل `Matrix`

الوظيفة المدعومة	`LU`	`LU{T,Tridiagonal{T}}`
`/`	✓
`\`	✓	✓
`inv`	✓	✓
`det`	✓	✓
`logdet`	✓	✓
`logabsdet`	✓	✓
`size`	✓	✓