技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 跳跃表的实现和测试

跳跃表的实现和测试

浏览:1764次  出处信息

   LevelDB中一个核心的数据结构就是跳跃表,它是一个类似单向链表的结构但增加了多层指针进行跳跃,可以获得近似平衡树的效率,但是代码远远没有AVL等平衡二叉树实现复杂,所以尽管理论上跳跃表不是一个好算法,但是实现简单令他很多地方都很实用。

   这面是一个跳跃表的结构。

   Skip List

   这是实现代码和测试代码,非常简单,相比平衡树那是简单了多了去了。

   发现一些内存泄露和内存越界,补上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.


建议继续学习:

  1. 跳跃表    (阅读:1504)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1