Мне нужно посчитать, сколько раз определенные пары целых чисел встречаются в каком-либо процессе (эвристика, обнаруживающая похожие изображения с использованием хеширования, чувствительного к локальности - целые числа представляют изображения, а нижеприведенные «соседи» - это изображения, имеющие одинаковое значение хэша, поэтому количество указывает, сколько разных хэшей соединяют данную пару изображений).

Счет хранится в виде карты из (упорядоченной) пары для подсчета (matches ниже).

Вход (nbrs-list ниже) представляет собой список из целых чисел, которые считаются соседями, где каждая отдельная (упорядоченная) пара во внутреннем списке («соседи») должна быть подсчитана. Так, например, еслиnbrs-list является[[1,2,3],[10,8,9]] тогда пары[1,2],[1,3],[2,3],[8,9],[8,10],[9,10].

Рутинаcollect вызывается несколько раз;matches параметр накапливает результаты иnbrs-list новый на каждый звонок. Наименьшее количество соседей (размер внутреннего списка) равно 1, а наибольшее ~ 1000. Каждое целое число вnbrs-list происходит только один раз при любом вызовеcollect (this implies that, on each call, no pair occurs more than once) и целые числа охватывают диапазон от 0 до 1 000 000 (поэтому размерnbrs-list меньше 1 000 000 - поскольку каждое значение встречается только один раз, а иногда они встречаются в группах (но обычно больше 100 000 - поскольку большинство изображений не имеют соседей).

Я вытащил подпрограммы из большей части кода, поэтому они могут содержать небольшие ошибки редактирования, извините.

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

Таким образом, приведенный выше код расширяет каждый набор соседей до упорядоченных пар; создает карту из пар в1; затем объединяет карты, используя сложение значений.

Мне бы хотелось, чтобы это работало быстрее. Я не вижу, как избежать расширения пар O (n ^ 2), но я думаю, что могу, по крайней мере, уменьшить постоянные издержки, избегая так много промежуточных структур. В то же время я хотел бы, чтобы код был достаточно компактным и читабельным ...

О, и теперь я превышаю "предел накладных расходов GC". Поэтому сокращение использования памяти / оттока также является приоритетом: о)

[Может быть, это слишком конкретно? Я надеюсь, что уроки носят общий характер и, похоже, не так много сообщений об оптимизации "реальной" ситуации. закрытый код. Кроме того, я могу профилировать и т. Д., Но мой код кажется таким уродливым, что я надеюсь, что есть очевидный, более чистый подход - особенно для расширения пар.]