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

Question

我希望优化一个当前时间复杂度为O(n²)的相当简单的算法。我有一份记录文件，其中每个记录需要与同一文件中的所有其他记录进行比较。如果两者是“相同”的（比较函数相当复杂），则输出匹配的记录。请注意，可能会有几个记录彼此匹配，没有顺序之分 - 只有匹配的真假。

伪代码：

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^2)？我考虑在代码中应用MapReduce模式，将外部和内部循环分开，并可能使用链式Map函数。我相当确定已经在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亿条记录。

- banncee

---

请给我一个记录的例子。您必须知道，您可以以任何方式对数据进行排序，并且其时间复杂度将为O(n*log(n))。 - TheHorse

你不能将整个文件读入集合中吗？然后你可以简单地对集合进行排序并迭代它，以查看哪些相邻元素是重复的。这将把时间复杂度从 O(n*n) 改为 O(n*log(n))。 - Bart Kiers

如果真的没有办法对你的集合进行排序（使用哈希等技术），那么它将始终保持为O(n^2)，因为您必须将每个元素与每个其他元素进行比较。这意味着你的复杂度是“n选2”=n!/(2!(n-2)!) = n(n-1)/2 = 0.5n^2 - 0.5n == O(n^2)。 - iolo

我们需要更多关于比较器的细节。比较器函数的细节将决定这可以被优化多少。例如，如果它是按字节的标识，您可以使用哈希。如果有字段的顺序不重要，您可以在排序字段后使用哈希。如果文件等效于描述程序给予另一个文件时失败后一百万步... 那么很难进行优化。 - Craig Gidney

文件将会非常庞大。我无法将它们读入内存中的集合中。对于记录进行“排序”（如果可能的话）不会产生重复的内容，以便轻松地提取出来。结果可以是“接近”或“模糊”的匹配。 - banncee

Answer 1

我不确定您的比较器和数据集属性，但假设您的比较器在行上定义了一个等价关系，那么请看以下步骤：

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

需要注意的是，在最坏的情况下，根据您的问题描述，您无法获得比O(n^2)更好的结果，因为可能有O(n^2)个匹配记录结果需要输出！

- Frank

---

嗯...有趣的可能性。我会研究一下！ - banncee

一个地图要么基于树，要么基于哈希表，而这个问题不适合使用排序函数或哈希函数。 - Mark Ransom

@Mark Ransom：我刚刚在查看Map实现，我很确定你是对的——我的比较函数只返回了T或F，而没有返回一个排序。 - banncee

@cbannerjee 但它是否可哈希？这是一个不同于排序的属性。 - Nick Johnson

Answer 2

假设文件不是非常大，我会遍历整个文件，并为每一行计算一个哈希值，并跟踪哈希/行号（或文件指针位置）的组合。然后对哈希列表进行排序，并识别出出现多次的哈希值。

- Joe

---

由于哈希冲突，这种方法不起作用。为什么不使用哈希表呢？ - Patrick

问题是设计一个只查看一个记录的哈希函数是不可能的（至少，我不知道如何做到）。此外，比较函数在bytes(A) != bytes(B)时也可能返回true。 - banncee

结果证明，一个相当简单的MinHash类型方案效果还不错。它不能捕捉所有的“重复项”，但对于政府工作来说已经足够好了... - banncee

Answer 3

我们需要了解更多关于您的比较函数的信息。您的比较是否具有传递性？（也就是说，A==B和B==C是否意味着A==C？）它是否具有自反性？（是否意味着A==B意味着B==A？）

如果您的比较函数具有传递性和自反性，并且许多记录相等是常见的情况，则可以通过将记录与一组“代表样本”进行比较来将其分组。在最好的情况下，这可能接近O(N)。

请注意，哈希记录假定哈希（A）==哈希（B）<=> compare（A，B）== true，但如果当bytes（A）！= bytes（B）时compare（A，B）仍然为true，那么设计一个合适的哈希算法可能会很棘手。

- Dennis

---

该函数是可传递和自反的。问题在于比较函数可以在 bytes(A) != bytes(B) 的情况下返回 true。事实上，这个想法是要识别“相似”的 A 和 B。 - banncee

@cbannerjee: 你确定它是可传递的吗？字符串相似度测量通常不是可传递的。例如，如果“Joey”类似于“Joesy”，而“Joesy”类似于“Joshy”，“Joshy”又类似于“Josh”，那么是否可以推断出“Joey”与“Josh”也相似呢？ - Steve Jessop

我建议基于分组来做。这里有另一个分组建议：将32位或64位整数定义为一组位标志，指示某些区别特征的存在，这些特征可能意味着记录是相似的。然后根据它们的位掩码的相似性决定首先比较哪些记录。(按bitcount(mask(A) & mask(B))的顺序进行比较。) 这就像哈希，但是模糊的。编辑：您可能需要查看AI技术或数据挖掘技术，而不是将其表述为算法问题。 - Dennis

