12

任务是计算输入文件中的单词数。

输入文件是每行8个字符，有10M行，例如： 

aaaaaaaa  
bbbbbbbb  
aaaaaaaa  
abcabcab  
bbbbbbbb  
...

输出是： 

aaaaaaaa 2  
abcabcab 1  
bbbbbbbb 2  
...

如果我将所有单词加载到内存中，将需要 80MB 内存，但在 os 系统中只有 60MB，我可以将其用于此任务。那么我该如何解决这个问题呢？

我的算法是使用map<String,Integer>，但是 jvm 在线程“main”java.lang.OutOfMemoryError: Java heap space 中抛出异常。例如，我知道我可以通过设置 -Xmx1024m 来解决这个问题，但我想使用更少的内存来解决它。

4

12 回答 12

7

我相信最强大的解决方案是使用磁盘空间。

例如，您可以使用对大文件（使用磁盘空间）进行排序的算法，对另一个文件中的文件进行排序，然后计算相同单词的连续出现次数。

我相信这篇文章可以帮助到你。或者自己搜索一些关于外部排序的东西。

更新 1

或者正如@jordeu建议的那样，您可以使用 Java 嵌入式数据库库：如 H2、JavaDB 或类似库。

更新 2

我想到了另一种可能的解决方案，使用Prefix Tree。但是我还是更喜欢第一个，因为我不是他们的专家。

于 2012-04-12T09:45:09.483 回答
5

一次读一行，然后有一个例如HashMap<String,Integer> 你把你的单词作为键和计数作为整数的地方。

如果存在键，则增加计数。否则将键添加到地图中，计数为 1。

无需将整个文件保存在内存中。

于 2012-04-12T09:37:50.550 回答
3

我猜你的意思是不同单词的数量是吗？

因此，显而易见的方法是将每个不同的单词（有关的独特信息）存储为映射中的键，其中值是关联的计数器。根据预期有多少不同的单词，存储所有这些单词甚至可能适合您的记忆，但在所有单词都不同的最坏情况下，情况并非如此。

为了减少内存需求，您可以计算单词的校验和并将其存储，而不是单词本身。存储例如 4 字节校验和而不是 8 字符字（需要至少 9 个字节来存储）需要 40M 而不是 90M。另外，每个单词也需要一个计数器。根据特定单词的预期出现次数，您可以使用 2 个字节（最多出现 65535 次），这需要最多 60M 的内存来存储 10M 个不同的单词。

更新

当然，校验和可以通过多种不同的方式来计算，它可以是无损的，也可以是无损的。这也很大程度上取决于单词中使用的字符集。例如，如果只使用小写的标准 ASCII 字符（如上例所示），我们在每个位置有 26 个不同的字符。因此，每个字符都可以无损编码为 5 位。因此 8 个字符适合 5 个字节，这比限制多一点，但可能足够密集，具体取决于具体情况。

于 2012-04-12T09:36:56.977 回答
1

使用H2 数据库引擎，如果需要，它可以在磁盘或内存上工作。它有一个非常好的性能。

于 2012-04-12T09:57:40.337 回答
1

我不擅长解释理论答案，但我们开始......

我对你的问题做了一个假设，因为它并不完全清楚。

  • 用于存储所有不同单词的内存为 80MB（整个文件更大）。
  • 单词可能包含非 ascii 字符（因此我们只是将数据视为原始字节）。

读取文件两次就足够了，每次存储约 40MB 的不同单词。

//  Loop over the file and for each word:
//
//      Compute a hash of the word. 
//      Convert the hash to a number by some means (skip if possible).
//      If the number is odd then skip to the next word. 
//      Use conventional means to store the distinct word. 
//
//  Do something with all the distinct words.

even然后使用代替第二次重复上述操作odd。

然后你把任务分成了2个，可以分别做。第一组中的任何单词都不会出现在第二组中。

散列是必要的，因为这些词（理论上）可能都以相同的字母结尾。

该解决方案可以扩展为使用不同的内存限制。我们可以使用 . 将单词分成 X 组，而不是只说奇数/偶数number MOD X。

于 2012-04-12T09:59:11.707 回答
0

