Idiomatic way to use for, while still maintaining high performance

Question

I have a map that is sorted by its keys which contains data like this: ``` (def h {50 Text1 70 Text2 372 Text1 391 Text2 759 Text1 778 Text2 }) ``` The map is sorted by Keys. The key (the number) can be interpreted as the position where the corresponding value was found in a large block of text. In the above example, "Text1" was found at position 50 in the text. Now, I want to find all Texts that were found within k positions of each other. I define a function a like this: ``` (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"]] ``` This works, but is too slow when the map m has 100s of thousands of elements. Because the for loop actually looks at all pairs of elements in the map. Since the map is sorted, for each element in the map, it is not necessary to check further elements, once the next element is…

Accepted Answer

One could probably exploit `subseq` when the map is a sorted-map.

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

Code not benchmarked.

Idiomatic way to use for, while still maintaining high performance

Solution

Problem