تدوير المصفوفة المتناثرة [ Sparse Matrix(2) ]

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

 

تدوير المصفوفة المتناثرة ( Transposing Sparse Matrix )



بعد أن تعرفنا على المصفوفة المتناثرة ( مصفوفة الأصفار ) [ Sparse_Matrix ] نتعرف الآن على طريقة تدويرها ؛ ونعني بتدويرها:  تبديل الصفوف بالأعمدة في السجل.
بمعنى أن كل عنصر a[i][j] في المصفوفة المتناثرة سيؤول إلى العنصر b[j][i]  في مصفوفة التدوير المقابلة لها. والشكل التالي يوضح التدوير للمصفوفة المتناثرة التي اعتمدناها في شرح الدرس السابق :



لنفكر قليلاً كيف يمكننا فعل ذلك بمصفوفة ذات بعد واحد ؟

أول ما سنستنجد به هو ترتيب المصفوفة المتناثرة ؛ حيث أنها مرتبة ترتيباً تصاعدياً عن طريق الصفوف ..

وهذا صحيح ولكن لنفكر للحظة كيف لنا استخدام هذا الترتيب التصاعدي في الصفوف كي نصل إلى ترتيب تصاعدي آخر ولكن عن طريق الأعمدة ؟



لنرى معاً :

لو قلنا أنه بما أننا فهرسنا مصفوفة الأصفار تصاعدياً باستخدام الصفوف ؛ فإننا سنستفيد من هذا الترتيب التصاعدي في عملية تدوير المصفوفة كما توضح الخوارزمية التالية :


For each row i

Take element < i , j , value > and store it as element < j , i , value > of the transpose ;



لو جدنا في هذه الطريقة أن الترتيب سيبقى تصاعدياً ولكن من ناحية الأعمدة - حيث أننا في مصفوفة التدوير بدلنا الصفوف بالأعمدة - وبذلك لن نحصل على مصفوفة مرتبة ترتيباً تصاعدياً من ناحية الصفوف !؛ ولو طبقنا الخوارزمية السابقة على المثال الذي شرحنا عليه مصفوفة الأصفار ؛ فسنحصل على التالي :

(0 , 0 , 15 ) ستصبح (0 , 0 , 15 )
( 0 , 3 , 22 ) ستصبح (3 , 0 , 22 )
(0 , 5 , -15 ) ستصبح ( 5 , 0 , -15 )
(4 , 0 , 91 ) ستصبح (0 , 4 , 91 )
(5 , 2 , 28 ) ستصبح (2 , 5 , 28 )
وهكذا



النتيجة: مصفوفة مرتبة تصاعدياً من ناحية الأعمدة ، بينما نحتاج إلى مصفوفة التدوير مرتبة تصاعدياً من ناحية الصفوف كما ذكرنا ذلك !!

الطريقة التي ستوصلنا إلى ترتيب تصاعدي جديد عن طريق الصفوف ، هي تثبيت العمود إبتداءاً من أصغر قيمة (صفر) والدوران حوله بجميع القيم الممكنة للصفوف (ابتداءاً من صفر إلى عدد الصفوف الكلي المخزن في a[0].row من مصفوفة الأصفار) ، وهكذا  لكل عمود على حدة ..

ربما تساعدك الخوارزمية التالية لمعرفة ديناميكية الحل :


For all elements in column j

 Place element < i , j , value > in element < j , i , value >  ;
 

لعمل ذلك ، سنستخدم Tow For Loops & If statement ولا ننسى أن نستخدم عداد جديد "currentb مثلاً " للفهرسة ، كما توضح الشيفرة التالية:

//----->------

void Transpose (sparse m[MAX_TERM] , sparse n[MAX_TERM] )

