4

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

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

地图按键排序。键（数字）可以解释为在大文本块中找到相应值的位置。在上面的示例中，“Text1”位于文本的第 50 位。

现在，我想查找在彼此的 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 个字符，就不需要检查更多元素。我能够使用循环和递归编写一个版本。但这有点不可读。有没有更自然的方法来做到这一点？我假设 for (: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 分钟。

4

3 回答 3

6

subseq当地图是排序地图时，可能会利用这一点。

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

代码未进行基准测试。

于 2013-04-24T15:26:45.503 回答
2

Clojurefor也有一个:while修饰符，因此您可以使用条件停止迭代。

于 2013-04-24T15:51:50.747 回答
0

从我从你那里了解到的任何例子：

(def h (sorted-map 50 "Text1"
                   70 "Text2"
                   372 "Text1"
                   391 "Text2"
                   759 "Text1"
                   778 "Text2"))


(->> (map #(-> [%1 %2]) h (rest h))
     (filter (fn [[[a b] [x y]]] (< (- x a) 50)))
     (map flatten))
于 2013-04-24T15:43:18.520 回答