Python中的归并排序

Question

基本上，我有很多文件，每个文件里都包含一些域名。我已经根据每个文件的顶级域名（TLD）进行了排序，使用了.sort(key=func_that_returns_tld)这个方法。

现在我完成了排序，想把所有的文件合并成一个大的、已经排序好的文件。我想我需要做一些类似这样的事情：

open all files
read one line from each file into a list
sort list with .sort(key=func_that_returns_tld)
output that list to file
loop by reading next line

我这样想对吗？如果有任何建议可以帮我实现这个目标，我会很感激。

Answer 1

除非你的文件大得让人无法理解，否则它会被加载到内存中。

你的伪代码看起来很难懂，请把它缩进整理好。最后那句“通过读取下一行来循环”没有意义。

基本上就是这样。

all_data= []
for f in list_of_files:
    with open(f,'r') as source:
        all_data.extend( source.readlines() )
all_data.sort(... whatever your keys are... )

你完成了。你可以把 all_data 写入一个文件，或者继续处理它，或者做你想做的任何事情。

Answer 2

另一个选择（同样适用于你的数据无法全部放进内存的情况）是创建一个 SQLite3 数据库，在那里进行排序，然后再把结果写入文件。

Answer 3

如果你的文件不太大，那就直接把它们全部读到内存里（就像S. Lott建议的那样）。这样做肯定是最简单的。

不过，你提到的排序会生成一个“巨大的”文件。如果这个文件大到无法放进内存，那你可以考虑使用 heapq.merge。虽然设置起来可能稍微复杂一点，但它的好处是可以避免一次性把所有的数据都加载到内存中。

import heapq
import contextlib

class Domain(object):
    def __init__(self,domain):
        self.domain=domain
    @property
    def tld(self):
        # Put your function for calculating TLD here
        return self.domain.split('.',1)[0]
    def __lt__(self,other):
        return self.tld<=other.tld
    def __str__(self):
        return self.domain

class DomFile(file):
    def next(self):
        return Domain(file.next(self).strip())

filenames=('data1.txt','data2.txt')
with contextlib.nested(*(DomFile(filename,'r') for filename in filenames)) as fhs:
    for elt in heapq.merge(*fhs):
        print(elt)

这里是data1.txt的内容：

google.com
stackoverflow.com
yahoo.com

还有data2.txt的内容：

standards.freedesktop.org
www.imagemagick.org

结果是：

google.com
stackoverflow.com
standards.freedesktop.org
www.imagemagick.org
yahoo.com