跳跃表的实现和测试
LevelDB中一个核心的数据结构就是跳跃表,它是一个类似单向链表的结构但增加了多层指针进行跳跃,可以获得近似平衡树的效率,但是代码远远没有AVL等平衡二叉树实现复杂,所以尽管理论上跳跃表不是一个好算法,但是实现简单令他很多地方都很实用。
这面是一个跳跃表的结构。
这是实现代码和测试代码,非常简单,相比平衡树那是简单了多了去了。
发现一些内存泄露和内存越界,补上fix。
#include <stdlib.h> #include <stdio.h> #include <memory.h> #include <pthread.h> #include <time.h> #include <math.h> #include <limits.h> #define TIME(A,B) (double)(B-A)/CLOCKS_PER_SEC*1000 /* Skip List Level Limit, Level begin wth 0 */ #define MAX_SKIP_LEVEL 6 /* Level Weight for Calc node level */ #define LEVEL_W 6 /* Skip List Struct */ typedef struct skip_list_struct skip_list_t; struct skip_list_struct { int key; int value; int level; /* Level[i] have (i+1) pointer to */ skip_list_t* forward[MAX_SKIP_LEVEL]; }; /* Rand Node Level */ int rand_level() { int level= 0; int i= 0; /* Node which level more bigger, more less */ for(; i< MAX_SKIP_LEVEL-1; ++i) //for(; i< MAX_SKIP_LEVEL; ++i) 这里不对,可能生成超过MAX_SKIP_LEVEL的数 { level+= rand()%10> LEVEL_W? 1: 0; } return level; } /* Make a new node and init it */ skip_list_t* init_skip_list_node (int level, int key, int value) { skip_list_t* node= (skip_list_t *)malloc(sizeof(skip_list_t)); node->level= level; node->key= key; node->value= value; int i= 0; for (; i< MAX_SKIP_LEVEL; ++i) { node->forward[i]= NULL; } return node; } /* Insert or Update a value on Skip List */ int skip_list_write (skip_list_t* skip_list, int key, int value) { skip_list_t* update_node[MAX_SKIP_LEVEL]; skip_list_t* node= skip_list; int i= skip_list->level; for(; i>=0; --i) { while (node->forward[i]!= NULL && key> node->forward[i]->key) { node= node->forward[i]; } update_node[i]= node; } node= node->forward[0]== NULL? node: node->forward[0]; if (key== node->key) { node->value= value; } else { int level= rand_level(); node= init_skip_list_node(level, key, value); for (i= 0; i<= level; ++i) { node->forward[i]= update_node[i]->forward[i]; update_node[i]->forward[i]= node; } } } /* Delete a node on Skip List */ int skip_list_delete (skip_list_t* skip_list, int key) { skip_list_t* update_node[MAX_SKIP_LEVEL]; skip_list_t* node= skip_list; int i= skip_list->level; for(; i>=0; --i) { while (node->forward[i]!= NULL && key> node->forward[i]->key) { node= node->forward[i]; } update_node[i]= node; } node= node->forward[0]== NULL? node: node->forward[0]; if (key== node->key) { for (i= 0; i<= skip_list->level; ++i) { if (update_node[i]->forward[i] != node) { break; } update_node[i]->forward[i]= node->forward[i]; } free(node); return 0; // SUCCESS } else { return 1; // NO FOUND } } /* Search a key from Skip List */ int skip_list_search (skip_list_t* skip_list, int key) { skip_list_t* node= skip_list; int level= node->level; int i= level; for (; i>= 0; --i) { while (node->forward[i]!= NULL && key> node->forward[i]->key) { node= node->forward[i]; } } node= node->forward[0]== NULL? node: node->forward[0]; if (key== node->key) { return node->value; } else { return INT_MIN; } } int print_skip_list (skip_list_t* skip_list) { skip_list_t* node; int i= 0; for(; i< MAX_SKIP_LEVEL; ++i) { node= skip_list->forward[i]; printf("Level[%d]: ", i); while(node!= NULL) { printf("%d -> ", node->key); node= node->forward[i]; } printf("NULL\n"); } } // 增加释放内存的操作,避免内存泄露 /* Free All Nodes */ int free_skip_list (skip_list_t* skip_list) { skip_list_t* node= skip_list->forward[0]; skip_list_t* next_node; while (node!= NULL) { next_node= node->forward[0]; free(node); node= next_node; } free(skip_list); } int main(int argc, char *argv[]) { srand((unsigned)time(0)); int count= 0; int i= 0; /* Function Test */ printf("#### Function Test ####\n"); count= 20; printf("== Init Skip List ==\n"); skip_list_t* skip_list= init_skip_list_node(MAX_SKIP_LEVEL-1, INT_MIN, INT_MIN); // skip_list_t* skip_list= init_skip_list_node(MAX_SKIP_LEVEL, INT_MIN, INT_MIN); 多了一层所以会越界 for (i= 0; i<count; ++i) { skip_list_write(skip_list, i, i); } printf("== Print Skip List ==\n"); print_skip_list(skip_list); printf("== Search Key ==\n"); for(i= 0; i<count; ++i) { int key= rand()%(count+5); printf("Search [%d]: %d\n", key, skip_list_search(skip_list, key)); } printf("== Delete Key ==\n"); for(i= 0; i<count; ++i) { int key= rand()%(count+5); printf("Delete [%d]: %s\n", key, skip_list_delete(skip_list, key)? "NO FOUND": "SUCCESS"); } printf("== Print Skip List ==\n"); print_skip_list(skip_list); /* Performance Test */ printf("#### Performance Test ####\n"); clock_t start, finish; float time= 0; count= 100000; printf("== Insert 10^5 Items (%d Level) ==\n", MAX_SKIP_LEVEL); start = clock(); for(i= 0; i<count; ++i) { skip_list_write(skip_list, i, i); } finish = clock(); time= TIME(start, finish); printf ("Time: %f ms, Speed: %f Node/s\n", time, count/time*1000); printf("== Search 10^5 Items (%d Level) ==\n", MAX_SKIP_LEVEL); start = clock(); for(i= 0; i<count; ++i) { skip_list_search(skip_list, rand()%count); } finish = clock(); time= TIME(start, finish); printf ("Time: %f ms, Speed: %f Node/s\n", time, count/time*1000); // 增加释放内存 printf("#### Clear Memory ####\n"); free_skip_list(skip_list); return 0; } |
这是测试结果:
### Function Test ####
== Init Skip List ==
== Print Skip List ==
Level[0]: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> NULL
Level[1]: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 13 -> 15 -> 16 -> 17 -> 18 -> 19 -> NULL
Level[2]: 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 13 -> 15 -> 16 -> 17 -> 18 -> NULL
Level[3]: 1 -> 2 -> 6 -> 7 -> 8 -> 10 -> 13 -> 15 -> NULL
Level[4]: 1 -> 2 -> 7 -> 8 -> 10 -> NULL
Level[5]: NULL
== Search Key ==
Search [4]: 4
Search [13]: 13
Search [9]: 9
Search [23]: -2147483648
Search [8]: 8
Search [7]: 7
Search [22]: -2147483648
Search [5]: 5
Search [3]: 3
Search [15]: 15
Search [13]: 13
Search [15]: 15
Search [6]: 6
Search [22]: -2147483648
Search [7]: 7
Search [13]: 13
Search [14]: 14
Search [2]: 2
Search [6]: 6
Search [17]: 17
== Delete Key ==
Delete [15]: SUCCESS
Delete [5]: SUCCESS
Delete [13]: SUCCESS
Delete [10]: SUCCESS
Delete [20]: NO FOUND
Delete [11]: SUCCESS
Delete [14]: SUCCESS
Delete [16]: SUCCESS
Delete [10]: NO FOUND
Delete [16]: NO FOUND
Delete [9]: SUCCESS
Delete [23]: NO FOUND
Delete [6]: SUCCESS
Delete [8]: SUCCESS
Delete [21]: NO FOUND
Delete [4]: SUCCESS
Delete [9]: NO FOUND
Delete [22]: NO FOUND
Delete [20]: NO FOUND
Delete [1]: SUCCESS
== Print Skip List ==
Level[0]: 0 -> 2 -> 3 -> 7 -> 12 -> 17 -> 18 -> 19 -> NULL
Level[1]: 2 -> 3 -> 7 -> 17 -> 18 -> 19 -> NULL
Level[2]: 2 -> 3 -> 7 -> 17 -> 18 -> NULL
Level[3]: 2 -> 7 -> NULL
Level[4]: 2 -> 7 -> NULL
Level[5]: NULL
#### Performance Test ####
== Insert 10^5 Items (6 Level) ==
Time: 1196.923950 ms, Speed: 83547.500000 Node/s
== Search 10^5 Items (6 Level) ==
Time: 1196.629028 ms, Speed: 83568.085938 Node/s
调整MAX_SKIP_LEVEL和LEVEL_W两个常量,可以明显的观察到Speed的变化,自己实现一遍,比看很多遍代码理解深刻多了。
修改后的代码无泄露无越界了:
==1631==
==1631== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 5 from 1)
==1631== malloc/free: in use at exit: 0 bytes in 0 blocks.
==1631== malloc/free: 100,010 allocs, 100,010 frees, 6,400,640 bytes allocated.
==1631== For counts of detected errors, rerun with: -v
==1631== All heap blocks were freed — no leaks are possible.
建议继续学习:
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:P.Linux 来源: P.Linux Laboratory
- 标签: 跳跃表
- 发布时间:2013-02-28 23:36:44
- [67] Go Reflect 性能
- [65] Oracle MTS模式下 进程地址与会话信
- [62] 如何拿下简短的域名
- [60] 【社会化设计】自我(self)部分――欢迎区
- [60] android 开发入门
- [58] 图书馆的世界纪录
- [58] IOS安全–浅谈关于IOS加固的几种方法
- [54] 视觉调整-设计师 vs. 逻辑
- [48] 界面设计速成
- [47] 给自己的字体课(一)——英文字体基础