@Steve Jessop：你是对的。它不是传递性的，但它是自反的。我想我是本能地做出了反应 <呻吟/>。 - banncee

Answer 4

FYI MapReduce不会提高解决方案的算法复杂度。它增加了一些开销，但是并行化使得你可以在较短的墙钟时间内使用必要的资源。

为了改善您的墙钟时间，首要的事情是找到避免运行比较的方法。任何这样做的方式都将是一个胜利。即使您的比较逻辑很复杂，您仍然可以使用排序来帮助。

例如，假设您有一些数据可能分散在某个维度中。那么在该维度上变化太大的数据保证是不相等的，尽管在该维度上接近并不保证相等。那么您可以按照该维度对数据进行排序，然后只在在该维度上接近的元素之间运行比较。万事大吉！大部分的O(n*n)比较现在已经消失了。

让我们把它变得更复杂。假设您可以确定两个相互独立的维度。按第一个这样的维度对数据进行排序。在第一维中将数据划分成条带(通过最大差异来重叠条带，并且仍然能够进行比较)。现在获取每个条带并按第二维对其进行排序。然后在第二维中接近的元素之间运行比较，并且如果相等，将该对包含在您的答案中，并且这是它可能出现的第一个条带。(需要去重逻辑，因为重叠可能意味着一个相等的对可能出现在多个条带中。)这很可能比第一种方法更好，因为您已经成功地缩小了范围，以便仅比较与少量“附近”行。

如果您想使用更少的资源，您需要专注于避免实际进行单独比较的方法。你走这条路上想到的任何事情都会有所帮助。

- btilly

---

仅仅对数据进行排序可能并不能帮助解决问题，因为输入数据具有极大的变异性。理想情况下，可以对字段进行字母表排序，并为每一行分配某种类型的哈希函数，然后根据该哈希值进行排序。不幸的是，我很难想出一个聪明的哈希函数来实现这个目标。 - banncee

如果数据具有变异性，并且您有可以排序的内容，并明确表示“此行不必与比那更远的任何东西进行比较”，则排序将有很大帮助。如果没有，还有许多其他技巧的变化可能会有所帮助。但是，在不知道有关您的比较函数的任何有用信息的情况下，列举可能性是没有意义的。 - btilly

Answer 5

正如你已经提到的，你不会有幸得到比O(n^2)更好的结果，但你可以并行化处理。

我有一个可行的解决方案，它可以与HDFS一起使用，你可以通过使用分布式缓存来扩展它。

public class MatchImporter extends Mapper<LongWritable, Text, Text, Text> {

FileSystem fs;
private BufferedReader stream;

@Override
protected void setup(Context context) throws IOException,
        InterruptedException {
    fs = FileSystem.get(context.getConfiguration());
}

private void resetFile() throws IOException {
    if (stream != null)
        stream.close();
    stream = new BufferedReader(new InputStreamReader(fs.open(new Path(
            "files/imp/in/target.txt"))));
}

private boolean compare(Text in, String target) {
    return target.contains(in.toString());
}

enum Counter {
    PROGRESS
}

@Override
protected void map(LongWritable key, Text value, Context context)
        throws IOException, InterruptedException {

    resetFile();
    String line = null;
    while ((line = stream.readLine()) != null) {
        // increment a counter to don't let the task die
        context.getCounter(Counter.PROGRESS).increment(1);
        context.progress();
        if (compare(value, line)) {
            context.write(new Text(line), value);
        }
    }
}

public static void main(String[] args) throws Exception {
    Configuration conf = new Configuration();
    Job job = new Job(conf);

    job.setMapperClass(MatchImporter.class);
    job.setReducerClass(Reducer.class);
    job.setJarByClass(MatchImporter.class);

    Path in = new Path("files/imp/in/source.txt");
    Path out = new Path("files/imp/out/");

    FileInputFormat.addInputPath(job, in);
    FileSystem fs = FileSystem.get(conf);
    if (fs.exists(out))
        fs.delete(out, true);

    SequenceFileOutputFormat.setOutputPath(job, out);
    job.setInputFormatClass(TextInputFormat.class);
    job.setOutputFormatClass(TextOutputFormat.class);
    job.setOutputKeyClass(Text.class);
    job.setOutputValueClass(Text.class);

    job.waitForCompletion(true);
}

}

使用 source.txt 中的输入：

thomas
phil
jen
james
christian
stefan
stephan
john

和 target.txt

john meat
jay hardly

将导致减速器输出为：

john meat   john

诀窍在于您可以拆分源文件并并行执行比较操作。这将使速度提高，但不会改善大O。

这里有一个重要的提示： 您必须使用计数器报告进度，因为与整个文件进行比较可能需要很长时间。这将防止您的任务在分布式环境中失败。

小提示： 尝试将源文件拆分为64m块，并将目标文件设置为sequencefile。这将获得很多加速，您需要重新编写读取内容。

祝您好运！

- Thomas Jungblut

