1

给定一个包含单词（一些重复）的 1GB（非常大）文件，我们需要读取文件并输出每个单词重复的次数。请让我知道我的解决方案是否高性能。

（为简单起见，假设我们已经捕获了 an 中的单词arraylist<string>）

我认为大 O(n) 是“n”。我对么？？

public static void main(String[] args) {

            ArrayList al = new ArrayList();
            al.add("math1");
            al.add("raj1");
            al.add("raj2");
            al.add("math");
            al.add("rj2");

            al.add("math");
            al.add("rj3");
            al.add("math2");
            al.add("rj1");
            al.add("is");
            Map<String,Integer> map= new HashMap<String,Integer>();

            for (int i=0;i<al.size();i++)
            {
                String s= (String)al.get(i);

                    map.put(s,null);

            }
            for (int i=0;i<al.size();i++)
            {
                String s= (String)al.get(i);
                if(map.get(s)==null)
                    map.put(s,1);
                else
                {
                    int count =(int)map.get(s);
                        count=count+1;
                        map.put(s,count);
                }


            }

            System.out.println("");
        }
4

5 回答 5

2

我认为你可以做得比使用 HashMap 更好。

关于 hashmap 解决方案的思考

您的 anwser 是可以接受的，但请考虑这一点：为简单起见，假设您一次将一个字节的文件读取到 StringBuffer 中，直到遇到空格。此时您将调用 toString() 将 StringBuffer 转换为字符串。然后检查字符串是否在 HashMap 中，或者它被存储或者计数器被递增。

英语 dic。包含在 linux 中的有 400k 字，大小约为 5MB。因此，在您阅读的“1GB”文本中，我们可以猜测您只会在 HashMap 中存储大约 5MB。文件的其余部分将在您在地图中完成查找后转换为需要进行垃圾收集的字符串。我可能是错的，但我相信在构造字符串期间字节将被再次迭代，因为需要在内部复制字节数组并再次计算哈希码。因此，该解决方案可能会浪费大量 CPU 周期并迫使 GC 经常发生。

在你的面试中指出这样的事情是可以的，即使这是你能想到的唯一解决方案。

我可以考虑使用自定义的RadixTree或 Trie 类结构

请记住 RadixT/Trie 的插入方法是如何工作的。这是获取一个字符/字节流（通常是一个字符串）并将每个元素与树中的当前位置进行比较。如果前缀存在，它只会在锁定步骤中沿着树和字节流前进。当它遇到新的后缀时，它开始将节点添加到树中。一旦到达流的末尾，它就会将该节点标记为 EOW。现在考虑我们可以在读取更大的流时做同样的事情，只要我们碰到一个空格，就将当前位置重置为树的根。

如果我们编写自己的基数树（或者可能是 Trie），谁的节点有词尾计数器（而不是标记），并且插入方法直接从文件中读取。我们可以一次将一个字节/字符插入到树中，直到我们读取一个空格。此时插入方法将增加字尾计数器（如果它是现有字）并将树中的当前位置重置回头部并再次开始插入字节/字符。基数树的工作方式是折叠单词的重复前缀。例如：

The following file:

math1 raj1 raj2 math rj2 math rj3 

would be converted to:

(root)-math->1->(eow=1)
     |    |-(eow=2)
     |    
      raj->1->(eow=1)
      | |->2->(eow=1)
      | |->3->(eow=1)
      j2->(eow=1)

像这样插入到树中的时间是 O(k)，其中 k 是最长单词的长度。但是由于我们在读取每个字节时正在插入/比较。我们并没有像我们必须读取文件那样效率低下。

另外，请注意，我们会将字节读入一个临时字节，该字节将是一个堆栈变量，因此我们需要从堆中分配内存的唯一时间是遇到一个新单词（实际上是一个新后缀）。因此，垃圾收集几乎不会经常发生。并且基数树使用的总内存将比 HashMap 小很多。

于 2011-07-25T07:30:54.130 回答
1

理论上，由于 HashMap 访问一般是 O(1)，我猜你的算法是 O(n)，但实际上有几个低效率。理想情况下，您只需遍历文件的内容一次，在读入单词时处理（即计数）单词。无需将整个文件内容存储在内存中（您的 ArrayList）。您循环内容三次 - 一次读取它们，第二次和第三次在上面代码的两个循环中。特别是，上面代码中的第一个循环是完全没有必要的。最后，您对 HashMap 的使用将比需要的要慢，因为构造时的默认大小非常小，并且它必须在内部多次增长，每次都强制重建哈希表。最好从适合您期望的尺寸开始。

于 2011-07-24T18:45:40.917 回答
1

您是否考虑过使用 mapreduce 解决方案？如果数据集变得更大，那么最好将其拆分并并行计算单词

于 2011-12-01T01:39:34.240 回答
0

您应该只用单词阅读文件一次。

无需事先放置空值 - 您可以在主循环中进行。

在这两种情况下，复杂度确实是 O(n)，但是你想让常数尽可能小。（O（n）= 1000 * O（n），对:)）

于 2011-07-24T18:58:45.073 回答
0

要回答您的问题，首先，您需要了解 HashMap 的工作原理。它由桶组成，每个桶都是一个链表。如果由于散列另一对需要占用同一个桶，它将被添加到链表的末尾。因此，如果 map 具有高负载因子，则搜索和插入将不再是 O(1)，算法将变得低效。此外，如果地图加载因子超过预定义的加载因子（默认为 0.75），则整个地图将被重新散列。

这是 JavaDoc http://download.oracle.com/javase/6/docs/api/java/util/HashMap.html的摘录：

在设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。

所以我建议你预定义一个地图容量，猜测每个单词都是唯一的：

Map<String,Integer> map= new HashMap<String,Integer>(al.size());

否则，您的解决方案效率不够高，尽管它仍然具有 O(3n) 的线性近似值，因为由于重新散列的摊销，元素的插入将花费 3n 而不是 n。

于 2011-07-24T19:25:36.870 回答