المصفوفة المتناثرة Sparse Matrix

بسم الله الرحمن الرحيم



سنتعلم أخي الكريم في هذا الدرس كيفية انشاء
class واستخدامه في برنامجنا، كما ستتعرف
على
المصفوفة المتناثرة وكيفية معالجتها.


المصفوفة

المتناثرة أو مصفوفة الأصفار (
Sparse

Matrix ) :



لو ألقينا نظرة على المصفوفة التالية التي تحوي 6 صفوف و6 أعمدة وتتكون
من : 6x
6 = 36 عنصر :





سيتضح لنا من الوهلة الأولى أن أكثر عناصر هذه
المصفوفة
عبارة عن " أصفار " ؛ تسمى المصفوفة التي أكثر عناصرها أصفار
بـمصفوفة
الأصفار أو المصفوفة المتناثرة "
Sparse

Matrix " . ومن الصعب علينا تحديد ما إذا كانت المصفوفة عبارة عن
Sparse

Matrix أو لا .. ولكن يتضح لنا ذلك عن طريق النظر؛ ففي المصفوفة
السابقة
يوجد فقط 8 عناصر لا تساوي الصفر من أصل 36 عنصر،

بينما البقية كلها أصفار .
نعالج الـ
Sparse

Matrix بالتكنيك الذي سنشرحه في درسنا لتوفير المساحة في الذاكرة
حيث
نستطيع تخزين العناصر الغير مساوية للصفر فيها فقط ؛ وذلك من خلال
استخدام
مصفوفة وحيدة لكل عنصر من عناصرها يوجد 3 صفات هي : الصف والعمود
والقيمة
الخاصة به؛ ويتم ذلك عن طريق استخدامنا
لـClass كالتالي :




package Sparse_Matrix;

public class SM
extends Object {
private int row , col , val ;

//-----------<< SM constructor
>>------------------------
public SM (int
row1 ,int col1 ,int
val1 ) {
setrow(row1) ;
setcol(col1) ;
setval(val1) ;
}

//-----------<< Method to perform row
>>-----------------
public int setrow(
int row1 ){
return row = row1 ;
}
//-----------<< Method to perform column

>>--------------
public int setcol(
int col1 ){ return col =
col1 ;
}
//-----------<< Method to perform value
>>---------------
public int setval(
int val1 ){
return val = val1 ;
}
//-----------<< Method to Print
>>-----------------------
public String Print() {
return ( row +"t"+
col +"t"+ val +"n")

;
}
}


ولكن يجب أن نراعي هنا أن ترتيب العناصر في هذه
المصفوفة
الوحيدة سيكون تابع لأحد هذه الصفات وهو الصف " row " و لابد من أن
يكون
تصاعدياً ..

إذن .. يتضح لدينا أن تعريف الـ
Sparse

Matrix كما هو موجود في قاموسنا كالتالي :
مصفوفة ذات بعد واحد تحوي الكثير من العناصر
المتشابهة ،
والتي غالباً ما تساوي صفر، لكل عنصر فيها ثلاث صفات : الصف ، العمود ،
والقيمة
التي تسند إليه .

*
Sparse_Matrix : a set of triples < row , col , value > , where
row & column
are integers & from a unique combination , & value comes
from the set item .

* Sparse_Matrix Create(max_row , max_col) ::= return a

Sparse_Matrix that can hold up to max_item = max_row X max_col
,&
whose maximum row size is max_row , & whose maximum
column size is
max_col.

ومن هنا نستطيع إعادة رسم الـ
Sparse

Matrix كما في الشكل التالي :




حيث أن a[0].row تحتوي عدد الأسطر الكلي
للمصفوفة الأصلية ( في هذا المثال = 6 ) , كذلك a[0].col فهي تحوي عدد
الأعمدة
الكلي للمصفوفة الأصلية ( في هذا المثال = 6 ) , وأيضاً a[0].value عدد
العناصر
الغير مساوية للصفر فقط ( في هذا المثال = 8 ) .
ولكي نعرف رقم الصف لأي عنصر ننظر لـ Field row , وبالمثل إذا
أردنا أن
نعرف رقم العمود فننظر لـ Field col وستكون قيمة هذا العنصر
مخزنة في
Field value . والثلاثي < row , col , value > سيكون مرتب
في المصفوفة
على حسب الصفوف " تصاعدياً " كما ذكرنا سابقاً ..
ولكن كيف نستطيع كتابة شيفرة لإنشاء هذه المصفوفة بلغة الجافا
؟ هذا ما سنعرفه ان شاء الله خلال الأسطر
التالية :



1) في البداية نقوم بعمل ملف ونسمّيه:
Sparse_Matrix مثلاً كما اعتمدنا في هذا المثال.
2) ثم نقوم بعمل كلاس نسميّه SM ونخزّنه في الملف السابق الذكر بعد أن
نعمل فيه
package Sparse_Matrix ونكتب في هذا الكلاس الكود السابق.
3) ثم نقوم بعمل Application ونضع فيه إستدعاء

