惯用的方式,同时仍保持高性能

Question

我有一个按其键排序的地图,其中包含如下数据:

    (def h {50 Text1
    70 Text2
    372 Text1
    391 Text2
    759 Text1
    778 Text2
    })

地图按键排序.键(数字)可以解释为在大块文本中找到相应值的位置.在上面的例子中,在文本的第50位找到"Text1".

现在,我想找到在彼此的k个位置内找到的所有文本.我定义了一个像这样的函数:

     (defn nearest [m k]
         (for [m1 (keys m) m2 (keys m)
              :when (and (> m2 m1) (not= (m m1) (m m2)) (< (- m2 m1) k))]
              [m1 (get m m1)  m2 (get m m2)]))

     (nearest h 50)
     ; [[50 "Text1" 70 "Text2"] [372 "Text1" 391 "Text2"] [759 "Text1" 778 "Text2"]]

这有效,但是当地图m有数千个元素时,它太慢了.因为for循环实际上是查看地图中的所有元素对.由于对地图进行了排序,因此对于地图中的每个元素,一旦下一个元素已经超过k个字符,就不必检查更多元素.我能够使用循环和重复编写一个版本.但它有点难以理解.是否有一种更自然的方式来执行此操作？我假设(:while)应该做的伎俩,但无法找到方法.

(defn nearest-quick [m k]
      (let [m1 (keys m) m2 (keys m)]
        (loop [inp m res []  i (first m1) m1 (rest m1) j (first m2) m2 (rest m2)]
          (cond
            (nil? i) res
            (nil? j)(recur inp res (first m1) (rest m1) j m2)
            (= i j) (recur inp res i m1 (first m2) (rest m2))
            (< j i) (recur inp res i m1 (first m2) (rest m2))
            (= (inp i) (inp j)) (recur inp res i m1 (first m2) (rest m2))
            (< (- j i) k) (recur inp (conj res [i (inp i) j (inp j)]) i m1 (first m2) (rest m2))
            (>= (- j i) k) (recur inp res (first m1) (rest m1) (first (rest m1)) (rest (rest m1)))))))

注意:使用带有42K元素的地图,第一个版本需要90分钟,第二个版本需要3分钟.

Answer 1

subseq当地图是有序地图时,人们可能会利用它.

(defn nearest
  [m n]
  (for [[k v]   m
        [nk nv] (subseq m < k < (+ k n))
        :when (not= v nv)]
    [k v nk nv]))

代码没有基准.