{

int i , j , k , currentb ;

k = m[0].val ; // total number of elements.

n[0].row = m[0].row ; // rows in n = columns in m .

n[0].col = m[0].col ; // columns in n = rows in m . 

n[0].val = k ;

if( k > 0 ){ /* non zero matrix */

 currentb = 1 ;

 for (i=0 ; i <= m[0].col ; i++ ) {

 /* transpose by the columns in m */

  for (j=1 ; j <= k ; j++ ) {

  /* find elements from the current column */

   if(m[j].col == i){

   /* element in curret column , add it to n */

    n[currentb].row = m[j].col ;

    n[currentb].col = m[j].row ;

    n[currentb].val = m[j].val ;

    currentb++ ;

   } // end if

  } // end j loop

 } // end i loop

 

 printf( "n**************nnTranspose of a Sparse_Matrix is : nrowtcoltvaluen------------n" );

 for ( i=0 ; i<= n[0].val ; i++ ){

  printf("%it",n[i].row );

  printf("%it",n[i].col );

  printf("%in",n[i].val );

  } // end i loop 

 } // end if 

} // end of function : Transpose.

 

 

الزمن الكلي لتنفيذ هذه الـ For Loops هو ببساطة ناتج ضرب عدد أعمدة مصفوفة الأصفار في عدد عناصرها ، وهو وقت قليل بالمقارنة مع وقت تدوير المصفوفة بطريقة تقليدية بدون استخدام الـ For Loops .

جرب هذه الشيفرة التي تعتبر تطبيق كلي لما تعلمناه في درسي مصفوفة الأصفار :

 

//------------------((( Sparse Matrix )))---------------

#include "stdio.h"

#define MAX_TERM 10

typedef struct {

   int row ;

   int col ;

   int val ;

   } sparse;

void Transpose (sparse m[MAX_TERM] ,sparse n[MAX_TERM] ) ;

void main()

{

sparse a[MAX_TERM] ,trans_a[MAX_TERM];

int b[3][3] ;

int i, j, count ;

printf("Plz. Enter the element one by one with press Enter :n");

for (i=0 ; i <3 ; i++ ) {

 for (j=0 ; j <3 ; j++ ) {

 scanf("%i",&b[i][j]) ;

 } // end j loop

} // end i loop

//------------>----------------

printf("n***************************nnNormal_Matrix is : n") ;

for (i=0 ; i <3 ; i++ ) {

 for (j=0 ; j <3 ; j++ ) {

 printf("%i t",b[i][j]) ;

 } // end j loop

printf("n") ;

} // end i loop

//------------>----------------

a[0].row=3 ;

a[0].col=3 ;

count=1;

for (i=0 ; i <3 ; i++ ){

 for (j=0 ; j <3 ; j++ ){

  if ( b[i][j]!= 0 ){

   a[count].row=i ;

   a[count].col=j ;

   a[count].val=b[i][j] ;

   count++;

  } // end if

 } // end j loop

} // end i loop

a[0].val=count-1 ;

printf("n***************nnSparse_Matrix is : nrowtcoltvaluen-----------n")
;

for ( i=0 ; i
 printf("%it",a[i].row) ;

 printf("%it",a[i].col) ;

    printf("%in",a[i].val) ;

}

//-----------<To Transpose Sparse_Matrix>------------

Transpose( a , trans_a);



//----->------

void Transpose (sparse m[MAX_TERM] , sparse n[MAX_TERM] )

{

int i , j , k , currentb ;

k = m[0].val ; // total number of elements.

n[0].row = m[0].row ; // rows in n = columns in m .

n[0].col = m[0].col ; // columns in n = rows in m . 

n[0].val = k ;

if( k > 0 ){ /* non zero matrix */

 currentb = 1 ;

 for (i=0 ; i <= m[0].col ; i++ ) {

 /* transpose by the columns in m */

  for (j=1 ; j <= k ; j++ ) {

  /* find elements from the current column */

   if(m[j].col == i){

   /* element in curret column , add it to n */

    n[currentb].row = m[j].col ;

    n[currentb].col = m[j].row ;

    n[currentb].val = m[j].val ;

    currentb++ ;

   } // end if

  } // end j loop

 } // end i loop

 

 printf( "n************nnTranspose of a Sparse_Matrix is : nrowtcoltvaluen---------n" );

 for ( i=0 ; i<= n[0].val ; i++ ){

  printf("%it",n[i].row );

  printf("%it",n[i].col );

  printf("%in",n[i].val );

  } // end i loop 

 } // end if 

} // end of function : Transpose.

 

 

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

السلام عليكم ورحمة الله وبركاته :)

 

 

 


Copyright © www.kettaneh.net