我有一个涉及生物领域的问题。现在我有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
我想不出一个像样的方法来解决这个问题，所以我现在只是编写了一个 brute-force-stupid-4-layer-nested 循环。我正在考虑按字母顺序对它们进行排序，即使这可能会有所帮助，但很明显，计算机内存不允许我一次加载所有内容。谁能告诉我一种既节省时间又节省空间的好方法来解决这个问题？谢谢！！
首先，我注意到您可以对文件进行排序，而无需一次将其全部保留在内存中，并且大多数操作系统都有一些程序可以执行此操作，通常称为“排序”。通常您可以让它对文件中的字段进行排序，但如果不能，您可以重写每一行以使其按照您想要的方式排序。
鉴于此，您可以通过对两个文件进行排序来连接它们，以便第一个文件在字段 #1 上排序，第二个文件在字段 #2 上排序。然后，您可以为每个匹配项创建一条记录，组合所有字段，并且仅在内存中保存每个文件中的一个块，其中您排序的所有字段都具有相同的值。这将允许您将结果与另一个文件连接 - 四个这样的连接应该可以解决您的问题。
根据您的数据，解决问题所需的时间可能取决于您进行连接的顺序。利用此功能的一种相当幼稚的方法是，在每个阶段从每个文件中抽取一个小的随机样本，并使用它来查看每个可能的连接会产生多少结果，并选择产生最少结果的连接。从大文件中随机抽取 N 个项目的一种方法是，获取文件中的前 N 行，然后，当您到目前为止已读取 m 行时，读取下一行，然后以概率 N/(m + 1) 交换为其保留的 N 行之一，否则将其扔掉。继续阅读，直到读完整个文件。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
