Cljs 定时器跳表存在一个明显的错误:没有递归的循环
{code:java}
(let [x (skip-list-node k v (make-array new-level))]
(loop [i 0]
(when (<= i level)
(let [links (.-forward (aget update i))]
(aset (.-forward x) i (aget links i))
(aset links i x)))))
这来自 `put` 函数。这通常是一个糟糕的错误,但 Links 在 0 位置的链接只是简单的链表链接,它省略了跳表的“跳”。一个简单的修补程序可以修复它,从 when 表达式递归。
这会对 ceilingEntry 函数产生影响
{code:java}
(ceilingEntry [coll k]
(loop [x header level level]
(if-not (neg? level)
(let [nx (loop [x x]
(let [x' (when (< level (alength (.-forward x)))
(aget (.-forward x) level))]
(when-not (nil? x')
(if (>= (.-key x') k)
x'
(recur x')))))]
(if-not (nil? nx)
(recur nx (dec level))
(recur x (dec level))))
(when-not (identical? x header)
x))))
此函数允许“超出”您正在搜索的键,假设找到“下一个”节点。在简单的链表中选择通常是好的,并且定义良好。然而,跳表允许根据跳跃的大小产生剧烈且非确定性超出。
需要修复为仅在最低链表中进行超出,而不是跳表链接中。