This is the 10th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Preface:

We simply learned, in front of the array and several simple compression storage, today we learn the sparse matrix, sparse matrix storage method only store non-zero elements, there are three main tuples and curb the two methods, then I will try to let everybody understand this stuff, didn’t learn it doesn’t matter, bloggers feel this thing is not so important, is, of course, only for myself, Because I haven’t come across a project that says that optimization should be done using sparse matrices. Hahaha, maybe bloggers don’t do enough projects. Ok, let’s get to the topic.

Once a day to prevent decadence

(Double eleven, others chop hands, we are poor in eating soil 🤣🤣🤣)

1. What is sparse matrix

In a matrix, if the number of elements with value of 0 is far more than the number of non-0 elements, and the distribution of non-0 elements is irregular, the matrix is called sparse matrix. Conversely, a matrix is said to be dense if the number of non-zero elements is in the majority. Define the density of the matrix as the total number of non-zero elements over the total number of all elements of the matrix. Is defined as the official matrix china-africa zero element number is far less than the total number of matrix element, and the distribution of the non-zero elements, and often think matrix china-africa matrix on the total number of zero elements than all the elements of the total value less than or equal to 0.05, says the matrix of the sparse matrix (sparse matrix), the ratio is called the consistency of the matrix; In contrast, if the distribution of non-zero elements is regular (such as triangular matrix, lower triangular matrix, diagonal matrix), the matrix is called a special matrix. A more basic definition is that most elements of a matrix are zero, and you can use zero elements to save a lot of storage, computation, and program running time. There is a matrix in which the elements are irregular and everything else is zero. 5% of the matrix is non-zero and 95% of the matrix is zero.

2. Triplet representation of sparse matrix

A triple is a set of the form ((x, y), z) (that is, a triple is such that its first projection is also an even), often abbreviated to (x, y, z). Triples are concepts in data structures, a common foundation course for computer science. A compact form used to store sparse matrices, also known as triplet tables. Assuming that triple table is represented by sequential storage structure, a compressed storage method of sparse matrix is obtained, namely triplet sequential table, or triplet table for short. A triplet is a group of three elements, the first two are the row and column numbers of a two-dimensional array, and the last number represents the value of the two-dimensional array, abba abba 😜😜😜

Note: the blogger lists the starting line numbers as 1 for convenience, some of them as zero

H > #include<stdio.h> #include<stdio.h> #include<stdlib.h> #define m 6 #define n 6 #define MAXSIZE 100// Assume the maximum number of non-zero elements is 100 Typedef struct{int I,j; // row subscript and column subscript int e; // element value}node; typedef struct{ node data[MAXSIZE+1]; Data [0] int mu,nu,tu; }TSMatrix;}TSMatrix;}TSMatrix; Int CreTSMatrix(TSMatrix *M,int a[M][n]) {int I,j,k=1; // loop over I for row, j for column, k for triple subscript, starting at 1 (*M). Mu = M; // Total number of assignment lines (*M).nu=n; For (I =0; i<m; i++) { for(j=0; j<n; j++) { if(a[i][j]! {(*M).data[k]. I = (I +1); Data [k]. J = (j+1); Data [k]. E = a[I][J]; // record the element value k++; }}} (*M). Tu =k-1; // Return 1; } int PrintTSM TSMatrix (M) / / output three yuan matrix {the if (M.m u = = 0 | | M.n u = = 0) / / figure out whether ranks of 0 {printf (" matrix is empty! \n"); return 1; } printf(" rows = %d, columns = %d\n", m.mu, m.nu); If (m.tu ==0) {printf(" The matrix is zero! \n"); return 1; } int k; for(k=1; k<=M.tu; K++) / / to iterate over output printf (" % d % d % d \ \ t t \ n ", m. ata [k]. I, m. ata [k]. J m. ata [k]. E); return 1; } // main function test int main() {TSMatrix M; int i,j; Int a [m] [n] = {,0,6,0,12,0 {0}, {0,4,0,0,0,0},,0,0,0,2,0 {0}, {0,0,0,0,0,0},,0,0,0,0,9 {0}, {0,0,6,0,0,0}}; Printf (" print out the original matrix: \n"); for(i=0; i<m; i++) { for(j=0; j<n; j++) printf("%3d",a[i][j]); printf("\n"); } CreTSMatrix(&M,a); Printf (" ternary matrix is: \n"); PrintTSM(M); return 0; }Copy the code

Effect demonstration:

Note: The disadvantage of the triplet order list is that it cannot be randomly accessed. If a non-zero element is accessed by the row number, it needs to be searched from the beginning.

3. The cross chain representation of sparse matrix is briefly introduced

It can flexibly insert new non-zero elements and delete new zero elements generated by operation, and realize various operations of matrix. In a cross linked list, each non-zero element of a matrix is represented by a node that has two fields in addition to (row, row, value) : (Right: used to link the next non-zero element in the same row; Down: used to link the next non-zero element in the same column. , draw a node diagram for you to see:

Cross link logic diagram:

typedef struct node { int row,col; Int value; Struct OLNode *right, *down; }node, *List; typedef struct{ List *rhead, *chead; Int mu,nu,tu; // The number of rows, columns, and non-zero elements of the sparse matrix}HeadList;Copy the code

Specific implementation code is not due to time relationship blogger wrote back, specific implementation logic is to each line each column as a linked list of nodes, two linked list, one is line, which is a column, this article represents an array of nodes above the line of a column, or understand for line and column number, then a node structure is to be placed inside the value. Blogger has the opportunity to write out, the specific implementation and some cross chain operation alone to write an article, and learn data structure, understanding can, the exam will not test, test, see the blogger this logic, also won’t say completely won’t. Sometime the blogger will publish a special article on sparse matrix cross chains.

Conclusion:

Array of chapters we have almost completely learned, actually is not very difficult, we need patience to learn, bloggers in the article, also can see a lot of video, data, knock on the code, but I learned that long, feeling really learn anything, logic must learn to understand, even if you don’t write, examination, as long as you will be the logical language, also not completely don’t understand, At the very least, you can read it. You can’t read logic you can’t read it. Creation is not easy to like, follow, comment, favorites.