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

Question

我希望优化一个相当简单的算法,目前是 O(n ²).我有一个记录文件,每个记录需要在同一个文件中相互比较.如果两者是'相同'(比较器功能非常复杂),则输出匹配的记录.请注意,可能存在多个彼此匹配的记录,并且没有顺序感 - 仅当匹配为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范例,分解外部和内部循环,可能使用链式Map函数.我很确定我已经在Hadoop上找到了代码,但是在我花时间编码之前想要检查替代方案.

建议赞赏!

补充:记录类型.基本上,我需要匹配名称/字符串.匹配类型如下例所示.

1,Joe Smith,Daniel Foster

2,Nate Johnson,Drew Logan

3,Nate Johnson, Jack Crank

4,Joey Smyth,Daniel Jack Foster

5,Joe Morgan Smith,Daniel Foster



Expected output:
Records 1,4,5 form a match set
End of output

补充:这些文件会非常大.最大的文件预计将有大约2亿条记录.

Answer 1

假设文件不是大得离谱，我会完整地浏览文件，计算该行的哈希值，并跟踪哈希/行号（或文件指针位置）组合。然后对哈希列表进行排序，并识别那些出现多次的哈希。