Sep
19
# 1. 什么是跳表
跳表(Skip List)是基于链表 + 随机化实现的一个有序数据结构,可以达到平均 O(logN) 的查找、插入、删除效率,在实际运行中的效率往往超过 AVL 等平衡二叉树,而且其实现相对更简单、内存消耗更低。
Redis 的 ZSET 底层实现就是用的 Skip List,这里是 [Antirez对此的说明](https://news.ycombinator.com/item?id=1171423)。
这是一个典型的跳表:
解释一下:
1. SkipList 是一个多层的链表
2. 第[0]层的链表包含所有节点,其他层的链表包含部分节点,层次越高,节点越少
3. 每层链表之间会共享相同的节点(节省内存,但为了方便展示,每一层都输出了它的值)
4. 对于某个节点,在插入时通过概率判断它最高会出现在哪一层,并且也会出现在之下的每一层
通过这样的设计,当需要查找某个 key 时,可以从最高层的链表开始往前找,在这一层遇到末尾或者大于 key 的节点时往下走一个层,直到找到 key 节点。
例如:
# 2. 跳表的节点
从上面的描述,我们大概可以知道 (1) 每个节点需要保存一个 key; (2) 每个节点需要有多个next指针 (3) 其 next 指针的数量会在插入时确定
因此我们可以用下面这个 class 来表示节点:
# 3. 创建跳表
一个新创建的跳表是没有节点的。但为了实现的简单起见,可以添加一个头节点:
到目前为止都特别简单,但是还什么也干不了。
# 4. 创建节点
创建节点时,需要先按一定的概率分布确定其高度。
为了保证高层的节点比低层少,我们可以用这样的概率分布:
实现其实非常简单:
这样可以保证平均的路径长度是 log(n) 。
精确一点的话,实际上是 log(n-1, 1/p) / p,也就是说, p 的选择会影响跳表层数、平均路径长度。
具体的计算比较复杂,有兴趣可以参考跳表的原论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。(TL;DR)
然后我们就可以这样来创建一个新的节点:
node = Node(self.randomHeight(), key)
# 5. 添加节点
如果只是为空跳表添加一个新的节点,只要更新头结点的每一个next指针:
但很显然这个方法只能用一次。
如果跳表中已经有多个节点,那我们就必须找到每一层中适合插入的位置:
这个函数返回一个 update 节点数组,其中的每个节点都是在这一层中小于 key 的最后一个节点。
也就是说,在 level = i 层,总是可以把新的节点插入 update[i] 之后:
但是由于这一版 getUpdateList 是 O(n) 的,插入效率并没有达到跳表的设计目标。
# 6. 添加节点++
考虑这一点:跳表的每一层都是有序的。
也就是说,我们在找到 update[n] = x 以后,其实可以从节点 x 的 n - 1 层继续查找 update[n-1] 应该是哪个节点。
由于查找路径的平均长度是 log(N) ,所以我们可以实现一个更快的 getUpdateList 方法
注意,需要从最高层开始查
# 7. 里程碑1
把上面的代码整合起来,我们就可以得到第一版跳表代码:能够插入节点。
为了更好地展示我们的成果,我们可以用这样一个函数,把链表按第1节的例子样式输出:
试试看:
多尝试几次,以及选择不同的 p 值,可以观察生成跳表的区别。
# 8. 查找节点
实际上查找节点的过程,已经包含在 insert 的实现里了:
# 9. 删除节点
既然已经能找出 update 节点数组,在 level = i 层,只要判断 update[i].next[i] 是否等于要删除的 key 就可以了:
# 10. 里程碑2
整合 find 和 update 数组,就可以实现跳表的基础操作了,试试看:
# 11. 其他
我们在 Node 中只添加了一个 key 属性,在具体的实现中,我们往往可能需要针对 key 存储一个 value,例如 Python 自带的 dict 实现。改造起来也很简单:
1. node 中添加一个 value 属性,并且添加相应的初始化逻辑(__init__方法)
2. 将 SkipList.insert 修改为 `insert(self, key, value)`,在新建 Node 时指定其 value
3. 再添加一个 `update(self, key, value)` API,方便调用方的使用
4. 可以考虑针对语言适配,例如实现 python 的 __getitem__ 、 __setitem__ 等魔术方法
# 12. 完整代码
完。
跳表(Skip List)是基于链表 + 随机化实现的一个有序数据结构,可以达到平均 O(logN) 的查找、插入、删除效率,在实际运行中的效率往往超过 AVL 等平衡二叉树,而且其实现相对更简单、内存消耗更低。
Redis 的 ZSET 底层实现就是用的 Skip List,这里是 [Antirez对此的说明](https://news.ycombinator.com/item?id=1171423)。
这是一个典型的跳表:
[0] -> 0 -> 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 9 -> nil
[1] -> 0 ------> 3 ------> 5 ------> 7 ------> nil
[2]----------------------> 5-----------------> nil
[1] -> 0 ------> 3 ------> 5 ------> 7 ------> nil
[2]----------------------> 5-----------------> nil
解释一下:
1. SkipList 是一个多层的链表
2. 第[0]层的链表包含所有节点,其他层的链表包含部分节点,层次越高,节点越少
3. 每层链表之间会共享相同的节点(节省内存,但为了方便展示,每一层都输出了它的值)
4. 对于某个节点,在插入时通过概率判断它最高会出现在哪一层,并且也会出现在之下的每一层
通过这样的设计,当需要查找某个 key 时,可以从最高层的链表开始往前找,在这一层遇到末尾或者大于 key 的节点时往下走一个层,直到找到 key 节点。
例如:
引用
4 的查找路径为 [2] -> [1] -> 0 -> 3 -> 3@[0] -> 4
6 的查找路径为 [2] -> 5 -> 5@[1] -> 5@[0] -> 6
8 的查找路径为 [2] -> 5 -> 5@[1] -> 7 -> 7@[0] -> 9 (找不到)
6 的查找路径为 [2] -> 5 -> 5@[1] -> 5@[0] -> 6
8 的查找路径为 [2] -> 5 -> 5@[1] -> 7 -> 7@[0] -> 9 (找不到)
# 2. 跳表的节点
从上面的描述,我们大概可以知道 (1) 每个节点需要保存一个 key; (2) 每个节点需要有多个next指针 (3) 其 next 指针的数量会在插入时确定
因此我们可以用下面这个 class 来表示节点:
class Node(object)
def __init__(self, height, key):
self.key = key
self.next = [None] * height
def height(self):
return len(self.next)
def __init__(self, height, key):
self.key = key
self.next = [None] * height
def height(self):
return len(self.next)
# 3. 创建跳表
一个新创建的跳表是没有节点的。但为了实现的简单起见,可以添加一个头节点:
class SkipList(object):
def __init__(self):
self.head = Node(0, None) #头节点高度为0,不需要key
def __init__(self):
self.head = Node(0, None) #头节点高度为0,不需要key
到目前为止都特别简单,但是还什么也干不了。
# 4. 创建节点
创建节点时,需要先按一定的概率分布确定其高度。
为了保证高层的节点比低层少,我们可以用这样的概率分布:
引用
Height(n) = p^n
实现其实非常简单:
import random
def randomHeight(self, p = 0.5):
height = 1
while random.uniform(0, 1) < p and self.head.height() >= height:
height += 1
return height
def randomHeight(self, p = 0.5):
height = 1
while random.uniform(0, 1) < p and self.head.height() >= height:
height += 1
return height
这样可以保证平均的路径长度是 log(n) 。
精确一点的话,实际上是 log(n-1, 1/p) / p,也就是说, p 的选择会影响跳表层数、平均路径长度。
具体的计算比较复杂,有兴趣可以参考跳表的原论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。(TL;DR)
然后我们就可以这样来创建一个新的节点:
node = Node(self.randomHeight(), key)
# 5. 添加节点
如果只是为空跳表添加一个新的节点,只要更新头结点的每一个next指针:
def insertFirstNode(self, key):
node = Node(self.randomHeight(), key)
while node.height > self.head.height():
self.head.next.append(None) #保证头节点的next数组覆盖所有层次的链表
for level in range(node.height()):
node.next[level] = self.head.next[level]
self.head.next[level] = node
node = Node(self.randomHeight(), key)
while node.height > self.head.height():
self.head.next.append(None) #保证头节点的next数组覆盖所有层次的链表
for level in range(node.height()):
node.next[level] = self.head.next[level]
self.head.next[level] = node
但很显然这个方法只能用一次。
如果跳表中已经有多个节点,那我们就必须找到每一层中适合插入的位置:
def getUpdateList(self, key):
update = [None] * self.head.height()
for level in range(len(update)):
x = self.head
while x.next[level] is not None and x.next[level].key < key:
x = x.next[level]
update[level] = x
return update
update = [None] * self.head.height()
for level in range(len(update)):
x = self.head
while x.next[level] is not None and x.next[level].key < key:
x = x.next[level]
update[level] = x
return update
这个函数返回一个 update 节点数组,其中的每个节点都是在这一层中小于 key 的最后一个节点。
也就是说,在 level = i 层,总是可以把新的节点插入 update[i] 之后:
def insert(self, key):
node = Node(self.randomHeight(), key)
while node.height > self.head.height():
self.head.next.append(None) #保证头节点的next数组覆盖所有层次的链表
update = self.getUpdateList(key)
next0 = update[0].next[0]
if next0 is not None and next0.key == key:
return # 0层总是包含所有元素;如果 update[0] 的下一个节点与key相等,则无需插入。
for level in range(node.height()):
node.next[level] = update[level].next[level]
update[level].next[level] = node
node = Node(self.randomHeight(), key)
while node.height > self.head.height():
self.head.next.append(None) #保证头节点的next数组覆盖所有层次的链表
update = self.getUpdateList(key)
next0 = update[0].next[0]
if next0 is not None and next0.key == key:
return # 0层总是包含所有元素;如果 update[0] 的下一个节点与key相等,则无需插入。
for level in range(node.height()):
node.next[level] = update[level].next[level]
update[level].next[level] = node
但是由于这一版 getUpdateList 是 O(n) 的,插入效率并没有达到跳表的设计目标。
# 6. 添加节点++
考虑这一点:跳表的每一层都是有序的。
也就是说,我们在找到 update[n] = x 以后,其实可以从节点 x 的 n - 1 层继续查找 update[n-1] 应该是哪个节点。
由于查找路径的平均长度是 log(N) ,所以我们可以实现一个更快的 getUpdateList 方法
注意,需要从最高层开始查
def getUpdateList(self, key):
update = [None] * self.head.height()
x = self.head
for level in reversed(range(len(update))):
while x.next[level] is not None and x.next[level].key < key:
x = x.next[level]
update[level] = x
return update
update = [None] * self.head.height()
x = self.head
for level in reversed(range(len(update))):
while x.next[level] is not None and x.next[level].key < key:
x = x.next[level]
update[level] = x
return update
# 7. 里程碑1
把上面的代码整合起来,我们就可以得到第一版跳表代码:能够插入节点。
为了更好地展示我们的成果,我们可以用这样一个函数,把链表按第1节的例子样式输出:
def dump(self):
for i in range(self.head.height()):
sys.stdout.write('[H]')
x = self.head.next[0]
y = self.head.next[i]
while x is not None:
s = ' -> %s' % x.key
if x is y:
y = y.next[i]
else:
s = '-' * len(s)
x = x.next[0]
sys.stdout.write(s)
print ' -> <nil>'
print
for i in range(self.head.height()):
sys.stdout.write('[H]')
x = self.head.next[0]
y = self.head.next[i]
while x is not None:
s = ' -> %s' % x.key
if x is y:
y = y.next[i]
else:
s = '-' * len(s)
x = x.next[0]
sys.stdout.write(s)
print ' -> <nil>'
试试看:
sl = SkipList()
for i in range(10):
sl.insert(sl)
s1.dump()
for i in range(10):
sl.insert(sl)
s1.dump()
[H] -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> <nil>
[H]----- -> 1 -> 2 -> 3---------- -> 6 -> 7---------- -> <nil>
[H]---------- -> 2-------------------- -> 7---------- -> <nil>
[H]----- -> 1 -> 2 -> 3---------- -> 6 -> 7---------- -> <nil>
[H]---------- -> 2-------------------- -> 7---------- -> <nil>
多尝试几次,以及选择不同的 p 值,可以观察生成跳表的区别。
# 8. 查找节点
实际上查找节点的过程,已经包含在 insert 的实现里了:
def find(self, key):
update = self.getUpdateList(key)
if len(update) == 0:
return None
next0 = update[0].next[0]
if next0 is not None and next0.key == key:
return next0 # 0层总是包含所有元素;如果 update[0] 的下一个节点与key相等,则无需插入。
else:
return None
update = self.getUpdateList(key)
if len(update) == 0:
return None
next0 = update[0].next[0]
if next0 is not None and next0.key == key:
return next0 # 0层总是包含所有元素;如果 update[0] 的下一个节点与key相等,则无需插入。
else:
return None
# 9. 删除节点
既然已经能找出 update 节点数组,在 level = i 层,只要判断 update[i].next[i] 是否等于要删除的 key 就可以了:
def remove(self, key):
update = self.getUpdateList(key)
for i, node in enumerate(update):
if node.next[i] is not None and node.next[i].key == key:
node.next[i] = node.next[i].next[i]
update = self.getUpdateList(key)
for i, node in enumerate(update):
if node.next[i] is not None and node.next[i].key == key:
node.next[i] = node.next[i].next[i]
# 10. 里程碑2
整合 find 和 update 数组,就可以实现跳表的基础操作了,试试看:
node = sl.find(3)
print node
for i in range(7, 14):
sl.remove(i)
sl.dump()
print node
for i in range(7, 14):
sl.remove(i)
sl.dump()
# 11. 其他
我们在 Node 中只添加了一个 key 属性,在具体的实现中,我们往往可能需要针对 key 存储一个 value,例如 Python 自带的 dict 实现。改造起来也很简单:
1. node 中添加一个 value 属性,并且添加相应的初始化逻辑(__init__方法)
2. 将 SkipList.insert 修改为 `insert(self, key, value)`,在新建 Node 时指定其 value
3. 再添加一个 `update(self, key, value)` API,方便调用方的使用
4. 可以考虑针对语言适配,例如实现 python 的 __getitem__ 、 __setitem__ 等魔术方法
# 12. 完整代码
#coding:utf-8
import random
class Node(object):
def __init__(self, height, key=None):
self.key = key
self.next = [None] * height
def height(self):
return len(self.next)
class SkipList(object):
def __init__(self):
self.head = Node(0, None) #头节点高度为0,不需要key
def randomHeight(self, p = 0.5):
height = 1
while random.uniform(0, 1) < p and self.head.height() >= height:
height += 1
return height
def insert(self, key):
node = Node(self.randomHeight(), key)
print node.height(), node.key
while node.height() > self.head.height():
self.head.next.append(None) #保证头节点的next数组覆盖所有层次的链表
update = self.getUpdateList(key)
if update[0].next[0] is not None and update[0].next[0].key == key:
return # 0层总是包含所有元素;如果 update[0] 的下一个节点与key相等,则无需插入。
for level in range(node.height()):
node.next[level] = update[level].next[level]
update[level].next[level] = node
def getUpdateList(self, key):
update = [None] * self.head.height()
x = self.head
for level in reversed(range(len(update))):
while x.next[level] is not None and x.next[level].key < key:
x = x.next[level]
update[level] = x
return update
def dump(self):
for i in range(self.head.height()):
sys.stdout.write('[H]')
x = self.head.next[0]
y = self.head.next[i]
while x is not None:
s = ' -> %s' % x.key
if x is y:
y = y.next[i]
else:
s = '-' * len(s)
x = x.next[0]
sys.stdout.write(s)
print ' -> <nil>'
print
def find(self, key):
update = self.getUpdateList(key)
if len(update) == 0:
return None
next0 = update[0].next[0]
if next0 is not None and next0.key == key:
return next0 # 0层总是包含所有元素;如果 update[0] 的下一个节点与key相等,则无需插入。
else:
return None
def remove(self, key):
update = self.getUpdateList(key)
for i, node in enumerate(update):
if node.next[i] is not None and node.next[i].key == key:
node.next[i] = node.next[i].next[i]
import random
class Node(object):
def __init__(self, height, key=None):
self.key = key
self.next = [None] * height
def height(self):
return len(self.next)
class SkipList(object):
def __init__(self):
self.head = Node(0, None) #头节点高度为0,不需要key
def randomHeight(self, p = 0.5):
height = 1
while random.uniform(0, 1) < p and self.head.height() >= height:
height += 1
return height
def insert(self, key):
node = Node(self.randomHeight(), key)
print node.height(), node.key
while node.height() > self.head.height():
self.head.next.append(None) #保证头节点的next数组覆盖所有层次的链表
update = self.getUpdateList(key)
if update[0].next[0] is not None and update[0].next[0].key == key:
return # 0层总是包含所有元素;如果 update[0] 的下一个节点与key相等,则无需插入。
for level in range(node.height()):
node.next[level] = update[level].next[level]
update[level].next[level] = node
def getUpdateList(self, key):
update = [None] * self.head.height()
x = self.head
for level in reversed(range(len(update))):
while x.next[level] is not None and x.next[level].key < key:
x = x.next[level]
update[level] = x
return update
def dump(self):
for i in range(self.head.height()):
sys.stdout.write('[H]')
x = self.head.next[0]
y = self.head.next[i]
while x is not None:
s = ' -> %s' % x.key
if x is y:
y = y.next[i]
else:
s = '-' * len(s)
x = x.next[0]
sys.stdout.write(s)
print ' -> <nil>'
def find(self, key):
update = self.getUpdateList(key)
if len(update) == 0:
return None
next0 = update[0].next[0]
if next0 is not None and next0.key == key:
return next0 # 0层总是包含所有元素;如果 update[0] 的下一个节点与key相等,则无需插入。
else:
return None
def remove(self, key):
update = self.getUpdateList(key)
for i, node in enumerate(update):
if node.next[i] is not None and node.next[i].key == key:
node.next[i] = node.next[i].next[i]
完。
Sep
6
excel很强大,但也有非常蠢的地方:比如今天遇到的,导出文档的日期列是“文本”格式,这时候用数据透视表,excel不能识别这是日期,于是无法根据月或者年对数据进行聚合。
即使选中整列,然后将格式全都修改为日期也不行。
即使再弄一列格式为日期的,然后用黏贴数值也不行。
按照过去的经验,只有逐个格子双击,然后回车,才能把格式应用到数据上,真是蠢到爆炸。
今天觉得实在不能忍了,放狗搜了下“excel apply format instead of double click on each column”,总算找到一个解决方案:
1. 选中该列
2. 在“数据”Tab里点击“分列”(按格式将单列文本拆分成多列,英文版是 Text To Columns)
3. 点击完成
搞定
即使选中整列,然后将格式全都修改为日期也不行。
即使再弄一列格式为日期的,然后用黏贴数值也不行。
按照过去的经验,只有逐个格子双击,然后回车,才能把格式应用到数据上,真是蠢到爆炸。
今天觉得实在不能忍了,放狗搜了下“excel apply format instead of double click on each column”,总算找到一个解决方案:
1. 选中该列
2. 在“数据”Tab里点击“分列”(按格式将单列文本拆分成多列,英文版是 Text To Columns)
3. 点击完成
搞定