`

sparse data structure - matrix

 
阅读更多

sparse data structure

 

sparse data structure - means most element are empty(or have a very same value), 

so we can try to use some better data structure to reduce memory use,

 

------

matrix

 

we can use 'header array' & 'link list' to represent matrix,

 

how to:

define a data structure to represent a element in matrix, the element include: x, y, value, next,

use a linked list to store the elements of a column, in order of increasing x, 

use a header array to store the first element's pointer of each column,

 

memory:

only exists element will use memory,

 

search time:

in matrix of size a * b, the max count is Nmax, and the actural count is N elements, 0 <= N <= Nmax,

then the time to search an element by (i,j) is:

N/2b

or

a*t/2 (t = N/Nmax,Nmax = a * b)

 

drawback:

the search/insert/delete/update operation take a little longer time, than the original matrix(two-dimensional array),

 

------

code

 

#include <stdio.h>
/**
 * (sparse data structure - use less memory to store element)
 * matrix might be a sparse data structure, we can use head array & linked list to represent matrix, this might free a lot memory,
 */

/** data struct for each element in link list */
struct matrix_ele { 
	int x,y,value;
	struct matrix_ele *next;
};
typedef struct matrix_ele matrix_ele;

/**
 * add element to matrix,
 * @param colheader
 	store pointer of all column's first element,
 * @param me_new
 	pointer of new element to insert,
 * 
 * @return
 	1 means add the new element, 0 means update the value of old element,
 */

int matrix_add(matrix_ele **colheader, matrix_ele *me_new) {
	matrix_ele *me = *(colheader + me_new->y);
	if(me == NULL) { // linked list is empty
		*(colheader + me_new->y) = me_new;
		return 1;
	} else { // linked list is not empty
		matrix_ele *me_pre = NULL;
		for(; me != NULL; me = me->next) {
			if(me->x == me_new->x) { // element already exists,
				me->x == me_new->x;
				return 0;
			} else if(me->x > me_new->x) {
				if(*(colheader+me_new->y)==me) { // replace the first in linked list,
					*(colheader+me_new->y)=me_new;
					me_new->next = me;
					me->next = NULL;
				}
				else { // the one replaced is not first in linked list,
					me_new->next = me;
					me_pre->next = me_new;
				}
				return 1;
			} else {
				me_pre = me; // record previous ele in linked list,
			}
		}

		// new element has largest x, put it at the end of linked list,
		me_pre->next = me_new;
		return 1;
	}
}

/**
 * delete element from matrix,
 * @param colheader
 	store pointer of all column's first element,
 * @param me_new
 	pointer of new element to delete,
 * 
 * @return
 	1 means delete, -1 mean the element does not exists,
 */

int matrix_del(matrix_ele **colheader, matrix_ele *me_del) {
	matrix_ele *me = *(colheader + me_del->y);
	if(me == NULL) { // linked list is empty
		return -1;
	} else { // linked list is not empty
		matrix_ele *me_pre = NULL;
		for(; me != NULL; me = me->next) {
			if(me->x == me_del->x) { // element found
				me->x == me_del->x;
				if(me_pre == NULL) { // deleted element is the first element in linked list
					*(colheader + me_del->y) == me_del->next;
				} else {
					me_pre->next = me->next;
				}
				me == NULL;
				me_del == NULL;
				return 1;
			} else if(me->x < me_del->x) {
				me_pre = me; // record previous ele in linked list,
			} else { // not found
				return -1;
			}
		}
	}
}

/**
 * search element in the matrix,
 * equal time: N/2b, (N is the total count,b is count of column)
 */
int matrix_search(matrix_ele **colheader, int x, int y) {
	matrix_ele *me = *(colheader+y);
	for(; me != NULL; me = me->next) {
		if(me->x == x)
			return me->value;
	}
	return -1;
}

int main() {
	int row = 10,col = 20;
	matrix_ele *colheader[20] = {};
	int i;
	for(i = 0;i<col;i++) { // init pointer to NULL, this is necessary, if not init, the init value might not be NULL,and bug might happen,
		colheader[i] = NULL;
	}
	matrix_ele e_1_1 = {1,1,101,NULL};
	matrix_ele e_3_1 = {3,1,301,NULL};
	matrix_ele e_4_1 = {4,1,401,NULL};
	matrix_ele e_3_2 = {3,2,302,NULL};
	matrix_ele e_6_2 = {6,2,602,NULL};
	matrix_ele e_7_2 = {7,2,702,NULL};

	// add
	matrix_add(colheader, &e_1_1);
	matrix_add(colheader, &e_3_1);
	matrix_add(colheader, &e_4_1);
	matrix_add(colheader, &e_3_2);
	matrix_add(colheader, &e_6_2);
	matrix_add(colheader, &e_7_2);

	// search
	int v_1_1 = matrix_search(colheader, 1, 1);
	printf("expect: %d,\tactural: %d,\n",101,v_1_1);

	int v_3_1 = matrix_search(colheader, 3, 1);
	printf("expect: %d,\tactural: %d,\n",301,v_3_1);

	int v_4_1 = matrix_search(colheader, 4, 1);
	printf("expect: %d,\tactural: %d,\n",401,v_4_1);

	int v_3_2 = matrix_search(colheader, 3, 2);
	printf("expect: %d,\tactural: %d,\n",302,v_3_2);

	int v_6_2 = matrix_search(colheader, 6, 2);
	printf("expect: %d,\tactural: %d,\n",602,v_6_2);

	int v_7_2 = matrix_search(colheader, 7, 2);
	printf("expect: %d,\tactural: %d,\n",702,v_7_2);

	int v_4_2 = matrix_search(colheader, 4, 2);
	printf("expect: %d,\tactural: %d,\n",-1,v_4_2);

	int v_x_x = matrix_search(colheader, 3, 9);
	printf("expect: %d,\tactural: %d,\n",-1,v_x_x);
	
	// test delete
	int d_3_1 = matrix_del(colheader, &e_3_1);
	v_3_1 = matrix_search(colheader,3,1);
	printf("expect: %d,%d,\tactural: %d,%d,\n",1,-1,d_3_1,v_3_1);

	matrix_ele e_x_x = {3,9,309,NULL};
	int d_x_x = matrix_del(colheader, &e_x_x);
	v_x_x = matrix_search(colheader,3,9);
	printf("expect: %d,%d,\tactural: %d,%d,\n",-1,-1,d_x_x,v_x_x);
}
 

 

------


分享到:
评论

相关推荐

    数据结构Advanced-Data-Structures

    Data structure 1 Linked data structure 3 Succinct data structure 6 Implicit data structure 8 Compressed data structure 9 Search data structure 10 Persistent data structure 11 Concurrent data structure...

    Data-Structure:2-1

    数据结构昆明2-1프로그램스 컴파일 $ javac lab.java LabTest.java 실행 $ java LabTest 주어진输入으로실행 $ java Lab...实验03 S(稀疏矩阵)의된Java의된가로아래과제 SparseMatrix Add(SparseMatrix b); 多项

    GNMF_Multi.m

    Recently, many sparse nonnegative matrix factorization (NMF) algorithms have achieved advanced performance for hyperspectral unmixing because they overcome the difficulty of absence of pure pixels ...

    eccv_Real-Time Compresssive Tracking

    sparse measurement matrix. The tracking task is formulated as a binary classification via a naive Bayes classifier with online update in the compressed domain. The proposed compressive tracking ...

    LeetCode最全代码

    * [Data Structure](https://github.com/kamyu104/LeetCode#data-structure) * [Math](https://github.com/kamyu104/LeetCode#math) * [Two Pointers](https://github.com/kamyu104/LeetCode#two-pointers) * [Sort]...

    Elegant SciPy The Art of Scientific Python

    Solve sparse matrix problems, including image segmentations, with SciPy’s sparse module Perform linear algebra by using SciPy packages Explore image alignment (registration) with SciPy’s optimize ...

    Elegant SciPy: The Art of Scientific Python

    Solve sparse matrix problems, including image segmentations, with SciPy’s sparse module Perform linear algebra by using SciPy packages Explore image alignment (registration) with SciPy’s optimize ...

    svm matlab版本

    The instance_matrix must be a sparse matrix. (type must be double) These codes are prepared by Rong-En Fan and Kai-Wei Chang from National Taiwan University. Additional Information ==================...

    算法导论--Introduction.to.Algorithms

    15.2 Matrix-chain multiplication 370 15.3 Elements of dynamic programming 378 15.4 Longest common subsequence 390 15.5 Optimal binary search trees 397 16 Greedy Algorithms 414 16.1 An activity-...

    算法导论英文版

    l5.2 Matrix-chain multiplication 331 l5.3 Elements of dynamic programming 339 15.4 Longest common subsequence 350 l5.5 Optimal binary search trees 356 l6 Greedy Algorithms 370 l6.l An activity-...

    数据结构基本英语词汇

    - **Sparse Matrix**(稀疏矩阵):大多数元素为零的矩阵,为了节省空间,会采用特殊的存储方法。 - **Transposed Matrix**(转置矩阵):矩阵A的转置是将A的行变为列,A的列变为行所得到的新矩阵。 #### 五、链表 ...

    第三章 MATLAB程序设计基础.doc

    - 稀疏双精度矩阵(Sparse matrix):高效存储大量零值的矩阵。 - 单元数组(Cell array):可以存储不同类型的变量。 - 结构数组(Structure array):类似于C语言的结构体,包含多个字段。 - Java类(Java class)...

    大维随机矩阵的谱分析理论

    7. 1 Sparse Matrix and Hadamard Product 16 7.2 Truncation and normalization 168 7. 2. 1 Truncation and Centralization 169 7. 3 Proof of Theorem 7.1 by the Moment Approach 172 8 Convergence Rates of ...

    SPEECHWATERMARKING BASED ON ROBUST PRINCIPAL COMPONENT ANALYSIS AND FORMANT MANIPULATIONS

    As the spectrogram of speech has a relatively sparse structure, the core information of speech is extracted into a sparse matrix using RPCA so that formants can be estimated with Linear Prediction ...

Global site tag (gtag.js) - Google Analytics