跳跃列表是一种数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n)，优于普通队列的O(n)。
快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集（见右边的示意图）。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。跳过的元素的方法可以是随机性选择或确定性选择，其中前者更为常见。
跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速通道”，这里在第 i 层中的元素按某个固定的概率 p（通常为 1/2 或 1/4 ）出现在第 i+1 层中。且每个元素平均出现在 1/(1-p) 个列表中，而最高层的元素（通常是在跳跃列表前端的一个特殊的头元素）在 log_{1/p}n 个列表中出现。在查找目标元素时，从顶层列表、头元素起步。算法沿着每层链表搜索，直至找到一个大于或等于目标的元素，或者到达当前层列表末尾。如果该元素等于目标元素，则表明该元素已被找到；如果该元素大于目标元素或已到达链表末尾，则退回到当前层的上一个元素，然后转入下一层进行搜索。每层链表中预期的查找步数最多为 1/p，而层数为 log_{1/p}n，所以查找的总体步数为 -log_{p}n/p，由于 p 是常数，查找操作总体的时间复杂度为 O(log n)。而通过选择不同 p 值，就可以在查找代价和存储代价之间获取平衡。
时间复杂度
算法 平均 最差 空间 O(n) O(n log n) 搜索 O(log n) O(n) 插入 O(log n) O(n) 删除 O(log n) O(n)
跳跃列表不像平衡树等数据结构那样提供对最坏情况的性能保证：由于用来建造跳跃列表采用随机选取元素进入更高层的方法，在小概率情况下会生成一个不平衡的跳跃列表（最坏情况例如最底层仅有一个元素进入了更高层，此时跳跃列表的查找与普通列表一致）。但是在实际中它通常工作良好，随机化平衡方案也比平衡二叉查找树等数据结构中使用的确定性平衡方案容易实现。跳跃列表在并行计算中也很有用：插入可以在跳跃列表不同的部分并行地进行，而不用对数据结构进行全局的重新平衡。
跳跃列表由威廉·普发明。发明者对跳跃列表的评价是：“跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。
下面是实现代码
class Skiplist
{
public $head = 0;
public $i = 0;
public $j = 0;
public function __construct()
{
// 哨兵
$this->head = [
'lv' => 1, // level
'id' => -1, // number
'next' => [], // next elements
];
}
public function add(int $id)
{
$elv = 0;
do {
$elv++;
} while ( rand(0, 99) < 50 );
$el = [
'lv' => $elv, // level
'id' => $id, // number
'next' => [], // next elements
];
$hd = &$this->head;
$hlv = $hd['lv'];
if ($hlv <= $elv) {
$hlv = $elv+1;
$hd['lv'] = $hlv;
}
do {
$this->i++;
$next = &$hd['next'][$hlv-1];
if ($next == null) {
if ( $hlv <= $elv ) {
$el['next'][$hlv-1] = &$next;
$hd['next'][$hlv-1] = &$el;
}
if ($hlv > 1) {
$hlv--;
} else {
break;
}
continue;
}
if ($next['id'] < $id ) {
$hd = &$next;
continue;
}
if ($next['id'] >= $id) {
if ( $hlv <= $elv ) {
$el['next'][$hlv-1] = &$next;
$hd['next'][$hlv-1] = &$el;
}
if ($hlv > 1) {
$hlv--;
} else {
break;
}
continue;
}
} while (1);
}
public function del(int $id)
{
$hd = &$this->head;
$hlv = $hd['lv'];
do {
$next = &$hd['next'][$hlv-1];
if ($next == null) {
if ($hlv > 1) {
$hlv--;
} else {
break;
}
continue;
}
if ($next['id'] < $id ) {
$hd = &$next;
continue;
}
if ($next['id'] >= $id) {
if ($next['id'] == $id) {
unset($hd['next'][$hlv-1]);
$hd['next'][$hlv-1] = &$next['next'][$hlv-1];
}
if ($hlv > 1) {
$hlv--;
} elseif ($next['id'] == $next['next'][$hlv-1]['id']) {
$hd = &$next;
} else {
break;
}
continue;
}
} while (1);
}
public function find(int $id)
{
$hd = &$this->head;
$hlv = $hd['lv'];
do {
$this->j++;
$next = &$hd['next'][$hlv-1];
if ($next == null) {
if ($hlv > 1) {
$hlv--;
} else {
break;
}
continue;
}
if ($next['id'] < $id ) {
$hd = &$next;
continue;
}
if ($next['id'] > $id) {
if ($hlv > 1) {
$hlv--;
} else {
break;
}
continue;
}
if ($next['id'] == $id) {
return true;//$hd['next'][$hlv-1];
}
} while (1);
return false;
}
/**
* why write this? because could less memory opeation
* @param int $nid
* @param int $dt
*/
public function upd($nid, int $dt)
{
if (!isset($this->sl[$dt]) || $nid == $this->sl[$dt]['id']) {
return 0;
}
/* delete from old position */
$this->del($dt);
/* add to new position */
$this->add($nid, $dt);
}
/**
* pop last element
* @return unknown|number|number[]|NULL[]|array[]
*/
public function pop()
{
$hd = &$this->head;
$hlv = $hd['lv'];
do {
if ($hd['next'][$hlv-1] == null) {
if ($hlv > 1) {
$hlv--;
} else {
break;
}
continue;
}
if ($hd['next'][$hlv-1] != null ) {
$hd = &$hd['next'][$hlv-1];
continue;
}
} while (1);
if ($hd != $this->head) {
$this->del($hd['id']);
return $hd;
}
return [];
}
public function print()
{
$hd = &$this->head;
$hlv = $hd['lv'];
for ($i = 0; $i < $hlv; $i++) {
$hd = &$this->head;
while ($hd != null) {
if ($hd['lv'] > $i) {
printf("%4d", $hd['id']);
} else {
printf(" ");
}
$hd = &$hd['next'][0];
}
printf(" null\n");
}
}
}
$sl = new Skiplist();
for ($i = 40; $i >= 0; $i--) {
$sl->add(rand(10,99), $i);
}
$sl->print();
echo memory_get_usage()."\n";
// exit();
for ($i = 10; $i > 0; $i--) {
$sl->find($i);
}
echo memory_get_usage()."\n";
for ($i = 10; $i >= 0; $i--) {
$n = rand(10,99);
echo "$n ";
$sl->del($n);
}
echo "\n";
$sl->print();
echo memory_get_usage()."\n";
/* test 10w's add */
$time1 = microtime(true);
for ($i = 10000; $i >= 0; $i--) {
$sl->add(rand(10000000,99999999), $i);
}
$time2 = microtime(true);
echo memory_get_usage()."\n";
echo ($time2 - $time1)."s\n";
/* test 10w's find */
for ($i = 10000; $i > 0; $i--) {
$sl->find(rand(10000000,99999999));
}
$time3 = microtime(true);
echo ($time3 - $time2)."s\n";
echo $sl->i." ".$sl->j."\n";
$i = 10000;
$j = 10000;
echo (int)($i*log($i, 2))." ".(int)($j*log($i, 2))."\n";
// -1 27 31 35 36 46 50 53 53 53 64 67 67 70 76 85 90 92 92 93 95 96 null
// -1 27 36 46 53 53 67 67 70 76 85 93 null
// -1 46 53 53 67 76 null
// -1 53 null
// -1 53 null
// -1 null
转载请注明：小Y » 跳表（skiplist）
php实现时间轮算法