Necesito contar el número de veces que ocurren determinados pares de enteros en algún proceso (una heurística que detecta imágenes similares utilizando el hashing sensible a la ubicación: los enteros representan imágenes y los "vecinos" a continuación son imágenes que tienen el mismo valor de hash, por lo que el conteo indica Cuántos hashes diferentes conectan el par de imágenes dado).

Los conteos se almacenan como un mapa de (ordenado) par a contar (matches abajo).

La entrada (nbrs-list a continuación) es una lista de una lista de enteros que se consideran vecinos, donde se debe contar cada par distinto (ordenado) en la lista interna ("los vecinos"). Entonces, por ejemplo, sinbrs-list es[[1,2,3],[10,8,9]] entonces las parejas son[1,2],[1,3],[2,3],[8,9],[8,10],[9,10].

La rutinacollect se llama varias veces; lamatches parámetro acumula resultados y lanbrs-list Es nuevo en cada llamada. El número más pequeño de vecinos (tamaño de la lista interna) es 1 y el más grande ~ 1000. Cada entero ennbrs-list ocurre solo una vez en cualquier llamada acollect (esto implica que, en cada llamada, ningún par ocurre más de una vez) y los enteros cubren el rango de 0 - 1,000,000 (por lo tanto, el tamaño denbrs-list es menos de 1,000,000, ya que cada valor aparece solo una vez y algunas veces aparecen en grupos, pero generalmente son más de 100,000, ya que la mayoría de las imágenes no tienen vecinos.

He eliminado las rutinas de un trozo más grande de código, por lo que pueden contener pequeños errores de edición, lo siento.

(defn- flatten-1
  [list]
  (apply concat list))

(defn- pairs
  ([nbrs]
    (let [nbrs (seq nbrs)]
      (if nbrs (pairs (rest nbrs) (first nbrs) (rest nbrs)))))
  ([nbrs a bs]
    (lazy-seq
      (let [bs (seq bs)]
        (if bs
          (let [b (first bs)]
            (cons (if (> a b) [[b a] 1] [[a b] 1]) (pairs nbrs a (rest bs))))
          (pairs nbrs))))))

(defn- pairs-map
  [nbrs]
  (println (count nbrs))
  (let [pairs-list (flatten-1 (pairs nbrs))]
    (apply hash-map pairs-list)))

(defn- collect
  [matches nbrs-list]
  (let [to-add (map pairs-map nbrs-list)]
    (merge-with + matches (apply (partial merge-with +) to-add))))

Así que el código anterior expande cada conjunto de vecinos a pares ordenados; crea un mapa de pares a1; luego combina mapas usando la suma de valores.

Me gustaría que esto corra más rápido. No veo cómo evitar la expansión de pares O (n ^ 2), pero me imagino que puedo al menos reducir la sobrecarga constante al evitar tantas estructuras intermedias. Al mismo tiempo, me gustaría que el código fuera bastante compacto y legible ...

Ah, y ahora estoy superando el "límite de gastos generales del GC". Por lo tanto, reducir el uso de la memoria / la rotación es también una prioridad: o)

[Tal vez esto es demasiado específico? Espero que las lecciones sean generales y que no parezcan muchas publicaciones sobre cómo optimizar el código de clojure "real". Además, puedo perfilar, etc., pero mi código parece tan feo que espero que haya un enfoque obvio y más limpio, especialmente para la expansión de pares.]