Preciso contar o número de vezes que determinados pares de inteiros ocorrem em algum processo (uma heurística que detecta imagens similares usando hashing-inteiros sensíveis à localidade representa imagens e os "vizinhos" abaixo são imagens que possuem o mesmo valor de hash, então a contagem indica quantos hashes diferentes conectam o par de imagens fornecido).

As contagens são armazenadas como um mapa de um par (ordenado) para contar (matches abaixo).

A entrada (nbrs-list abaixo) é uma lista de uma lista de inteiros que são considerados vizinhos, onde cada par distinto (ordenado) na lista interna ("os vizinhos") deve ser contado. Então, por exemplo, senbrs-list é[[1,2,3],[10,8,9]] então os pares são[1,2],[1,3],[2,3],[8,9],[8,10],[9,10].

A rotinacollect é chamado várias vezes; amatches parâmetro acumula resultados eonbrs-list é novo em cada chamada. O menor número de vizinhos (tamanho da lista interna) é 1 e o maior ~ 1000. Cada inteiro emnbrs-list ocorre apenas uma vez em qualquer chamada paracollect (isso implica que, em cada chamada, nenhum par ocorre mais de uma vez) e os inteiros cobrem o intervalo de 0 a 1.000.000 (portanto, o tamanhonbrs-list é menor que 1.000.000 - já que cada valor ocorre apenas uma vez e às vezes eles ocorrem em grupos - mas tipicamente maiores que 100.000 - já que a maioria das imagens não tem vizinhos).

Eu tirei as rotinas de um grande pedaço de código, então elas podem conter pequenos erros de edição, desculpe.

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

Portanto, o código acima expande cada conjunto de vizinhos para pares ordenados; cria um mapa de pares para1; Em seguida, combina mapas usando a adição de valores.

Eu gostaria que isso fosse mais rápido. Não vejo como evitar a expansão de pares O (n ^ 2), mas imagino que posso pelo menos reduzir a sobrecarga constante evitando tantas estruturas intermediárias. Ao mesmo tempo, gostaria que o código fosse razoavelmente compacto e legível ...

Ah, e agora estou excedendo o "limite de sobrecarga do GC". Portanto, reduzir o uso / rotatividade de memória também é uma prioridade: o)

[Talvez isso seja específico demais? Eu espero que as lições sejam gerais e não pareçam muitas postagens sobre como otimizar o código clojure "real". Além disso, posso criar um perfil, etc., mas meu código parece tão feio que espero que exista uma abordagem óbvia e mais limpa - especialmente para a expansão de pares.]