- 浏览: 442781 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (158)
- J2SE (15)
- c/c++ (17)
- linux & ubuntu (20)
- js (18)
- algorithm (21)
- android (1)
- software (3)
- svn (1)
- db (6)
- other (19)
- css (5)
- go (1)
- html 5 (3)
- computer science (1)
- php (3)
- 创业 (8)
- EJB & jboss (1)
- TDD (1)
- jsp & servlet (2)
- http, tcp & ip (2)
- hibernate (1)
- json (1)
- 乐 (2)
- ps (2)
- netbeans (1)
- extjs (2)
- eclipse (4)
- 项目管理 (1)
- varnish (2)
- study abroad (1)
- python (1)
- erlang (1)
- math (1)
- shell (1)
- assembly (4)
- lucene (1)
- web (1)
- http (1)
- tcp & ip (1)
最新评论
-
yiguxianyun:
...
css li 不换行 -
stdayong:
...
netbeans 中使用 maven -
程序猿_星:
为啥会中文乱码啊
servlet 以 gzip 格式返回数据 -
huanhuan519:
感谢分享~
gdb 调试工具 -
heyl1234:
写过些js,对css还不熟。谢谢~
css li 不换行
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); }
------
发表评论
-
c - linkedlist
2012-05-10 14:52 1080c - linkedlist store ordere ... -
c - word counter (binary-tree)
2012-05-09 14:17 1723c - word counter (binary-tree) ... -
c - pointer is also pass by value
2012-05-09 14:13 969c - pointer is also pass by ... -
find palindromic-prime in pi
2012-04-26 18:32 1845find palindromic-prime in pi ... -
c #define
2012-04-08 13:29 2103c #define macro substitu ... -
c static
2012-04-04 21:59 1235c static static external ... -
c extern
2012-04-04 21:53 1152c extern extern, used to de ... -
int to string by specified base
2012-04-03 22:15 1076int to string by specified base ... -
random select
2011-08-28 01:00 1204random select problem: ... -
max sub_sequence - c
2011-08-10 01:02 1072max sub_sequence - c /* ... -
binary search - c
2011-08-06 12:07 1089binary search - c (simple) ... -
bit_array - simple use
2011-05-28 23:47 1006bit array,use less memory to de ... -
linux c udp
2011-04-01 18:02 2090linux 下可用 c 进行 udp 通信,使用 server ... -
linux c tcp
2011-04-01 18:00 3062linux 下可用 c 进行 tcp 通信,使用 server ... -
gdb 调试工具
2011-02-21 17:20 3313gdb 调试工具 gdb 概 ... -
linkedlist - java 简单实现
2011-02-11 21:29 1592linked list 链表, - ... -
queue (用 java 简单实现)
2011-02-03 01:45 4047queue ------ 结构 线性存 ... -
Medians and Order Statistics (次序统计)
2011-01-03 14:36 2827Medians and Order Statistics - ... -
counting sort
2011-01-02 20:36 1562counting sort ------ counting ... -
quick sort
2011-01-01 20:26 1188quicksort ------ quicksort ove ...
相关推荐
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...
数据结构昆明2-1프로그램스 컴파일 $ javac lab.java LabTest.java 실행 $ java LabTest 주어진输入으로실행 $ java Lab...实验03 S(稀疏矩阵)의된Java의된가로아래과제 SparseMatrix Add(SparseMatrix b); 多项
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 ...
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 ...
* [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]...
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 ...
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 ...
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 ==================...
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的列变为行所得到的新矩阵。 #### 五、链表 ...
- 稀疏双精度矩阵(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 ...
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 ...