0

我对大数据这个话题完全陌生。我必须分析一个近 10 GB 的带有数字的文本文档。这些是近 10 亿个数字，所以对我来说，像这个文件这样分析并不是那么容易。文档的结构像一个列表，一行一个数字。我的主要问题是，您认为分析这些庞大数据集的最佳机会是什么？我的目的是找出列表包含多少个不同的数字，我想保存这个结果。

输入是这样的，有近十亿行：

123801
435345
123
7
43958112
4569
45
509858172
...

输出应该是这样的（仅作为示例）：

1 2
2 4
3 1
4 109
5 56
...
高达近十亿

首先，我使用 linux/unix 'sort' 和 'unique' 以及特定参数进行了尝试，但对于这样的情况，这不是一个解决方案。

我的下一个想法是尝试在数据集上实现快速排序或合并排序。是否可以在 Java 或其他语言中进行这样的分析/加载？我读到 ArrayList 在 Java 列表中开销最小。如果可能的话，我想我可以尝试实现一个 for 循环，该循环将递增到数字“n”，并且如果 nextElement != thisElement 退出 for 循环。我想我可以通过增加一个变量来保存计数，如果条件正确则设置为零。您如何看待这个想法，当然还有这个问题？

我也想过为这个数据集建立一个数据库。这是更好的机会吗？如果是，哪个 DBMS 是最好的？

我对其他任何事情都非常开放，我将非常感谢您的意见、想法和解决方案！

4

4 回答 4

1

如果您遵循以下模式，则可以并行完成：

1）将文件拆分为可管理的块（您需要使用“split -l”在行边界处拆分，因此选择适当数量的行而不是绝对大小（以 MB 为单位））

2）分析每个块，“awk”（gawk）脚本可以有效地做到这一点，因为文件大小不是太大，内存需求是合理的；将这些中间结果写入每个块的单独文件。

3）合并所有分析的结果——但这仍然需要太多的内存；
也许如果您的脚本仅合并所有块中选定的数字范围，即数字 0..1000000、200000..3000000 等；这些结果对于每个范围都是确定的。对前几个块的初步分析可能会让您了解值的分布以及在哪里设置这些边界。

4) 最后将这些结果合并到一个文件中

我建议在这里使用标准的 shell 实用程序，因为它们非常适合文本处理并且可以这样做，但大多数语言应该能够应付。

例如，根据最大数字的大小，您可能需要在 Java 中使用 BigInteger；另一方面，“awk”只是将它们视为文本，因此这不是问题。

于 2013-10-10T11:58:05.193 回答
0

文件中的 10GB 数字 = ~ 5-50 GB 内存

问题是您无法加载所有数据然后“唯一”它们，导致 JVM 甚至您的计算机无法处理那么多 GB 的 RAM。

因为不可能只加载一些输入，计算子结果并添加到结果中（例如添加所有数字），所以最好的方法是使用 UNIQUE 修饰符将这些数字发送到数据库。许多聪明的人在数据库上工作了很多时间，以使它们尽可能快，因此它比您的任何“本地”解决方案都要快得多。

数据库本身...每个世界范围的数据库都是有用的，每个数据库在某些方面是好是坏。例如 facebook 和 youtube 在 MySQL 上运行 - 所以即使是 MySQL 也用于大型系统。

于 2013-10-10T11:52:05.130 回答
0

我相信他们希望你在某个时候达到概率计数。参见示例：大数据计数：如何仅使用 1.5KB 的内存计算十亿不同的对象

如果您想要精确计数，请对数据进行排序（如果您有非常大的集合，请使用 TeraSort），然后只需计算完全相同的值彼此相邻出现的次数。

或者使用 MapReduce。将每个数字映射到 (number, 1)，然后对 reducer 中的第二列求和。

如果您想手动执行，sort也可以执行合并。因此，您可以使用split对数据进行分区，sort每个分区，然后sort -m是分区并uniq -c计算结果。如果你想在 Java 中做到这一点：永远不要使用带有原始类型的 Java 集合。这浪费了大量的内存。使用 GNU Trove 类型，例如TIntIntHashMap.

# Split into chunks of 100k lines:
split -l100000 input temp-
# Sort each chunk
for nam in temp-*; do sort $nam > sorted-$nam; done
# Merge-sort and count:
sort -m sorted-* | uniq -c
于 2013-10-10T16:10:00.760 回答
0

要使用的核心数据结构是 Map(Integer,Integer) 来存储每个数字出现的计数器。

如果你的机器有几十GB RAM，你可以尝试使用普通的java.util.hashMap。

否则，您可以使用任何数据库 - 每个 DBMS 都可以管理此类表。为简单起见，请使用嵌入式。

但是，为了获得最佳速度，您可以编写专门的程序，它类似于外部排序，但用对 [number, counter] 替换一系列相同的数字。它可以按如下方式工作：

  • 读取输入文件并在 TreeMap 中收集对，直到内存可用。

  • 将 TreeMap 作为排序的对序列保存在二进制文件中

  • 清除 TreeMap 并继续直到输入文件结束

  • 合并保存的文件

于 2013-10-10T11:52:46.590 回答