`
zhangyu8374
  • 浏览: 95111 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

基本算法连载(6)-Skip List(上)

阅读更多
Skip List号称性能与BST(Binary Sort Tree)树有得一拼,于是把它翻了个底朝天。代码是阐述其思想的最好方式,那我们还是看看它的具体实现(采用Java语言)
public class SkipList {

public static final int NOT_FOUND = -1;
public static final int HEADER_KEY = -2;
public static final int NIL_KEY = Integer.MAX_VALUE;

// optimum probability
public static final float OPT_PROB = 0.25f;
private float myProbability;
// probability to increase level
private int myMaxLevel;
// upper bound of levels
private int myLevel;
// greatest level so far
private SkipListElement
myHeader; // the header element of list

/*
* Constructs a new skip list optimized for the given
* expected upper bound for the number of nodes.
*/

public SkipList(long maxNodes) {
// probability set to 0.25 and maximum level
// of list is depending on expected number of nodes
// (see paper for mathematical background)
this(OPT_PROB,(int)Math.ceil(Math.log(maxNodes)/Math.log(1/OPT_PROB))-1);
}

public SkipList(float probability, int maxLevel) {
myLevel = 0;
myProbability = probability;
myMaxLevel = maxLevel;
// generate the header of the list
myHeader = new SkipListElement(myMaxLevel,HEADER_KEY, 0);

// append the "NIL" element to the header
SkipListElement nilElement = new SkipListElement(myMaxLevel, NIL_KEY, 0);
for (int i=0; i<=myMaxLevel; i++) {
myHeader.forward[i] = nilElement;
}
}

/*
* Generates with help of randomizer the level of a new element.
* The higher a level, the less probable it is (see paper).
* Levels begin at 0 (not at 1 like in the paper).
*/
private int generateRandomLevel() {
int newLevel = 0;
while (newLevel<myMaxLevel &&Math.random()<myProbability ) {
newLevel++;
}
return newLevel;
}

/*
* Inserts a new node into the list.
* If the key already exists, its node is updated to the new value.
*/
public void insert(int searchKey, int value) {
// update pointers to next elements on each level and
// levels run from 0 up to myMaxLevel.
SkipListElement[] update = new SkipListElement[myMaxLevel+1];

// init "cursor" element to header
SkipListElement element = myHeader;

// find place to insert the new node
for (int i=myLevel; i>=0; i--) {
while (element.forward[i].key <searchKey) {
element = element.forward[i];
}
update[i] = element;
}

element = element.forward[0];

// element with same key is overwritten
if (element.key == searchKey) {
element.value = value;
}else{
// or an additional element is inserted
int newLevel = generateRandomLevel();
// element has biggest level seen in this list,update list
if (newLevel > myLevel) {
for (int i=myLevel+1;i<=newLevel; i++) {
update[i] = myHeader;
}

myLevel = newLevel;
}

// allocate new element:
element = new SkipListElement(newLevel,searchKey, value);
for (int i=0; i<=newLevel; i++) {
element.forward[i] = update[i].forward[i];
update[i].forward[i] = element;
}
}

}

/*
* Search for a given key in list. You get the value associated
* with that key or the NOT_FOUND constant.
*/

public int search(int searchKey) {
// init "cursor"-element to header
SkipListElement element = myHeader;

// find element in list:
for (int i=myLevel; i>=0; i--) {
SkipListElement nextElement = element.forward[i];
while (nextElement.key < searchKey) {
element = nextElement;
nextElement = element.forward[i];
}
}

element = element.forward[0];
if (element.key == searchKey) {
return element.value;
}else {
return NOT_FOUND;
}

}

public void delete(int searchKey) {
// update holds pointers to next elements of each level
SkipListElement update[] = new SkipListElement[myMaxLevel+1];

// init "cursor"-element to header
SkipListElement element = myHeader;

// find element in list
for (int i=myLevel; i>=0; i--) {
SkipListElement nextElement = element.forward[i];
while (nextElement.key < searchKey) {
element = nextElement;
nextElement = element.forward[i];
}
update[i] = element;
}

element = element.forward[0];
// element found, so rebuild list without node
if (element.key == searchKey) {
for (int i=0; i<=myLevel; i++) {
if (update[i].forward[i] == element) {
update[i].forward[i] = element.forward[i];
}
}

// element can be freed now
element = null;

// maybe we have to downcorrect the level of the list
while (myLevel>0&& myHeader.forward[myLevel].key==NIL_KEY){
myLevel--;
}
}
}

/*
* inner class
*/

private class SkipListElement {
int key;
int value;
int level;

// array of forward pointers
SkipListElement forward[];

public SkipListElement(int level, int key, int value) {
this.key = key;
this.value = value;
this.level = level;
forward = new SkipListElement[this.level+1];
}
}

}
分享到:
评论

相关推荐

    wK算法算法处理RADARSAT-1数据_share

    **标题解析:** ...综上所述,这个项目涉及了遥感数据处理的高级技术,特别是对SAR数据的wK算法处理,以及使用Matlab进行编程实现。虽然核心代码未公开,但通过链接的文章可能能获取一些实施细节和成果展示。

    A skip list cookbook.

    通过本文档的介绍,我们可以看到 Skip list 不仅可以支持基本的操作,还可以灵活地实现其他高级功能,如使用搜索指针、合并、分割和连接等。这些扩展操作使得 Skip list 成为一个非常实用的数据结构,可以在多种应用...

    数据结构算法与应用--C++语言描述(代码与习题答案)

    在《数据结构算法与应用--C++语言描述》这本书中,作者深入浅出地介绍了各种基本和高级的数据结构及其对应的算法,并提供了详细的C++实现。以下是基于这个主题的详细知识点讲解: 1. **数组**:数组是最基础的数据...

    用python实现skip-gram算法:AAAI-14 accepted papers(NLP)分类任务

    首先,我们需要理解skip-gram模型的基本架构。在skip-gram中,我们有两个主要的神经网络组件:输入层和输出层。输入层接收一个单词的one-hot编码作为输入,输出层则尝试预测上下文中的单词。这个过程通过反向传播...

    粒子群算法与灰狼优化结合算法(PSO-GWO).m

    粒子群算法与灰狼优化结合算法(PSO-GWO) 粒子群算法与灰狼优化结合算法(PSO-GWO) 粒子群算法与灰狼优化结合算法(PSO-GWO).m

    视频编码中低内存P-Skip决策算法研究与实现及其应用探讨

    内容概要:本文详细介绍了一种新型的低内存消耗P-Skip(跳过预测)决策算法在视频编码器中的实施方法,尤其适用于需要减少外部存储使用的环境。传统P-Skip算法因需要保存前后帧图像来决定宏块是否变化而占用较多内存...

    数据结构,算法与应用 ---C++语言描述(代码与习题答案)

    此外,C++标准库提供了丰富的容器(如vector、list、set、map)和算法(如sort、find、transform),简化了数据结构和算法的实现。 4. **代码与习题答案**:这部分内容包含对书中各种数据结构和算法的C++实现,以及...

    粒子群算法优化3-5-3多项式工业机器人时间最优轨迹规划算法matlab代码

    在机器人路径规划领域,优化算法起着至关重要的作用,它能帮助找到最有效、最经济的运动轨迹。本文将深入探讨“粒子群算法优化3-5-3多项式工业机器人时间最优轨迹规划算法”这一主题,以及如何在MATLAB环境下实现这...

    MIMO预编码算法MATLAB实现-ZF、MMSE、SVD、BD

    MIMO预编码算法MATLAB实现-ZF、MMSE、SVD、BD

    遗传k-means 基于遗传算法的k-means

    遗传k-means 遗传算法 演化算法 聚类算法 k-means 遗传k-means 遗传算法 演化算法 聚类算法 k-means 遗传k-means 遗传算法 演化算法 聚类算法 k-means

    帧间编码算法优化:基于P-skip模式提前判决的研究

    通过对运动估计基本原理的介绍以及块匹配准则的深入研究,文中建立了一个全零块阈值模型,使得可以在运动估计前快速识别P_skip模式的宏块,大幅减少了不必要的计算。最终实现了编码时间减少约32%,同时比特率降低了...

    py-skiplist:skiplist数据结构的纯python实现

    清单清单Python 跳过列表数据结构的纯python实现。 介绍 跳过列表是一种数据结构,可以用来代替平衡树。 跳过列表使用概率平衡而不是严格执行的平衡,因此,与等效树平衡算法相比...'skiplist({"foo": "bar", "spam":

    什么是神经网络算法?----关于神经网络算法的基本介绍

    神经网络算法的基本介绍,其中也说明了神经网络算法与网格计算的区别

    skiplist 跳表C++实现

    跳表(Skip List)是一种高效的查找数据结构,它利用了概率算法来提高查询效率,通常用于数据库和搜索引擎中。在C++中实现跳表,我们可以利用STL中的容器和算法库来简化工作,同时理解其背后的原理至关重要。 跳表...

    AC算法和AC-BM算法

    6. `acbm`:这个文件可能是AC-BM算法的源代码或者一个可执行程序。 理解并实现这些算法,不仅能够提升字符串匹配的效率,还能帮助开发者深入理解计算机科学中的搜索算法和数据结构。对于研究和实践文本处理、信息...

    数据结构与算法分析--C语言描述_数据结构与算法_

    此PDF教材可能涵盖这些基本概念,并通过实例代码展示C语言中如何实现这些数据结构和算法。学习者不仅可以了解理论知识,还能动手实践,提升编程能力。通过学习,读者应能理解各种数据结构的特点和适用场景,掌握常见...

    空间谱估计理论与算法------程序.rar

    第6章_旋转不变子空间算法;第7章_子空间迭代与更新;第8章_宽带信号的空间谱估计算法;第10章 空间分布式信号源参数估计;第11章_特殊阵列结构的空间谱估计;第12章_基于高阶统计量的空间谱估计;第13章_空间谱估计...

    NSGA-III算法-matlab版本-写满了中文注释

    这是从mathwork上下载的NSGA-3的代码,自己写的注释。因为也没有完全弄懂代码,所以有些地方空着没写注释,有些地方还注释了问号。就是希望能和大家一起讨论交流一下,希望大家指正。希望弄懂代码的小伙伴能回帖说...

    k-shell分解算法

    其基本思想如下,假设边缘节点的 K-shell值为 1,然后往内一层层进入网络的核心,先去除网络 中度值等于 1 的所有节点以及连边。 若剩下的节点里面,仍有度值等于 1 的节点,则重复上述操作,即去除这些节点和连边...

Global site tag (gtag.js) - Google Analytics