المصفوفات المتفرقة

خزّن فقط ما ليس صفرًا

كثير من المصفوفات الكبيرة أصفار تقريبًا. شبكة تسعير خيار فيها صف لكل مستوى سعر ويلمس كل صف جاريه فقط. تسمى مثل هذه المصفوفة متفرقة. وتخزين كل صفر يهدر الذاكرة والوقت. تحتفظ scipy.sparse بالعناصر غير الصفرية فقط. وتستعمل الصيغة csr_matrix (الصف المتفرق المضغوط) ثلاث قوائم. تحمل data القيم غير الصفرية صفًا صفًا، وتحمل indices عمود كل قيمة، وتبين indptr أين يبدأ كل صف وينتهي داخل data: الصف $i$ هو data[indptr[i]:indptr[i+1]]. وآخر رقم في indptr هو عدد غير الأصفار nnz.

تناسب الصيغ المختلفة أعمالًا مختلفة. تخزن coo_matrix ثلاثيات بسيطة (صف وعمود وقيمة) وهي الطريقة السهلة لبناء مصفوفة. وتسرع csr_matrix في قص الصفوف وفي الجداء $A\mathbf x$ الذي يكلف نحو nnz عملية ضرب بدل $n^2$ . وcsc_matrix الفكرة نفسها بالأعمدة، وdia_matrix تخزن الأقطار وهي مثالية للمصفوفات الشريطية. ولنظام $A\mathbf x=\mathbf b$ تستفيد sparse.linalg.spsolve من الأصفار فتكون أسرع بكثير من الحل الكثيف. وليس التفرق أفضل دائمًا: إذا زادت العناصر غير الصفرية على الثلث تقريبًا كلّف الحساب الإضافي أكثر مما يوفر. وفي المالية يظهر التفرق في شبكات التسعير وفي نماذج العوامل التي أغلب تحميلاتها صفر وحين تحتفظ بالارتباطات القوية فقط.

A\mathbf x\ \text{costs}\ \approx \mathrm{nnz}\ \text{multiplications},\qquad \text{density}=\frac{\mathrm{nnz}}{n^{2}},\qquad \text{row } i=\texttt{data}[\texttt{indptr}[i]:\texttt{indptr}[i+1]]

(1)

قراءة مصفوفة CSRلنأخذ المصفوفة

4\times4

بصفوفها

(5,0,0,1)

(0,0,2,0)

(0,0,0,0)

(3,0,0,4)

. في CSR تكون data=[5,1,2,3,4] وindices=[0,3,2,0,3] وindptr=[0,2,3,3,5]. الصف

2

فارغ لأن indptr[2]=indptr[3]=3 وnnz=5. والضرب في

(1,1,1,1)

يجمع كل صف فيعطي

(6,2,0,7)

بـ

5

عمليات ضرب فقط. ولمصفوفة ثلاثية القطر بـ

n=1000

كشبكة تسعير بالفروق المنتهية

2{,}998

عنصرًا غير صفري من أصل

1{,}000{,}000

أي كثافة

0.30\%

. وتحتاج نحو

40

كيلوبايت في CSR مقابل

8

ميغابايت كثيفة. وفي بيانات حقيقية تشكل ارتباطات

55

سهمًا من ملف الأسعار المشترك مصفوفة

55\times55

. والاحتفاظ بالعناصر ذات

|\rho|>0.5

فقط يُبقي

249

من

3{,}025

أي

8.2\%

وتأخذ نسخة CSR

3.2

كيلوبايت مقابل

24.2

كثيفة. وعند

|\rho|>0.6

يبقى

4.3\%

فقط.

ثلاث قوائم: data وindices وindptr تصف مصفوفة CSR، وindptr[-1] هو عدد غير الأصفار.
ابنِ بـ COO واحسب بـ CSR: الثلاثيات سهلة التجميع والتخزين بالصفوف سريع للجداءات والحلول.
التفرق يفيد فقط إذا كان أغلبها أصفارًا: المصفوفة الكثيفة أفضل حين تكثر العناصر غير الصفرية.

المختبر: ما الذي يُقيَّم

عدّ غير الأصفار10 نقطة
كم قيمة في صف10 نقطة
كثافة شبكة10 نقطة
جداء متفرق15 نقطة
أي صيغة لأي عمل15 نقطة
نظام ثلاثي القطر10 نقطة
متى يفيد التفرق ومتى لا30 نقطة

خزّن فقط ما ليس صفرًا

A\mathbf x\ \text{costs}\ \approx \mathrm{nnz}\ \text{multiplications},\qquad \text{density}=\frac{\mathrm{nnz}}{n^{2}},\qquad \text{row } i=\texttt{data}[\texttt{indptr}[i]:\texttt{indptr}[i+1]]

(1)

قراءة مصفوفة CSRلنأخذ المصفوفة

4\times4

بصفوفها

(5,0,0,1)

(0,0,2,0)

(0,0,0,0)

(3,0,0,4)

. في CSR تكون data=[5,1,2,3,4] وindices=[0,3,2,0,3] وindptr=[0,2,3,3,5]. الصف

2

فارغ لأن indptr[2]=indptr[3]=3 وnnz=5. والضرب في

(1,1,1,1)

يجمع كل صف فيعطي

(6,2,0,7)

بـ

5

عمليات ضرب فقط. ولمصفوفة ثلاثية القطر بـ

n=1000

كشبكة تسعير بالفروق المنتهية

2{,}998

عنصرًا غير صفري من أصل

1{,}000{,}000

أي كثافة

0.30\%

. وتحتاج نحو

40

كيلوبايت في CSR مقابل

8

ميغابايت كثيفة. وفي بيانات حقيقية تشكل ارتباطات

55

سهمًا من ملف الأسعار المشترك مصفوفة

55\times55

. والاحتفاظ بالعناصر ذات

|\rho|>0.5

فقط يُبقي

249

من

3{,}025

أي

8.2\%

وتأخذ نسخة CSR

3.2

كيلوبايت مقابل

24.2

كثيفة. وعند

|\rho|>0.6

يبقى

4.3\%

فقط.

ثلاث قوائم: data وindices وindptr تصف مصفوفة CSR، وindptr[-1] هو عدد غير الأصفار.
ابنِ بـ COO واحسب بـ CSR: الثلاثيات سهلة التجميع والتخزين بالصفوف سريع للجداءات والحلول.
التفرق يفيد فقط إذا كان أغلبها أصفارًا: المصفوفة الكثيفة أفضل حين تكثر العناصر غير الصفرية.

المختبر: ما الذي يُقيَّم

عدّ غير الأصفار10 نقطة
كم قيمة في صف10 نقطة
كثافة شبكة10 نقطة
جداء متفرق15 نقطة
أي صيغة لأي عمل15 نقطة
نظام ثلاثي القطر10 نقطة
متى يفيد التفرق ومتى لا30 نقطة

المصفوفات المتفرقة

خزّن فقط ما ليس صفرًا

المختبر: ما الذي يُقيَّم

سجّل الدخول لتشغيل الكود الخاص بك.

المصفوفات المتفرقة

خزّن فقط ما ليس صفرًا

المختبر: ما الذي يُقيَّم

سجّل الدخول لتشغيل الكود الخاص بك.