algorithm - 优化 O(n^2) 算法所需的建议

Question

我正在寻求优化目前相当简单的算法 O(n²)。我有一个记录文件，其中每个人都需要 在同一个文件中相互比较。如果两者是 'same'(比较器函数相当复杂)，匹配的 记录输出。请注意，可能有多个记录匹配 彼此，并且没有顺序感 - 仅当匹配为 True 或 False 时。

伪代码:

For (outRec in sourceFile) {
  Get new filePointer for targetFile //starting from the top of the file for inner loop
  For (inRec in targetFile) {
    if (compare(outRec, inRec) == TRUE ) {
      write outRec
      write inRec
    }
    increment some counters
  }
  increment some other counters
}

数据没有以任何方式排序，也没有预处理 可以订购数据。

任何关于这如何变得不那么重要的想法 O(n²)？我正在考虑应用 MapReduce 范式 在代码上，打破外部和内部循环，可能使用 链式映射函数。我很确定我已经弄清楚了代码 Hadoop，但想在花时间编码之前检查替代方案

感谢建议!

添加:记录类型。基本上，我需要匹配名称/字符串。这 匹配类型如下例所示。

1,Joe Smith,Daniel Foster<br/>
2,Nate Johnson,Drew Logan<br/>
3,Nate Johnson, Jack Crank<br/>
4,Joey Smyth,Daniel Jack Foster<br/>
5,Joe Morgan Smith,Daniel Foster<br/>
<br/>
Expected output:
Records 1,4,5 form a match set
End of output

补充:这些文件会很大。最大的文件是 预计将有大约 2 亿条记录。

Answer 1

我不确定你的比较器和数据集的属性，但假设你的比较器在你的行上定义了一个等价关系，这里什么也没有:

1. 为输入文件创建一个映射，并使用比较器函数作为映射的关键比较器。 map 值是行的序列/列表，即所有“相同”的行被连续添加到同一 map 条目)。花费 O(n*log n) 时间。
2. 遍历其他文件的行并检查每一行是否与映射中的键匹配。在这种情况下，由于比较器隐含的等价关系，您知道该行与该映射条目值中的所有行“相同”。需要 O(n* log n + C)，具体取决于您必须输出多少匹配项。

请注意，在最坏的情况下，根据您的问题描述，您无法获得比 O(n^2) 更好的结果，这仅仅是因为您必须输出匹配记录的 O(n^2) 结果!