للكلاس السابق أي : import Sparse_Matrix.SM .. ونكتب فيه
شيفرة لمعالجة المصفوفة المتناثرة بالتسلسل التالي:

• 
  
  سنفترض في مثالنا الحالي أن
  المصفوفة
  مكوّنة من 3 صفوف و3 أعمدة ..
  
• 
  
  وبعد ذلك نسمح للمستخدم بإدخال
  العناصر
  كمصفوفة عادية شريطة أن تكون أكثرها مساوية للصفر ونطبع المصفوفة
  بالطريقة
  التقليدية العادية.
  
• 
  
  ثم
  نقوم بإنشاء الـ
  Sparse
  Matrix ؛ نخزّن في البداية عدد الصفوف الكلي وعدد الأعمدة الكلي
  في كل
  من a[0].row و a[0].col .. ثم نضع عداداً = 1 كفهرس لكي نبدأ
  التخزين ..
  
  
• 
  
  نقوم بعمل Loop يمّر على كل
  عناصر
  المصفوفة العادية ويسأل ما إذا كان هذا العنصر مساوياً للصفر أما لا ؟
  
  إذا اتضح أن العنصر لا يساوي الصفر .. نقوم بتخزين رقم الصف الموجود
  فيه هذا
  العنصر وكذلك رقم العمود ثم نخزّن قيمة العنصر باستخدام العداد الذي
  جعلنا
  قيمته =1 كفهرس لأول عنصر يقابلنا غير مساوي للصفر .. ثم نزيد قيمة
  العداد
  بواحد لكي يفهرس العنصر المخزن الجديد .. وهكذا إلى أن ننتهي من جميع
  عناصر
  المصفوفة الأصلية .
  
• 
  
  الآن قمنا بتخزين جميع القيم
  الغير
  مساوية للصفر في الـ
  Sparse
  Matrix ولكن يتبقى Field واحد لم نخزّن به شئ .. أتعلمون ما هو ؟
  
  إنه الـ Field الخاص بعدد العناصر الغير مساوية للصفر في المصفوفة
  الأصلية
  (a[0].val ) .. ونستطيع معرفة عدد العناصر الغير مساوية للصفر من
  خلال العداد
  الذي فهرس العناصر ..
  ولكن نلاحظ هنا أن هذا العداد داخل Loop عندما انتهى التخزين قد
  زادت قيمته
  بواحد على عدد العناصر الغير مساوية للصفر؛ فيجب علينا أن نقوم
  بانقاص قيمته
  بمقدار واحد ثم نخزنها في a[0].val ...
  
• 
  
  الآن
  نستطيع نقوم
  بطباعة المصفوفة المتناثرة الناتجة لدينا.
  

وأليك الشيفرة كاملة:









import Sparse_Matrix.SM;
import javax.swing.*;

public class Sparse_MatrixO
{
public static void main
(String
args[])
{
int Matrix [][] ;
int i , j , q ,count =
1 ;
SM SparseMatrix ;
SparseMatrix= new

SM(0,0,0);
String x,output="";
output+="The Normal Matrix :n";
JTextArea outputarea = new JTextArea(10,20);
Matrix = new int]3]]3];
//-----------<< To Read & Print
Normal Matrix
>>-------------------
for(i=0

; i<3 ; i++){
for(j=0
; j<3 ; j++){
x=JOptionPane.showInputDialog("plz.
Enter
the value of element n");
q = Integer.parseInt(x) ;
Matrix[i][j] = q ;
output += Matrix[i][j] +"t"
;
if ( Matrix[i][j] !=
0 ) count++ ;
} // end of j Loop
output += "n" ;
} // end of i Loop
//-----------<< To Make & Print Sparse_Matrix

>>-------------------
output +="n The Sparce_Matrix
:nrowtcoltvaluen--------------------------------------------------n"

;
SparseMatrix.setcol(3);
SparseMatrix.setrow(3);
SparseMatrix.setval(count-1);
output += SparseMatrix.Print() ;
for(i=0

; i<3 ; i++){
for(j=0
; j<3 ; j++){
if ( Matrix[i][j] !=
0 ) {
SparseMatrix.setcol(j);
SparseMatrix.setrow(i);
SparseMatrix.setval(Matrix[i][j]);
output += SparseMatrix.Print()
;
} // end of if
} // end of j Loop
} // end of i Loop

outputarea.setText(output);
JOptionPane.showMessageDialog(null,outputarea,"Sparse_Matrix",
JOptionPane.INFORMATION_MESSAGE);
System.exit(0);
}
}



طبعاً، في برنامجنا المتواضع أدخلنا
العناصر عنصراً عنصراً، وهي طريقة غير عملية بتاتاً مع التطبيقات
الكبيرة، حيث
أننا في التطبيقات الكبيرة نخزن المصفوفة في ملف ونقوم بقراءة عناصرها
منه.

وهكذا .. نكون قد وفرنا الذاكرة لدينا عند استخدام مثل هذه المصفوفات
في حل
المشكلات الكبيرة .