---

这正是我所想的-再次感谢！ 我将研究sequenceFile作为目标，以使迭代尽可能快。另外一件相关的事，我仍然很想尝试MapReduce目标文件，以进一步并行化解决方案。 - banncee

如果你需要帮助，随时可以再来问相关问题。我很乐意为您提供帮助。 - Thomas Jungblut

谢谢！我将实现自定义Reducer，然后就可以了。如果我搞清楚如何对目标文件进行MapReduce，我一定会告诉你！ - banncee

Answer 6

只需遍历文件中的每个记录并将它们插入哈希表中。在每一步中，检查记录是否已经在哈希表中。如果是，则输出它。这可以在O(n)时间内完成。

- tskuzzy

---

+1. OP需要编写一个适当的哈希函数（根据比较的细节）。但是哈希函数不需要完美；即使存在一些冲突，这仍然应该是一种改进。 - Gareth Rees

问题就在这里。我不认为有一种方法可以创建哈希函数......如果你看一下数据，我不确定哈希如何生成以落入“近似”类型的情况。 - banncee

哦，当我读到“相同”时，我以为它是一个等价关系并暗示了传递性。如果它不是一个等价关系，那么就会变得非常棘手... - tskuzzy

将每行拆分成名称，对每个名称应用规范化转换（如soundex），并在每个名称下标出该行。 - Gareth Rees

Answer 7

正如btilly所指出的那样，你并不需要传递性来分类记录。对于英国人的名字，你可以用两个缩写来表示每个名字，并使用排序后的缩写列表来表示每个记录。然后，你只需要在同一类别中运行完整的O（N^2）记录比较即可。存在一个额外的问题，即相同的记录对可以出现在多个类别中，但通过维护单独的匹配记录对集合（由记录索引标识），很容易检测到。

在这个例子中，你会将记录1放入“DF,JS”类，将记录2放入“DL,NJ”类，将记录3放入“JC,NJ”类，将记录4放入“DJ,JS”、“JF,JS”和“DF,JS”类，将记录5放入“DF,JM”、“DF,JS”和“DF,MS”类。你得到了总共7个类别：“DF,JM”，“DF,MS”，“DF,JS”，“DJ,JS”，“DL,NJ”，“JC,NJ”，“JF,JS”，其中只有“DF,JS”类包含多个记录，即记录1、4和5。因此，在这个例子中，你只需要运行两次完整的比较函数。

另一方面，人们有奇怪的名字这个问题。无论你做什么，都会错过一些匹配项。如果您以前没有看过它，这篇关于此主题的博客文章值得一看。

- han

Answer 8

您还没有提到预期匹配输入的百分比，或者精确匹配与不精确匹配的频率。如果您可以进行一些预处理来减少问题规模，那么这可能会大有帮助。

如果您只是对输入进行排序，并在相邻条目上运行比较函数，那么您可能会剔除足够多的重复项，使n^2的第二次遍历变得可承受。

- Mark Ransom

---

我正在尝试回到源代码，使数据集变小，并且看看是否有一些聪明的方法可以先进行排序，以使比较次数更少... - banncee

Answer 9

如果你真的无法做出比等价关系更好的处理，那么最坏情况下你的时间复杂度将始终为O(n^2)——例如，在没有匹配项的情况下，你需要比较每一对来确保没有匹配。 (正如人们所提到的，你可以并行化这个过程，但对于数亿条记录来说，这仍然不是特别容易处理的；也许把资源用在这种方式上并不值得）。

通常，有更好的方法来解决这个问题。

如果你确实有一个等价关系（也就是说，如果有一个逻辑保证，如果match(a,b)=match(b,c)=true，则match(a,c)也为true），那么你可能可以将你的记录转换为某个规范形式，这个形式适用于哈希和/或排序。

在你的例子中，你似乎是在匹配"Joe Smith"的变体。如果是这样，你可能可以扩展你的比较标准，选择一个等价类的特定成员来代表整个类。例如，选择"JOSEPH"来代表所有等价于"Joe"的名字，"SMITH"来代表所有等价于"Smythe"的名字等等。

一旦进行了这种转换，您可以使用哈希表将操作减少到O(n)，而不是O(n^2)。

- comingstorm

---

问题在于该函数不是可传递的。我正在尝试通过回到客户端并解释N^2增长的性质来减少问题规模，然后稍后合并结果。我还试图想出某种哈希函数，它将允许我“条纹化”排序数据并在哈希的某个预定义范围内进行比较。 - banncee

Answer 10

感谢所有的建议。
经过筛选，考虑到时间限制，最好的方法是使用MapReduce框架来并行化问题，并增加更多的硬件。我知道这并不能减少O(n²)的复杂度。
我能想到的唯一可能的解决方案是对数据运行某种类型的minHash，将数据分成重叠的部分，并在条纹和重叠中进行比较。这应该可以减少比较的次数，但我不确定哈希运行的代价会有多大。

- banncee