【大数据算法】一文掌握大数据算法之：排序链表搜索的亚线性算法。

排序链表搜索的亚线性算法

1、引言
2、平面图直径问题的亚线性算法
- 2.1 定义
- 2.2 核心原理
- - 2.2.1 跳表
  - 2.2.2 跳跃搜索
  - 2.2.3 分块搜索
- 2.3 应用场景
- 2.4 算法公式
- 2.5 代码示例
3、总结

1、引言

小屌丝：鱼哥，这茶味道怎么样？
小鱼：嗯，确实不错？
小屌丝：这时间也差不多了，我们去泡泡澡？
小鱼：也行，这茶叶，带着。
小屌丝：… 鱼哥，咱这会所有茶啊。
小鱼：别这么小气，你这茶味道不错的。
小屌丝：你这…没喝到这个茶叶之前，你喝其他的，这味道不也是不错的嘛。
小鱼：要不，咱再等一会？
小屌丝：怎么不着急了？
小鱼：我突然想起来，排序链表搜索的亚线性算法还没跟你说的
小屌丝：这个，我不着急啊。
小鱼：那不行，学习岂能学一半的时候，
小屌丝：…。
小鱼：这茶，再冲泡一次。
小屌丝：…
小鱼：别那么小气。
小屌丝：… 好好好~

在这里插入图片描述

2、平面图直径问题的亚线性算法

2.1 定义

在数据结构中，排序链表是一种链表，其中节点按某种自然顺序排序。

对排序链表进行搜索时，传统线性搜索的时间复杂度是 $O (n)$ ，其中 $n$ 是链表的长度。

亚线性时间算法旨在通过某些特殊技巧和预处理步骤，使搜索操作的时间复杂度低于 $O (n)$ ，实现更快的查询速度。

2.2 核心原理

排序链表搜索的亚线性算法主要利用了如下核心原理：

跳表（Skip List）：一种层级化的链表结构，增加了多层索引以实现更快的跳跃和搜索。
跳跃搜索（Jump Search）：在链表上进行固定长度的跳跃，以减少搜索范围。
分块搜索（Block Search）：将链表划分为若干块，每块进行局部排序，再在每块内进行二分查找。

2.2.1 跳表

跳表（Skip List）

跳表是一种层次化的数据结构，允许快速搜索。跳表为普通链表增加了多层“跳跃”链表，每层链表的长度是下层的约一半，通过这些级联的跳跃层，可以快速跳过大量元素。

2.2.2 跳跃搜索

跳跃搜索（Jump Search）

跳跃搜索算法在排序链表上以固定步长跳跃进行搜索，先找到目标值可能存在的区间，再在该区间内进行线性扫描，从而减少搜索的耗时。
假设步长为 $k$ ，则其时间复杂度为 $O (\sqrt n)$ 。

2.2.3 分块搜索

分块搜索（Block Search）

分块搜索将排序链表划分成若干块，每块内进行局部排序，然后在每块内进行二分查找。
这种方法利用了局部性的优势，实现了更快的搜索速度。

2.3 应用场景

平排序链表搜索的亚线性算法在以下场景中具有广泛的应用：

数据库索引：跳表广泛应用于数据库索引结构，如 LevelDB 和 Redis。
搜索引擎：在各种搜索引擎中，跳表用于快速查找和排序。
网络路由：在计算网络路由路径时，跳表有助于快速定位路由信息。
内存缓存：在高速缓存系统中，跳表用于快速存取缓存数据。

2.4 算法公式

以跳表为例，其时间复杂度通常为 $O (l o g n)$ ，这显著优于传统链表的 $O (n)$ 。

跳表算法的索引结构
设节点总数为 n，则跳表的结构通常包括以下几层：

底层：包含所有节点。
上层：每隔 $k$ 个节点抽取一个节点 $（ k \approx 2 ）$ 。
…
顶层：仅包含几个或一个节点。

各层的节点数大致为 $n$ , $n /2$ , $n /4$ , …, 1。

2.5 代码示例

# -*- coding:utf-8 -*-
# @Time   : 2024-08-10
# @Author : Carl_DJimport randomclass SkipListNode:def __init__(self, value, level):self.value = valueself.forward = [None] * (level + 1)class SkipList:def __init__(self, max_level):self.max_level = max_levelself.header = SkipListNode(None, max_level)self.level = 0def random_level(self):level = 0while random.random() < 0.5 and level < self.max_level:level += 1return leveldef insert(self, value):update = [None] * (self.max_level + 1)current = self.headerfor i in range(self.level, -1, -1):while current.forward[i] and current.forward[i].value < value:current = current.forward[i]update[i] = currentlevel = self.random_level()if level > self.level:for i in range(self.level + 1, level + 1):update[i] = self.headerself.level = levelnew_node = SkipListNode(value, level)for i in range(level + 1):new_node.forward[i] = update[i].forward[i]update[i].forward[i] = new_nodedef search(self, value):current = self.headerfor i in range(self.level, -1, -1):while current.forward[i] and current.forward[i].value < value:current = current.forward[i]current = current.forward[0]return current and current.value == value# 示例使用
skiplist = SkipList(max_level=4)
values = [1, 3, 7, 8, 9, 10, 13, 14, 19]
for value in values:skiplist.insert(value)# 搜索
search_value = 10
found = skiplist.search(search_value)
print(f"Value {search_value} {'found' if found else 'not found'} in the skiplist")

代码解析：

SkipListNode 类定义了跳表节点，每个节点包含一个值和一个 forward 数组，表示该节点的跳跃层。
SkipList 类定义了跳表的数据结构和基本操作，包括插入和搜索。
random_level 方法定义了一个基于随机数的层级选择机制，符合跳表的性质。
insert 方法插入一个新值到跳表中，动态调整跳表的层级。
search 方法在跳表中搜索一个值，利用多层索引快速定位。