Clojure CSV匹配文件

Question

我有两个csv文件，F1文件中有约22K条记录，F2文件中有约50K条记录，两个文件都包含公司名称和地址信息。我需要对名称、地址和电话进行模糊匹配。F1中的每条记录都需要与F2中的每条记录进行模糊匹配。我已经创建了第三个文件R3，它是一个包含模糊匹配规则的csv文件，其中指定了从F1的哪一列到F2的哪一列进行模糊匹配，并设置了一个模糊容差级别。我正在尝试使用for循环来实现这个功能，代码如下 -

(for [j f1-rows
      h f2-rows
      r r3-rows
      :while (match-row j h r)]
  (merge j h))

(defn match-row [j h rules]
  (every?
   identity
   (map (fn [rule]
          (<= (fuzzy/jaccard
           ((keyword (first rule)) j)
           ((keyword (second rule)) h))
          ((nth rule 2))))
    rules)))

f1-rows和f2-rows是map的集合。Rules是包含来自f1、f2的列名和公差级别的序列集合。代码正在按预期运行和工作。但我的问题是，执行时间大约需要2小时。我了解到transducers如何通过消除中间块来提高性能，但我无法想象如何在我的情况下应用它。有什么建议可以让这个过程变得更好/更快吗？

- Amit Shah

Answer 1

:while vs :when

您在这种情况下使用的:while似乎与您所述的问题不符。您的for表达式将在match-row为true时继续进行，并在第一个false结果处完全停止。:when将遍历所有组合，并仅在生成的lazy-seq中包含match-row为true的组合。该差异在此处进行了说明。

例如：

(for [i (range 10)
      j (range 10)
      :while (= i j)]
  [i j]) ;=> ([0 0])

(for [i (range 10)
      j (range 10)
      :when (= i j)]
  [i j]) ;=> ([0 0] [1 1] [2 2] [3 3] [4 4] [5 5] [6 6] [7 7] [8 8] [9 9])

很奇怪你的代码一直运行了两个小时，因为这意味着在这两小时内每次调用 (match-row j h r) 都返回 true，只有最后一次返回 false。建议重新检查结果以确定其是否合理。

需要多长时间？

让我们先做些草稿计算。如果要将 22k 条记录与 55k 条记录进行比较，则必须执行 22k * 55k 次比较，没有任何绕过的方法。

22k * 55k = 1,210,000,000

这是一个非常大的数字！

比较的成本是多少？

从维基百科上简略了解，Jaccard 是关于集合的某种内容。以下估算可以得到一个大致的成本，但可能相当低廉。

(time (clojure.set/difference (set "foo") (set "bar")))

在我的电脑上，这大约需要十分之一毫秒的时间。

(/ (* 22e3 55e3) ;; Number of comparisons.
   10 ; milliseconds
   1000 ;seconds
   60 ;minutes
   60) ;hours
;=> 33.611111111111114

那就是33个半小时。这是一个低估的单个成本估计，并且没有考虑到您想在每个人上比较姓名、地址和电话号码这一事实。所以如果每次比较都在第一行失败，则需要33小时，如果全部到达最后一行，则需要99小时。

在进行任何微观优化之前，您需要通过找到某种聪明的方式来避免需要超过10亿次比较来改进算法。如果您想得到帮助，至少需要提供一些样本数据。

小细节： match-row内部的匿名函数缩进方式令人困惑。我会使用自动缩进的编辑器，并坚持99%的时间使用它，因为Lisp程序员通过缩进来读取嵌套结构，就像Python一样。编辑器/自动缩进器之间存在一些细微差异，但它们都与嵌套结构一致。

(defn match-row [j h rules]
  (every?
   identity
   (map (fn [rule]
          (<= (fuzzy/jaccard
               ((keyword (first rule)) j)
               ((keyword (second rule)) h))
              ((nth rule 2))))
        rules)))

此外，match-row需要在使用之前进行定义（考虑到它能够编译通过，那么它很可能已经被定义了）。

- madstap

Answer 2

22k x 50k超过了10亿种组合。再乘以3个模糊规则，你就需要进行30亿次计算。其中大部分都是浪费的。

唯一加速的方法是对所有组合进行预排序或其他预处理。例如，只有在邮政编码相同的情况下才进行模糊计算。如果你浪费时间试图匹配来自纽约和佛罗里达的人，那么你将浪费99%或更多的工作。

- Alan Thompson

---

感谢madstap和Alan。很有道理。我需要重新设计我的算法。抱歉没有表达清楚。我确实需要while。我只关心第一个匹配项。然后我会继续处理F1的下一条记录，所以我确实需要while。 - Amit Shah

@AmitShah 哇，显然我不知道 :while 如何工作。哈哈，真尴尬。对此感到抱歉。我认为我可以看到改进您的算法的方法，但您必须先发布一些样本数据。 - madstap

嘿嘿！别担心@madstap..我仍然会因此感到困惑并且在这方面跌跌撞撞。我是一个Java程序员，正在尝试Clojure！我已经认真考虑过了，并且快速搜索显示了https://github.com/clojurewerkz/elastisch。所以我正在考虑将我的F2〜50K记录作为文档放入弹性搜索中，并调整映射以返回结果，看看它的表现如何..当我的主要目标只是使用Clojure玩耍并尝试解决实际问题时，深入研究模糊匹配/索引领域对我来说没有意义。 - Amit Shah