2024 Clojure 状态调查! 中分享您的想法。

欢迎!请参阅 关于页面 了解更多关于该功能的信息。

0
core.async
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))))


此函数允许“超出”您正在搜索的键,假设找到“下一个”节点。在简单的链表中选择通常是好的,并且定义良好。然而,跳表允许根据跳跃的大小产生剧烈且非确定性超出。

需要修复为仅在最低链表中进行超出,而不是跳表链接中。

2 答案

0
_由 dpsutton 发表的评论_


{code:java}
{:current {:extra-deps {org.clojure/core.async {:mvn/version "0.4.500"}}}}
  :patched {:extra-deps {:org.clojure/core.async
                            {:git/url "https://github.com/dpsutton/core.async"
                          :sha "e01932e6763cc155b86ef2098df1a49bee0e6d38"}}}}

0
参考: https://clojure.atlassian.net/browse/ASYNC-228 (由 dpsutton 报告)
...