生成循环对列表的算法

Question

Given a text file in the format below, each line is a list of up to 50 names. Write a program produces a list of pairs of names which appear together in at least fifty different lists.

Tyra,Miranda,Naomi,Adriana,Kate,Elle,Heidi
Daniela,Miranda,Irina,Alessandra,Gisele,Adriana

In the above sample, Miranda and Adriana appear together twice, but every other pair appears only once. It should return "Miranda,Adriana\n". An approximate solution may be returned with lists which appear at least 50 times with high probability.

我想到了以下解决方案:

1. 生成 Map <Pair,Integer> pairToCountMap，在通读文件之后。

2. 遍历 map ，并打印那些计数 >= 50 的 map

有更好的方法吗？该文件可能非常大，我不确定近似解决方案是什么意思。任何链接或资源将不胜感激。

Answer 1

首先让我们假设名称的长度是有限的，因此对它们的操作是常数时间。

如果适合内存，您的答案应该是可以接受的。如果您有 N 行，每行都有 m 个名称，则您的解决方案应该需要 O(N*m*m) 才能完成。

如果该数据集不适合内存，您可以将这些对写入一个文件，使用合并排序对该文件进行排序，然后扫描以计算对。其运行时间为 O(N*m*log(N*m))，但由于有关磁盘访问速度的详细信息，在实践中运行速度会快得多。

如果您有一个分布式集群，那么您可以使用 MapReduce。它的运行方式与上一个解决方案非常相似。

至于统计方法，我的猜测是它们意味着遍历文件列表以查找每个名称的频率，以及其中包含不同名称的行数。如果我们假设每一行都是随机组合的名字，使用统计数据我们可以估计任何一对普通名字之间有多少交集。这与文件的长度大致成线性关系。