4

我有包含两列的简单文本文件，都是整数

1 5
1 12
2 5
2 341
2 12

等等..

我需要按第二个值对数据集进行分组，这样输出就可以了。

5 1 2
12 1 2
341 2

现在的问题是该文件非常大，大约 34 Gb，我尝试编写一个 python 脚本将它们分组到一个字典中，其值为整数数组，但仍然需要太长时间。（我想array('i')在append.

我现在正计划编写一个猪脚本，我计划在伪分布式 hadoop 机器（一个 Amazon 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 万的第二个 col 值在下一次运行时考虑 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:
4

5 回答 5

2

假设每行有大约 17 个字符（我随机选择了一个数字以使数学更容易），那么这个文件中有大约 20 亿条记录。除非您在 64 位系统上使用大量物理内存运行，否则您将试图将所有这些内容保存在单个 dict 中的内存中，从而使您的页面文件死气沉沉。这只是将其作为数据结构读入 - 假设在构建此结构之后，您计划实际使用它做一些事情。

使用如此简单的数据格式，我应该认为你最好用 C 而不是 Python 做一些事情。破解这些数据应该不难，而且每个值的开销也会少得多。至少，仅保存 20 亿个 4 字节整数将是 8 Gb（除非您可以对当前列为 1 和 2 的值的可能范围做出一些简化假设 - 如果它们适合一个字节或一个短字节，那么您可以使用较小的 int 变量，这对于这种大小的数据集来说是值得的）。

于 2010-08-04T08:47:49.557 回答
1

也许您可以对文件进行多次传递。

每次通过文件执行一系列键，例如，如果您选择的范围大小为 100

第一遍 - 计算出 0-99 的所有键
第二遍 - 计算出 100-199 的所有键
第三遍 - 计算出 200-299 的所有键
第四遍 - 计算出 300-399 的所有键
..等等。

对于您的样本，第一遍将输出

5 1 2
12 1 2

第四遍将输出

341 2

选择范围大小，以便您创建的 dict 适合您的 RAM

我不会费心使用多处理来尝试通过使用多个内核来加速它，除非你有一个非常快的硬盘驱动器，这应该是 IO 绑定的，你最终会破坏磁盘

于 2010-08-04T09:56:20.447 回答
1

我有一个类似的要求，你只需要一个猪语句来删除 5 (1,5) (2,5) 中的冗余。

a = LOAD 'edgelist' USING PigStorage('\t') AS (user:int,following:int);
b = GROUP a BY user;
x = FOREACH b GENERATE group.user, a.following;
store x INTO 'following-list';
于 2011-03-26T06:40:34.537 回答
1

如果我必须在我目前的硬件上解决这个问题，我可能会写一些小程序：

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

然后我会调用sort(1)每个小文件上提供的操作系统。（这可能需要一些内存。）

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

然后我会写一个程序来运行这个大的排序列表；你会有一堆像这样的行：

5 1
5 2
12 1
12 2

你需要返回：

5 1 2
12 1 2

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

通过将其分成更小的块，希望您可以将 RSS 降低到适合合理机器的东西——这将需要更多的磁盘 I/O，但是在除了令人惊讶的硬件之外的任何东西上，交换使用都会扼杀尝试一次处理这个问题的尝试大程序。

于 2010-08-04T09:00:18.673 回答
1

如果您使用的是 34 GB 文件，我假设硬盘驱动器在存储和访问时间方面都不是问题。如何顺序读取对，当您找到对 (x,y) 时，打开文件“x”，附加“y”并关闭文件“x”？最后，每个 Twitter 用户 ID 将拥有一个文件，并且每个文件都包含该文件所连接的所有用户。然后，如果您希望结果采用您指定的输出格式，则可以连接所有这些文件。

话虽如此，我确实认为：（a）对于如此大的数据集，精确的分辨率是不合适的，并且（b）可能有一些更好的方法来测量连接性，所以也许你想告诉我们你的最终目标。

事实上，你有一个非常大的图，并且已经设计了许多有效的技术来研究巨大图的形状和属性——这些技术中的大多数都是为了作为流式在线算法而构建的。

例如，一种称为三角形计数的技术与概率基数估计算法相结合，可以有效且快速地提供有关图中包含的团的信息。有关三角形计数方面的更好想法，以及它与图形的关系，请参见例如这篇（随机选择的）文章。

于 2010-08-04T14:26:28.783 回答