3

我需要计算特定整数对在某些过程中出现的次数（使用局部敏感散列法检测相似图像的启发式方法 - 整数表示图像，下面的“邻居”是具有相同散列值的图像，因此计数表示有多少不同的哈希连接给定的图像对）。

计数存储为从（有序）对到计数（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。in 中的每个整数在nbrs-list任何调用中只出现一次collect（这意味着，在每次调用中，没有任何对出现超过一次）并且整数覆盖范围 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 开销限制”。所以减少内存使用/流失也是一个优先事项:o)

[也许这太具体了？我希望这些课程是一般性的，并且似乎没有很多关于优化“真实”clojure 代码的帖子。此外，我可以分析等，但我的代码看起来很丑，我希望有一个明显的、更干净的方法——特别是对于对扩展。]

4

4 回答 4

3

我猜你想要每对出现的频率？

尝试功能频率。它在后台使用瞬态，这应该避免 GC 开销。

于 2012-05-29T13:11:12.210 回答
1

（希望我没有误解你的问题）

如果您只想这样计算列表中的对，那么 [[1,2,3],[8,9,10]] 是

(defn count-nbr-pairs [n]
   (/ (* n (dec n))
      2))

(defn count-pairs [nbrs-list]
   (apply + (map #(count-nbr-pairs (count %)) nbrs-list)))

(count-pairs [[1 2 3 4] [8 9 10]])
; => 9

这当然假设您不需要删除重复的对。

于 2012-05-29T13:57:01.490 回答
1 
=>(require '[clojure.math.combinatorics :as c])

=>(map #(c/combinations % 2) [[1 2 3] [8 9 10]])

(((1 2) (1 3) (2 3)) ((8 9) (8 10) (9 10)))

这是一个很小的库，看看源代码

性能方面，您正在为 1M 以下的 1K 唯一值的用例查看以下数字

=> (time (doseq
           [i (c/combinations (take 1000 (shuffle (range 1000000))) 2)]))

"Elapsed time: 270.99675 msecs"

这包括生成目标集，这在我的机器上大约需要 100 毫秒。

于 2012-05-29T15:11:02.957 回答
0

上述建议似乎有所帮助，但还不够。我终于得到了不错的表现：

  • 将对打包成一个long值。MAX_LONG > 1e12之所以有效，是因为long实例是可比较的（与哈希键不同，因此可以很好地工作long[2]）。与[n1 n2].

  • 使用TLongByteHashMap原始类型哈希映射并对其进行变异。

  • doseq使用嵌套循环（或for使用不可变数据结构时的嵌套循环）处理对代码。

  • 改进我的位置敏感哈希。问题的很大一部分是它太弱了，所以找到了太多的邻居 - 如果一百万张图像的邻居受到不良约束，那么你会得到一百万对，这会消耗太多内存......

内部循环现在看起来像：

(doseq [i (range 1 (count nbrs))]
  (doseq [j (range i)]
    (let [pair (pack size (nth nbrs i) (nth nbrs j))]
      (if-let [value (.get matches pair)]
        (.put matches pair (byte (inc value)))
        (.put matches pair (byte 0))))))

在哪里

(defn- pack
  [size n1 n2]
  (+ (* size n1) n2))

(defn- unpack
  [size pair]
  [(int (/ pair size)) (mod pair size)])
于 2012-05-29T23:24:55.050 回答