我会为每个单词创建一个 SHA-1，然后将这些数字存储在一个集合中。然后，当然，在读取数字时，检查 Set 是否存在 [（并非完全必要，因为 Set 根据定义是唯一的，因此您也可以“添加”其 SHA-1 数字）]

于 2012-04-12T09:40:32.963 回答
0

根据单词的构建类型，您可以为此系统选择：

如果它可能包含大写和小写字母的任何字符，您将有 (26*2)^8 组合，即 281474976710656。这个数字可以适合长数据类型。

因此计算字符串的校验和，如下所示：

public static long checksum(String str)
{
    String tokes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    long checksum = 0;

    for (int i = 0; i < str.length(); ++i)
    {
        int c = tokens.indexOf(str.charAt(i));

        checksum *= tokens.length();
        checksum += c;
    }

    return checksum;
}

这将使每个字占用的内存减少超过 8 个字节。一个字符串是一个数组char，每个字符在 Java 2 字节中。因此，8 个字符 = 16 个字节。但是 string 类包含的数据不仅仅是 char 数组，它还包含一些用于大小和偏移量的整数，即每个 int 4 个字节。不要忘记指向字符串和字符数组的内存指针。因此，原始估计让我认为这将减少每个单词 28 个字节。

因此，每个字 8 个字节，而您有 10 000 000 个字，则为 76 MB。这是你的第一个错误估计，因为你忘记了我注意到的所有事情。所以这意味着即使这种方法也行不通。

于 2012-04-12T09:46:24.273 回答
0

如果您可以先对文件进行排序（例如，在 Unix 上使用内存高效的“排序”实用程序），那么这很容易。您只需读取已排序的项目，边走边计算相邻的重复项，然后立即将总数写入新文件。

如果您需要使用 Java 进行排序，这篇文章可能会有所帮助：

http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

于 2012-04-12T10:00:44.843 回答
0

您可以将每个 8 字节的字转换为 along并使用TLongIntHashMap，这比Map<String, Integer>or更有效Map<Long, Integer>

如果您只需要可以使用的不同单词TLongHashSet

于 2012-04-12T10:03:09.567 回答
0

您可以通过多次读取文件来使用常量内存。

基本思路：

将文件视为 n 个分区 p_1...p_n，调整大小以便您可以将每个分区加载到 ram 中。

  1. 将 p_i 加载到 Map 结构中，扫描整个文件并仅跟踪 p_i 元素的计数（参见 Heiko Rupp 的答案）
  2. 如果我们在 j 小于 i 的分区 p_j 中遇到相同的值，则删除元素
  3. Map 中元素的输出结果计数
  4. 清除地图，对所有 p_1...p_n 重复
于 2012-04-12T10:18:13.360 回答
0

与任何优化一样，需要权衡取舍。在您的情况下，您可以使用更少的内存来执行相同的任务，但这是以增加运行时间为代价的。

您的稀缺资源是内存，因此您无法将单词存储在 RAM 中。

您可以使用哈希而不是其他帖子提到的单词，但是如果您的文件变大，这不是解决方案，因为在某些时候您会再次遇到同样的问题。

是的，您可以使用外部 Web 服务器来处理文件并为您的客户端应用程序完成工作，但是阅读您的问题，您似乎想在一个（您的应用程序）中完成所有事情。

所以我的建议是遍历文件，并且对于每个单词：

  • 如果第一次找到该单词，则将该字符串与整数值 1 一起写入结果文件。
  • 如果之前处理过这个词（它将出现在结果文件中），则增加记录值。

无论输入文件的行数或单词的长度如何，此解决方案都可以很好地扩展*。

您可以优化在输出文件中进行写入的方式，以便更快地进行搜索，但上述基本版本就足够了。

编辑：
*它可以很好地扩展，直到您用完磁盘空间 XD。所以前提条件是有一个至少有 2N 字节可用空间的磁盘，其中 N 是输入文件的大小（以字节为单位）。

于 2012-04-12T11:05:01.207 回答
0

可能的解决方案：

  1. 使用文件排序，然后只计算每个值的后续出现。
  2. 将文件加载到数据库中并使用如下计数语句：select value, count(*) from table group by value
于 2012-04-12T12:01:06.643 回答