如何对大数据集进行分组

Question

我有一个简单的文本文件，里面有两列，都是整数。

1 5
1 12
2 5
2 341
2 12

还有其他内容……

我需要根据第二列的值对数据进行分组，输出结果应该是这样的。

5 1 2
12 1 2
341 2

现在的问题是，这个文件非常大，差不多有34GB。我尝试写了一个Python脚本，把数据分组到一个字典里，字典的值是整数数组，但这样做还是太慢了。（我猜是因为在分配array('i')和用append扩展数组时花了很多时间。）

我现在打算写一个Pig脚本，准备在一个伪分布式的Hadoop机器上运行（一个亚马逊EC3高内存大实例）。

data = load 'Net.txt';
gdata = Group data by $1; // I know it will lead to 5 (1,5) (2,5) but thats okay for this snippet
store gdata into 'res.txt';

我想知道有没有更简单的方法来做到这一点。

更新：把这么大的文件放在内存里是不可能的。对于Python的解决方案，我计划进行4次运行，第一次只考虑第二列值在1到1000万之间的数据，下一次考虑1000万到2000万的数据，依此类推。但这样做真的很慢。

Pig/Hadoop的解决方案很有趣，因为它大部分数据都保存在磁盘上。

为了更好地理解，这个数据集包含了大约4500万Twitter用户的连接信息，文件中的格式意味着第二个数字所代表的用户ID正在关注第一个用户。

我使用的解决方案：

class AdjDict(dict):
    """
     A special Dictionary Class to hold adjecancy list
    """
    def __missing__(self, key):
        """
        Missing is changed such that when a key is not found an integer array is initialized
        """
        self.__setitem__(key,array.array('i'))
        return self[key]

Adj= AdjDict()

for line in file("net.txt"):
    entry =  line.strip().split('\t')
    node = int(entry[1])
    follower = int(entry[0])
    if node < 10 ** 6:
        Adj[node].append(follower)

# Code for writting Adj matrix to the file:

Answer 1

也许你可以对文件进行多次处理。

每次处理时选择一段键，比如说你选择的范围大小是100。

第一次处理 - 计算所有从0到99的键
第二次处理 - 计算所有从100到199的键
第三次处理 - 计算所有从200到299的键
第四次处理 - 计算所有从300到399的键
……依此类推。

对于你的例子，第一次处理的结果会是

5 1 2
12 1 2

而第四次处理的结果会是

341 2

选择范围大小时，要确保你创建的字典能放进你的内存里。

我建议不要用多线程来加速处理，除非你的硬盘非常快，因为这可能会受到输入输出的限制，结果只是让硬盘忙得不可开交。

Answer 2

如果我想在现在的电脑上解决这个问题，我可能会写几个小程序：

第一个程序会处理文件的500兆字节的小块，交换列并把结果写到新的文件里。（你会得到70个或更多的文件。）（这不会占用太多内存。）

然后我会对每个小文件使用操作系统自带的 sort(1) 命令进行排序。（这可能会占用几GB的内存。）

接着，我会写一个合并排序的程序，把所有70多个子文件中的行合并在一起。（这不会占用太多内存。）

最后，我会写一个程序，遍历这个大的排序列表；你会得到一堆像这样的行：

5 1
5 2
12 1
12 2

然后你需要返回：

5 1 2
12 1 2

（这不会占用太多内存。）

通过把问题拆分成小块，希望能把内存使用量控制在合理的范围内——虽然这样会增加磁盘的读写次数，但在普通的电脑上，如果用一个大程序来处理，内存交换会让这个过程变得很糟糕。

Answer 3

假设每行大约有17个字符（这个数字我随便选的，为了计算方便），那么这个文件里大约有20亿条记录。如果你的电脑不是64位系统，或者物理内存不够的话，你会发现自己在用一个字典存储这些数据时，系统会频繁地使用虚拟内存，导致性能下降。而这只是为了把数据读入内存，大家都知道，读完这些数据后，你肯定还想用它们做点什么。

考虑到数据格式这么简单，我觉得用C语言来处理会比用Python更合适。解析这些数据应该不难，而且每个值占用的内存会少很多。最起码，仅仅是存储20亿个4字节的整数，就需要8GB的内存（当然，如果你能对目前列出的1和2的值范围做一些简化假设，比如它们能放在一个字节或短整型里，那么你可以使用更小的整数变量，这样对于这么大的数据集来说，会节省不少内存）。