Idiomatische Verwendung von for, während die hohe Leistung erhalten bleibt

Question

Ich habe eine Karte, die nach ihren Schlüsseln sortiert ist und Daten wie diese enthält:

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

Die Karte ist nach Schlüsseln sortiert. Der Schlüssel (die Zahl) kann als die Position interpretiert werden, an der der entsprechende Wert in einem großen Textblock gefunden wurde. Im obigen Beispiel wurde "Text1" an Position 50 im Text gefunden.

Jetzt möchte ich alle Texte finden, die innerhalb von k Positionen voneinander gefunden wurden. Ich definiere eine Funktion wie diese:

     (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"]]

Dies funktioniert, ist aber zu langsam, wenn die Karte m Hunderttausende von Elementen hat. Da die Schleife tatsächlich alle Paare von Elementen in der Karte betrachtet. Da die Karte sortiert ist, ist es für jedes Element in der Karte nicht notwendig, weitere Elemente zu überprüfen, sobald das nächste Element bereits mehr als k Zeichen entfernt ist. Ich konnte eine Version mit loop und recur schreiben. Aber sie ist irgendwie unleserlich. Gibt es einen natürlicheren Weg, dies mit for zu tun? Ich gehe davon aus, dass for (:while ) den Trick machen sollte, war aber nicht in der Lage, einen Weg zu finden.

(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)))))))

Hinweis: Mit einer Karte mit 42K Elementen dauert die erste Version 90 Minuten und die zweite Version 3 Minuten.

Answer 1

Man könnte wahrscheinlich subseq ausnutzen, wenn die Map eine sortierte Map ist.

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

Code nicht benchmarked.

Answer 2

Clojure's for hat auch einen :while Modifier, damit Sie die Iteration mit einer Bedingung stoppen können.

Answer 3

Von allem, was ich aus deinem Beispiel verstanden habe:

(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))