精华内容
下载资源
问答
  • Skip list

    千次阅读 2016-08-02 19:21:31
    skiplist 代码疑问:leveldb 和 redis 都使用了 skip list,它们为什么要使用 skip list?

    疑问:leveldbredis 都使用了 skip list,它们为什么要使用 skip list

    跳跃表(skiplist)是一种链表,它在链表的基础上增加了跳跃功能,使得在查找元素时,跳表能够提供 O(log N) 的时间复杂度。

    像红黑树这样的数据结构查找的时间复杂度也是 O(log N),但是相比实现一颗红黑树,跳跃表的实现要简单得多。

    我们通过下面单链表和跳跃表查找对比先来感受下跳跃表的优势。

    单链表

    图片标题

    下面这个就是跳跃表

    图片标题

    假设我们要查找17这个点,链表自然是顺序查找了。
    下图是用跳跃表查找17,过程跳过了3,7,12 这些点,这就是跳跃表的特点。

    图片标题

    一、什么是跳跃表

    概念

    跳跃表William Pugh 发明并于 1990 年 6 月 发表在 Communications of the ACM,文章题目为 Skip lists: a probabilistic alternative to balanced trees

    引用 William Pugh 的话:

    Skip lists are a data structure that can be used in place of balanced trees.
    Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

    跳跃表是一种可用于替换平衡树的数据结构。
    跳跃表使用概率均衡而非强制均衡,因此跳跃表的插入和删除比平衡树更简单快捷。

    组成

    • 表头(head):负责维护跳跃表的节点指针。
    • 跳跃表节点:保存着元素值,以及多个层。
    • :保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针,为了提高查找的效率,程序总是从高层先开始访问,然后随着元素值范围的缩小,慢慢降低层次。
    • 表尾:全部由 NULL 组成,表示跳跃表的末尾。

    那么,这个跳跃的功能是怎么实现的?
    为什么能够提供跟查找树一样的 O(log N) 时间复杂度?

    二、跳跃表数据结构

    节点

    struct Node {
      int key;
      int value;
      Node* forward_[1];  // 保存着指向其他节点的指针
    };

    skip list

    typedef struct List_* List;
    struct List_ {
      int level;
      Node* head;  // 头结点,负责维护跳跃表的节点指针
    };

    SkipList 的实现

    class SkipList {
     public:
      SkipList() : rnd_(0xdeadbeef) { NewList(); }
      ~SkipList() { FreeList(); }
    
      bool Insert(int key, int value);
      bool Delete(int key);
      bool Search(int key);
      void Print();
    
      enum { kMaxLevel = 16 };  // 最大层数
    
     private:
      void NewList();
      void FreeList();
    
      inline int GetMaxHeight() const { return list_->level; }
      inline void SetMaxHeight(int level) { list_->level = level; }
      void NewNode(int level, Node*& n);
      int RandomHeight();
    
      List list_;
      Random rnd_;  // 随机数生成器
    
      SkipList(const SkipList&);
      void operator=(const SkipList&);
    };

    随机数生成器

    这里使用了 leveldb 中的随机数生成器,也可以用标准库中的 rand() 函数

    // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
    // Use of this source code is governed by a BSD-style license that can be
    // found in the LICENSE file. See the AUTHORS file for names of contributors.
    
    #ifndef RANDOM_H
    #define RANDOM_H
    
    #include <stdint.h>
    
    // A very simple random number generator.  Not especially good at
    // generating truly random bits, but good enough for our needs in this
    // package.
    class Random {
     private:
      uint32_t seed_;
     public:
      explicit Random(uint32_t s) : seed_(s & 0x7fffffffu) {
        // Avoid bad seeds.
        if (seed_ == 0 || seed_ == 2147483647L) {
          seed_ = 1;
        }
      }
      uint32_t Next() {
        static const uint32_t M = 2147483647L;   // 2^31-1
        static const uint64_t A = 16807;  // bits 14, 8, 7, 5, 2, 1, 0
        // We are computing
        //       seed_ = (seed_ * A) % M,    where M = 2^31-1
        //
        // seed_ must not be zero or M, or else all subsequent computed values
        // will be zero or M respectively.  For all other values, seed_ will end
        // up cycling through every number in [1,M-1]
        uint64_t product = seed_ * A;
    
        // Compute (product % M) using the fact that ((x << 31) % M) == x.
        seed_ = static_cast<uint32_t>((product >> 31) + (product & M));
        // The first reduction may overflow by 1 bit, so we may need to
        // repeat.  mod == M is not possible; using > allows the faster
        // sign-bit-based test.
        if (seed_ > M) {
          seed_ -= M;
        }
        return seed_;
      }
      // Returns a uniformly distributed value in the range [0..n-1]
      // REQUIRES: n > 0
      uint32_t Uniform(int n) { return Next() % n; }
    
      // Randomly returns true ~"1/n" of the time, and false otherwise.
      // REQUIRES: n > 0
      bool OneIn(int n) { return (Next() % n) == 0; }
    
      // Skewed: pick "base" uniformly from range [0,max_log] and then
      // return "base" random bits.  The effect is to pick a number in the
      // range [0,2^max_log-1] with exponential bias towards smaller numbers.
      uint32_t Skewed(int max_log) {
        return Uniform(1 << Uniform(max_log + 1));
      }
    };
    
    #endif  // RANDOM_H_
    

    三、操作

    初始化

    void SkipList::NewList() {
      list_ = (List) malloc(sizeof(List_));
      assert(list_ != NULL);
    
      list_->level = 0;
      NewNode(kMaxLevel - 1, list_->head);
    
      for (int i = 0; i < kMaxLevel; i++) {  // 将每层 head 节点置空
        list_->head->forward_[i] = NULL;
      }
    }
    
    void SkipList::NewNode(int level, Node*& n) {
      n = (Node *) malloc(sizeof(Node) + level * sizeof(Node *));
      assert(n != NULL);
    }

    插入

    bool SkipList::Insert(int key, int value) {
      Node* update[kMaxLevel];
      Node* x = list_->head;
    
      for (int i = list_->level - 1; i >= 0; i--) {
        Node* next;
        while ((next = x->forward_[i]) && (next->key < key)) {
          x = next;
        }
    
        update[i] = x;
      }
    
      if (x->key == key) {  // 不允许重复 key
        return false;
      }
    
      int level = RandomHeight();  // 随机生成 level
      if (level > GetMaxHeight()) {
        for (int i = GetMaxHeight(); i < level; i++) {
          update[i] = list_->head;
        }
    
        SetMaxHeight(level);
      }
    
      // make node
      Node* newNode;
      NewNode(level, newNode);
      newNode->key = key;
      newNode->value = value;
    
      for (int i = 0; i < level; i++) {
        newNode->forward_[i] = update[i]->forward_[i];
        update[i]->forward_[i] = newNode;
      }
    
      return true;
    }

    插入数据过程请看下图:

    这里就回答了文章开始的时候提出的疑问 为什么能够提供跟查找树一样的 O(log N) 时间复杂度?
    我们每次在进行查询操作的时候,都会从最高一层开始找,由于链表是有序的,所以期望的时间复杂度是 O(log N),当然最坏情况下的时间复杂度是 O(N),不过这种情况通常不会遇到。

    图片标题

    再附一张来自 wikipedia 插入元素的 gif

    图片标题

    删除

    bool SkipList::Delete(int key) {
      Node* update[kMaxLevel];
      Node* x = list_->head;
      Node* next = NULL;
    
      for (int i = GetMaxHeight() - 1; i >= 0; i--) {
        while ((next = x->forward_[i]) && (next->key < key)) {
          x = next;
        }
    
        update[i] = x;
      }
    
      if (next->key != key)
        return false;
    
      // 删除每层的 key 节点
      for (int i = 0; i < GetMaxHeight(); i++) {
        if (update[i]->forward_[i] == next)
          update[i]->forward_[i] = next->forward_[i];
      }
    
      free(next);
    
      // 如果删除的是最大层的节点,需要重新维护跳跃表的层
      for (int i = GetMaxHeight() - 1; i >= 0; i--) {
        if (list_->head->forward_[i] == NULL) 
          list_->level--;
      }
    
      return true;
    }

    四、测试

    #include <iostream>
    #include <sys/time.h>
    #include "skiplist.h"
    
    int main()
    {
      struct timeval start, end;
      gettimeofday(&start, NULL);
    
      SkipList list;
    
      // 插入 key 为 1 ~ 100 的节点
      for (int i = 1; i <= 100; i++) {
        list.Insert(i, i);
      }
      list.Print();
    
      // 删除 key 为 20 的节点
      bool d_ok = list.Delete(20);
      if (d_ok) {
        std::cout << std::endl << "Delete OK\n\n";
        list.Print();
      }
    
      gettimeofday(&end, NULL);
      long time_used = end.tv_sec * 1000000 + end.tv_usec - start.tv_sec * 1000000 - start.tv_usec;
      printf("In %ld usec\n", time_used);
    
      return 0;
    }

    完整的代码在底部

    P.S. 下图是 William Pugh 文章中各算法查找、插入和删除的用时对比

    图片标题

    参考文献

    skip list 维基百科
    skiplists.pdf
    skip list in c++
    浅析 SkipList 跳跃表原理及代码实现
    Skip List(跳跃表)原理详解与实现 - ITeye技术网站

    skiplist 代码

    skiplist.tar.gz

    展开全文
  • Skip List

    2017-10-24 14:20:53
    Skip List 是什么我们常用数组和链表来组织数据,对于已排序的数据,数组的查询时间复杂度可以是Θ(lgn)Θ(lgn)(二分查找),插入和删除都是Θ(n)Θ(n)。链表提供了一种更加灵活的组织方式,插入和删除的时间复杂度是...

    Skip List 是什么

    我们常用数组和链表来组织数据,对于已排序的数据,数组的查询时间复杂度可以是Θ(lgn)(二分查找),插入和删除都是Θ(n)。

    链表提供了一种更加灵活的组织方式,插入和删除的时间复杂度是Θ(1),查询的时间复杂度是Θ(n)。

    平衡树是更好的方案,查询、插入、删除的时间复杂度都是Θ(lgn),但实现上比较复杂。

    Skip List作为性能和实现难度的一个折中,它的查询、插入、删除等主要操作时间复杂度也都是Θ(lgn),空间复杂度是Θ(n)。

    一个Skip List的结构如下图,除了数据域,每个节点还包括1个或多个域用来保存后续节点的位置。

    这里写图片描述

    从结构上看,Skip List就是带有层级结构的链表(节点都是排好序的),最下面一层(level-0)是所有节点组成的一个链表,依次往上,每一层都也都是一个链表。不同的是,它们只包含一部分节点,并且越往上节点越少。仔细的话你会发现,通过增加层数,节点上可以带有更多的信息,通过这些信息可以直接访问更远的节点(这也是Skip List精髓所在),就像跳过去一样,所以取名叫Skip List(跳表)。

    Skip List查询

    查询操作很简单,比如我们要找图中节点key为20的节点。

    1. 我们首先获取到头节点,从头检点的最高层开始(节点中的点表示指向节点的指针),下一个节点是17,很明显20>17所以应该在后面。继续往后结果是NULL那说明后面没有要找的节点了。
    2. 跳到下一层继续往后是25且20<25说明后面也没有我们要找的节点了。
    3. 再跳到下一层,往后就找到我们要的节点了。如果到最下面一层还找不到,那这个节点就肯定不在表中了(因为最低层包含所有节点)。

    这里写图片描述

    对比一下,如果只有一层(图中level-0),我们要找20这个节点是需要5次才能找到,但是加上层级,我们有了更远节点的信息,利用更远节点的信息缩小查找范围,这里例子中我们只需要2次就找到了。

    Skip List插入

    插入操作稍微复杂, 首先我们要找到插入位置,怎么找我们刚才已经描述过了。如下图所示,插入key为10的节点,插入点应该是节点9和节点12之间(紫色的线表示要更新的指向)。然后是插入节点10,其实就是链表的逐层插入。

    这里写图片描述

    这里的需要注意是,逐层插入需要知道节点在每一层的位置,如在level-2中,节点10前面应该是头结点,而后面应该是节点17。 因为查询操作得到的只是最后位置,所以通常需要一个临时的空间来记录这些信息。如果节点的高度超过超过了Skip List的最大层数,那么Skip List的层数相应的需要升高。如节点10的高度是4的话,根据Skip List的结构特点,那么层数需要提高到level-3。

    节点高度与Skip List的最大层数

    节点的高度可以理解为需要多少域来保存后续节点的信息,Skip List的层数跟结构中最高节点的高度相等。理想的SkipList结构(如图一)是第一层有所有的节点,第二层只有1/2的节点,且是均匀间隔的,第三层是1/4的节点,且是均匀间隔的…,那么理想的层数是lgnlgn。

    每一次插入一个新节点时,最好的做法就是根据当前表的结构得到一个合适的高度,插入后可以让Skip List的尽量的接近理想的结构,但是实现上这会非常的复杂。

    Pugh论文中提出的方法是根据概率随机为新节点生成一个高度,具体的算法如下:

    • 给定一个概率pp, 产生一个[0,1) 之间的随机数
    • 如果这个随机数小于pp,则高度加1

    虽然随机生成的高度会打破理想的结构,Pugh在论文中证明,这种结构依然有非常高概率可以使得时间复杂度为Θ(lgn)。

    通常我们还会约束Skip List的最大层数,公式:maxLevel= log 1/p n其中n表示节点总数。 根据Pugh论文中的结论,p为1/2或者1/4时,整体性能会比较好。(当p=1/2时,确定节点高度有的地方称为抛硬币的方法)。

    Skip List删除

    删除操作跟插入操作类似。 首先找到我们要删除节点的位置,在查找时使用临时空间记录节点在每一级的位置。 接着就是逐层的链表删除操作。 最后记住要释放空间。 删除节点之后,如果最高层没有节点存在,那Skip List的层数相应的需要降下来。 下图表示节点9的删除操作。

    这里写图片描述

    小结

    如果对链表的实现很熟悉,实现Skip List也很容易。本文没有具体代码,一方面我不想文章篇幅因为代码变得很大,另一方面网上已经有很多实现。关于复杂度分析,当p=1/2时或者理想结构下,很好分析。推广到一般情况,那么分析也会比较复杂,需要比较高的数学功底,有兴趣可以看看Pugh在论文,另外MIT的算法公开课教授对Skip List的讲解也非常棒。

    参考资料

    Skip List(跳跃表)原理详解与实现

    skip list跳跃表实现

    数据结构-skiplist(跳表)

    展开全文
  • SkipList

    2014-05-09 12:26:34
    1、什么是SkipList 当使用链表存放有序数据

    1、什么是SkipList

    当使用链表存放有序数据的时候,查找某个数据或者添加某个数据的复杂度是O(n),每次查找都需要顺序遍历。加快搜索的方法有哪些呢?想想数据库的设计思路,对,使用索引,利用空间换取时间。跳表基本上采用的就是这个思路。


    图1

    在最底层的链表中随机抽取一定是数量的节点作为索引,形成另一个链表。然后继续从新生成的链表中随机抽取点作为新的索引,继续形成另一个链表。将这个步骤继续多次。
    可以得到上面图中的结构。通过观察上面的图,可以发现越往上的链表越稀疏。如果对多叉树比较熟悉的话,可以将上面的结构立即为多叉树。因此可以猜测SkipList的时间复杂度是O(ogn)。

    来看看SkipList如何工作的。


    图2
    由于上层的链表十分稀疏,所以上层链表遍历的时候可以忽略掉底层链表中许多的元素。比如上面的图中,插入的数据是80的时候,从30到50可以把40忽略掉。如果链表中的数据规模达到一定地步,上层链表的一次遍历可以跳过的元素是相当可观的。就像二叉树一样,没经过一个节点都可以跳过当前元素的一般。而由于SkipList每层链表都是按照一定概率生成的,虽然不是像二叉树那样经过一个节点可以忽略一半元素,但是效果也还是不错的。

    2、SkipList中的概念

    2.1、Node

    每个节点有一个值,用于排序。并且有一个数组用于存放后面的节点。比如图1中,节点6的nexts数组大小是4, 数组的数据依次指向节点7,节点9,节点25,NIL节点。


    2.2、SkipList

    跳表中有一个head节点,同时设置一个level表示当前最大的层数。比如图2中,level = 4。

    而且每个跳表都有一个常量的MAX_LEVEL,链表层数无论如何增加也不能超过这个值。

    2.3、NIL

    NIL值用于表示比任何值都大。一般存放在每个链表的结尾。表示当前链表搜索可以结束了。

    3、SkipList的初始化

    An element NIL is given a key greater than any legal key. All levels of all skip lists are terminated with NIL.A new list is initialized so that the levelof the list is equal to 1 and all forward pointers of the list’s header point to NIL.
    (摘自论文  A Skip List Cookbook  Author: William Pugh)

    4、SkipList的搜索

    We search for an element by traversing forward pointers that do not overshoot the node containing the element being searched for (Figure 2). When no more progress can be made at the current level of forward pointers, the search moves down to the next level. When we can make no more progress at level 1, we must be immediately in front of the node that contains the desired element (if it is in the list).

    Search(list, searchKey)
    	x := list→header
    	-- loop invariant: x→key < searchKey
    	for i := list→level downto1 do
    		whilex→forward[i]→key < searchKey do
    			x := x→forward[i]
    	-- x→key < searchKey ≤x→forward[1]→key
    	x := x→forward[1]
    	if x→key = searchKey then returnx→value
    	else return failure

    5、SkipList的插入和删除

    To insert or delete a node, we simply search and splice.Figure 3 gives algorithms for insertion and deletion. A vector updateis maintained so that when the search is complete (and we are ready to perform the splice), update[i] contains a pointer to the rightmost node of level ior higher that is to the left of the location of the insertion/deletion. If an insertion generates a node with a level greater than the previous maximum level of the list, we update the maximum level of the list and initialize the appropriate portions of the update vector. After each deletion, we check if we have deleted the maximum element of the list and if so, decrease the maximum level of the list.

    Insert(list, searchKey, newValue)
    	localupdate[1..MaxLevel]
    	x := list→header
    	for i := list→level down to 1 do
    		whilex→forward[i]→key < searchKey do
    			x := x→forward[i]
    		update[i] := x
    	x := x→forward[1]
    	if x→key = searchKey then x→value := newValue
    	else
    		newLevel := randomLevel()
    		if newLevel > list→level then
    			for i := list→level + 1 to newLevel do
    				update[i] := list→header
    			list→level := newLevel
    		x := makeNode(newLevel , searchKey, value)
    		for i := 1 tonewLevel do
    			x→forward[i] := update[i]→forward[i]
    			update[i]→forward[i] := x

    Delete(list, searchKey)
    	local update[1..MaxLevel]
    	x := list→header
    	for i := list→level down to 1 do
    		while x→forward[i]→key < searchKey do
    			x := x→forward[i]
    		update[i] := x
    	x := x→forward[1]
    	if x→key = searchKey then
    		for i := 1 to list→level do
    			if update[i]→forward[i] ≠ x then break
    			update[i]→forward[i] := x→forward[i]
    		free(x)
    		while list→level > 1 and list→header→forward[list→level] = NIL do
    			list→level := list→level – 1	

    6、新插入节点随机层数算法

    randomLevel()
    	lvl := 1
    	while random() < p and lvl < MaxLevel do
    		lvl := lvl + 1
    	return lvl

    这里设置p为1/2。
    如果random()函数设计的足够好,那么每次random()产生的数据都有50%的概率小于1/2。也就是说层数为1的概率为100%,层数为2的概率为50%,层数为3的概率为25%,层数为4的概率为12.5%,依次衰减。所以可以看出越往上的链表,其中的节点数也就越少。

    7、java版本的实现

    import java.util.ArrayList;
    import java.util.List;
    
    
    public class Node<T extends Comparable<T>> {
    	private T value;
    	private List<Node<T>> nexts;
    	
    	public Node(){
    		this.value = null;
    		this.nexts = new ArrayList<Node<T>>(0);
    	}
    	
    	public Node(T value){
    		this.value = value;
    		this.nexts = new ArrayList<Node<T>>(0);
    	}
    	
    	public Node(int size){
    		this.value = null;
    		this.nexts = new ArrayList<Node<T>>(size);
    	}
    	
    	public void setValue(T value) {
    		this.value = value;
    	}
    	public T getValue() {
    		return value;
    	}
    	public void setNexts(List<Node<T>> nexts) {
    		this.nexts = nexts;
    	}
    	public List<Node<T>> getNexts() {
    		return nexts;
    	}
    }
    

    注意这里的nexts数组就是伪代码中的forward数组。

    public class SkipList<T extends Comparable<T>> {
    	public static final int MAX_LEVEL = 100;
    	// the head of the SkipList
    	private Node<T> head = null;
    
    	private int level = 0;
    	// initial of the SkipList
    	public SkipList() {
    		// 初始化头部
    		setHead(new Node<T>(MAX_LEVEL));
    
    		// 初始化head的nexts数组
    		for (int i = 0; i < MAX_LEVEL; i++) {
    			head.getNexts().add(null);
    		}
    		
    		// 设置深度
    		setLevel(1);
    	}
    
    	@SuppressWarnings("unchecked")
    	public void insert(T newValue) {
    		if (newValue == null) {
    			return;
    		}
    		// 更新数组
    		Node<T> update[] = new Node[MAX_LEVEL];
    		// 获得头部
    		Node<T> p = this.head;
    
    		int j = this.level - 1;
    		while (j >= 0) {
    			// 下一个节点不为NULL 并且  值小于newValue
    			while ((Node<T>) p.getNexts().get(j) != null
    					&& newValue.compareTo(((Node<T>) p.getNexts().get(j))
    							.getValue()) >= 0) {
    				p = (Node<T>) p.getNexts().get(j);
    			}
    			update[j] = p;
    			j--;
    		}
    
    		int newLevel = randomLevel();
    
    		if (newLevel > this.level) {
    			// 当newLevel大于当前的level时,设置更新数组中level到newLevel为head
    			for (int i = newLevel - 1; i > level - 1; i--) {
    				update[i] = this.head;
    			}
    
    			// 当newLevel大于当前的level时,需要更新当前level
    			this.level = newLevel;
    		}
    
    		Node<T> newNode = new Node<T>();
    		newNode.setValue(newValue);
    
    		for (int i = 0; i < newLevel; i++) {
    			newNode.getNexts().add(update[i].getNexts().get(i));
    			update[i].getNexts().set(i, newNode);
    		}
    		
    	}
    	
    	//获取随机层数
    	private int randomLevel() {
    		int level = 1;
    		while (Math.random() < 1.0 / 2.0 && level < MAX_LEVEL) {
    			level++;
    		}
    		return level;
    	}
    	public void setHead(Node<T> head) {
    		this.head = head;
    	}
    	public Node<T> getHead() {
    		return head;
    	}
    
    	public void setLevel(int level) {
    		this.level = level;
    	}
    
    	public int getLevel() {
    		return level;
    	}
    
    	public static void main(String[] args) {
    		SkipList<Integer> skip = new SkipList<Integer>();
    
    		for (int i = 0; i < 10; i++) {
    			skip.insert(new Integer(i));
    		}
    	}
    }
    





    展开全文
  • skip list

    千次阅读 2010-11-18 11:13:00
    list的操作:查找,插入,删除。有序链表1.如何构建一个skip list?

    list的操作:

    查找,插入,删除。

     

    有序链表

    link list

     

    上面链表是有序排列的,那么如果想查找某一个元素x,则可以如下操作

     

     

     

    如此以来,得到了p之前的元素均小于x,而p之后的元素均不小于x,p是不小于x的第一个元素节点指针.

     

    如果要按照顺序插入一个元素x,则可以如下操作

     

     

    删除操作,删除不小于x的第一个元素

     

     

    以上是顺序链表,而skip list能够在这三个操作上节省时间。将时间由原来的O(n)节省到O(log(n))。

    1.如何构建一个skip list?

    按照顺序排列的链表作为底层;

    将链表中随机抽取一些元素,作为第二层,而第二层的每一个元素均有向下的一个指针,指向第一层中与其相同的元素;

    而后再在第二层元素中,随机选取一部分元素,作为第三层,而第三层中的元素也均有向下的指针指向第二层与其相同的元素;以此类推,

    直到构建了一层只有最大值最小值(-1,1)指针的元素。如此构建一个skip list。

     

    skip list有以下特征:

    最下面得一层具有所有元素;

    上面每一层的元素均是来自其下面一层的元素;

    每层元素均有向下的指针与其下一层相同的元素相关联;

    有一个top指针指向最高一层的第一个元素。

     

    在skip list中,要实现查找、插入、删除等操作时,只需要操作O(log(n))次。

     

    此时的操作方式分别为:

     

    查找元素x

     

     

     

    插入元素,假设要在第k层插入元素x,k的值不同也会有不同:

     

    Determine k the number of levels in which x participates (explained later)
    Do find(x), and insert x to the appropriate places in the lowest k levels. (after the elements at which the search path turns down or terminates)
    Example - inserting 119. k =2

     

     

     

    If k is larger than the current number of levels, add new levels (and update top)
    Example - inser (119) when k=4
    详见SkipList的PPT,是Arizona的一个guy写的,感觉很NICE,很形象。可惜很多图我无法粘贴。不知道为何。
    下面是来自另外一个网站的资料。
    目的:向跳跃表中插入一个元素x 
     首先明确,向跳跃表中插入一个元素,相当于在表中插入一列从S0中某一位置出发向上的连续一段元素。有两个参数需要确定,即插入列的位置以及它的“高度”。 
     关于插入的位置,我们先利用跳跃表的查找功能,找到比x小的最大的数y。根据跳跃表中所有链均是递增序列的原则,x必然就插在y的后面。 
     而插入列的“高度”较前者来说显得更加重要,也更加难以确定。由于它的不确定性,使得不同的决策可能会导致截然不同的算法效率。为了使插入数据之后,保持该数据结构进行各种操作均为O(logn)复杂度的性质,我们引入随机化算法(Randomized Algorithms)。 
    我们定义一个随机决策模块,它的大致内容如下: 
    产生一个0到1的随机数r                            r ← random() 
    如果r小于一个常数p,则执行方案A,  if  r<p then do A 
     否则,执行方案B                                     else do B 
    初始时列高为1。插入元素时,不停地执行随机决策模块。如果要求执行的是A操作,则将列的高度加1,并且继续反复执行随机决策模块。直到第i次,模块要求执行的是B操作,我们结束决策,并向跳跃表中插入一个高度为i的列。 
    性质1: 根据上述决策方法,该列的高度大于等于k的概率为p^(k-1)。 
    此处有一个地方需要注意,如果得到的i比当前跳跃表的高度h还要大的话,则需要增加新的链,使得跳跃表仍满足先前所提到的条件。 
    三、删除 
     目的:从跳跃表中删除一个元素x 
     删除操作分为以下三个步骤: 
    (1) 在跳跃表中查找到这个元素的位置,如果未找到,则退出  * 
    (2) 将该元素所在整列从表中删除        * 
    (3) 将多余的“空链”删除         * 
    【复杂度分析】 
    一个数据结构的好坏大部分取决于它自身的空间复杂度以及基于它一系列操作的时间复杂度。跳跃表之所以被誉为几乎能够代替平衡树,其复杂度方面自然不会落后。我们来看一下跳跃表的相关复杂度: 
    空间复杂度: O(n)    (期望) 
    跳跃表高度: O(logn)  (期望) 
    相关操作的时间复杂度: 
     查找:  O(logn)  (期望) 
     插入:   O(logn)  (期望) 
     删除:  O(logn)  (期望) 
      
    之所以在每一项后面都加一个“期望”,是因为跳跃表的复杂度分析是基于概率论的。有可能会产生最坏情况,不过这种概率极其微小。 

    一、 空间复杂度分析  O(n) 
    假设一共有n个元素。根据性质1,每个元素插入到第i层(Si)的概率为pi-1 ,则在第i层插入的期望元素个数为npi-1,跳跃表的元素期望个数为  ,当p取小于0.5的数时,次数总和小于2n。 
    所以总的空间复杂度为O(n) 
    二、跳跃表高度分析  O(logn) 
    根据性质1,每个元素插入到第i层(Si)的概率为p^i ,则在第i层插入的期望元素个数为np^(i-1)。 
    考虑一个特殊的层:第1+ 层。 
     层的元素期望个数为 np^0+np^1+...+np^(h-1),当n取较大数时,这个式子的值接近0,故跳跃表的高度为O(logn)级别的。 
    三、查找的时间复杂度分析  O(logn) 
    我们采用逆向分析的方法。假设我们现在在目标节点,想要走到跳跃表最左上方的开始节点。这条路径的长度,即可理解为查找的时间复杂度。 
    设当前在第i层第j列那个节点上。 
    i) 如果第j列恰好只有i层(对应插入这个元素时第i次调用随机化模块时所产生的B决策,概率为1-p),则当前这个位置必然是从左方的某个节点向右跳过来的。 
    ii) 如果第j列的层数大于i(对应插入这个元素时第i次调用随机化模块时所产生的A决策,概率为p),则当前这个位置必然是从上方跳下来的。(不可能从左方来,否则在以前就已经跳到当前节点上方的节点了,不会跳到当前节点左方的节点) 
    设C(k)为向上跳k层的期望步数(包括横向跳跃) 
    有: 
    C(0) = 0 
    C(k) = (1-p)(1+向左跳跃之后的步数)+p(1+向上跳跃之后的步数) 
         = (1-p)(1+C(k)) + p(1+C(k-1)) 
    C(k) = 1/p + C(k-1) 
    C(k) = k/p 
     而跳跃表的高度又是logn级别的,故查找的复杂度也为logn级别。 
    对于记忆化查找(Search with fingers)技术我们可以采用类似的方法分析,很容易得出它的复杂度是O(logk)的(其中k为此次与前一次两个被查找元素在跳跃表中位置的距离)。 
    四、插入与删除的时间复杂度分析  O(logn) 
     插入和删除都由查找和更新两部分构成。查找的时间复杂度为O(logn),更新部分的复杂度又与跳跃表的高度成正比,即也为O(logn)。 
     所以,插入和删除操作的时间复杂度都为O(logn) 
    最后,概率因子一般用1/2或1/e 

     

    展开全文
  • skiplist

    2014-05-13 18:07:57
    set/map,与 skiplist性能同级别。 但是实现复杂。 skiplist 在redis中作为set的底层容器。 插入、查找、删除级别都是log(n) //author: lovelychen_1005@163.com /*改动: 0 改为c++类。 1 ...
  • skiplist - Skiplist 在Go中的实现
  • SkipList.pptx

    2021-08-12 11:03:43
    跳跃表 skiplist 技术分享
  • 清单清单Python 跳过列表数据结构的纯python实现。 介绍 跳过列表是一种数据结构,可以用来代替平衡树。 跳过列表使用概率平衡而不是严格执行的平衡,因此,与等效树平衡算法相比...'skiplist({"foo": "bar", "spam":
  • SkipList详解

    千次阅读 2019-05-19 17:45:28
    本文参考:《大数据日知录》 概念 SkipList是一种用来代替平衡树的数据结构。 虽然在最坏的情况下SkipList的效率要...SkipList的使用还是比较广泛的,比如在LevelDB中的MemTable就是使用SkipList实现的,Redis的...
  • SkipList.h

    2020-04-28 16:27:47
    基于C++实现的SkipList源码, 代码风格比较粗犷, 没有注释.....不知道这样够不够50字
  • skipList.rar

    2020-04-21 20:56:30
    C++ 实现的跳跃表skiplist,支持模板,参照Redis的zskiplist跳跃表实现, 支持模板,适合用来做排行榜
  • skiplist模板类

    2016-10-09 16:31:30
    skiplist模板类
  • 跳表(skiplist)的理解

    万次阅读 多人点赞 2018-07-27 21:28:19
    听到跳表(skiplist)这个名字,既然是list,那么应该跟链表有关。 跳表是有序链表,但是我们知道,即使对于排过序的链表,我们对于查找还是需要进行通过链表的指针进行遍历的,时间复杂度很高依然是O(n),这个显然是...
  • A skip list cookbook.

    2017-02-03 10:18:20
    介绍skip list实现的文档
  • skiplist跳表C++实现

    2016-03-04 17:29:35
    skiplist的C++实现,包含test程序
  • 简单得实现跳表相关功能 SkipList<Integer> skipList = new SkipList(maxLevel); 提供insert和seach接口 删除接口可做类似操作
  • Skiplist简介

    2018-05-16 21:20:15
    看了这篇文章大概知道了skiplist的原理https://blog.csdn.net/ict2014/article/details/17394259/Skiplist首先是有序存储的,然后每个节点的后续节点数是random的(至少为2)这样的结构查找效率会比较高,单链表的...
  • Go中的Skiplist实现。 在了解更多信息 标准列表上具有各种添加项和潜在变体的跳过列表。 安装 go get -u github.com/mtchavez/skiplist 用法 初始化一个跳过列表 package main func main () { list := skiplist ....
  • skiplist 跳表C++实现

    热门讨论 2012-10-08 14:25:11
    skiplist 跳表C++实现,资料参考 en.wikipedia.org/wiki/Skip_list
  • skiplist 分析

    2016-03-23 16:03:32
    skiplist 时间复杂度分析
  • C++ SkipList简单实现

    千次阅读 2019-11-11 18:24:19
    SkipList.h: #pragma once #include <vector> struct SkipListNode { SkipListNode(int data, int level); int m_data; std::vector<SkipListNode*> m_forward; }; class SkipList { public: ...
  • 跳表(skiplist)是一个非常优秀的数据结构,实现简单,插入、删除、查找的复杂度均为O(logN),下面这篇文章主要介绍了c++实现跳跃表(Skip List)的相关资料,需要的朋友可以参考借鉴,下面随着小编来一起学习学习...
  • Algorithm-SkipList.zip

    2019-09-17 17:38:22
    Algorithm-SkipList.zip,Java列表中跳过列表的一种Java实现,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
  • Algorithm-skiplist.zip

    2019-09-17 12:14:39
    Algorithm-skiplist.zip,在redis中设置等级代码小于z_的跳过列表,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
  • 开源项目-MauriceGit-skiplist.zip,Go中非常快的Skiplist
  • redis中使用的skiplist数据结构
  • skiplist及Java实现

    千次阅读 2018-11-03 13:43:59
     在看《深入分布式缓存》的第7章,介绍redis的set的实现时候,提到了跳表skiplist.对应的整理下,主要分两篇吧,本篇先整理跳表及Java实现。后面在看Java的实现ConcurrentSkipListSet跟ConcurrentSkipListMap。 二...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 129,554
精华内容 51,821
关键字:

skiplist