Sha*_*ang 6 sorting algorithm complexity-theory search large-files
我有一个涉及生物学领域的问题.现在我有4个非常大的文件(每个有1亿行),但结构相当简单,这些文件的每一行只有2个字段,都代表一种基因.
我的目标是:设计一个可以实现以下目标的高效算法:在这4个文件的内容中找到一个圆圈.圆圈定义为:
field #1 in a line in file 1 == field #1 in a line in file 2 and
field #2 in a line in file 2 == field #1 in a line in file 3 and
field #2 in a line in file 3 == field #1 in a line in file 4 and
field #2 in a line in file 4 == field #2 in a line in file 1
我想不出一个解决这个问题的好方法,所以我现在只写了一个暴力 - 愚蠢的4层嵌套循环.我正在考虑将它们按字母顺序排序,即使这可能有点帮助,但是很明显计算机内存不允许我一次加载所有内容.有人能告诉我一个以时间和空间有效的方式解决这个问题的好方法吗？谢谢!!
首先，我注意到您可以对文件进行排序，而无需一次将其全部保留在内存中，并且大多数操作系统都有一些程序可以执行此操作，通常称为“排序”。通常您可以让它对文件中的字段进行排序，但如果不能，您可以重写每一行以使其按照您想要的方式排序。
鉴于此，您可以通过对两个文件进行排序来连接它们，以便第一个文件在字段 #1 上排序，第二个文件在字段 #2 上排序。然后，您可以为每个匹配项创建一条记录，组合所有字段，并且仅在内存中保存每个文件中的一个块，其中您排序的所有字段都具有相同的值。这将允许您将结果与另一个文件连接 - 四个这样的连接应该可以解决您的问题。
根据您的数据，解决问题所需的时间可能取决于您进行连接的顺序。利用这一点的一种相当幼稚的方法是，在每个阶段，从每个文件中抽取一个小的随机样本，并使用它来查看每个可能的连接会产生多少结果，并选择产生最少结果的连接。从大文件中随机抽取 N 个项目的一种方法是，获取文件中的前 N 行，然后，当您到目前为止已读取 m 行时，读取下一行，然后以概率 N/(m + 1) 交换为其保留的 N 行之一，否则将其扔掉。继续下去，直到读完整个文件。