当Dictionary类可以用于大型文件中的字符串计数时，为什么要尝试DataStructure

本文关键字：为什么 DataStructure 字符串 Dictionary 用于 文件 大型 | 更新日期: 2023-09-27 18:20:11

假设我需要计算一个非常大的文件中的单词（单词由"分隔）

我会按照

  1. 不在内存中加载整个文件，逐行读取流
  2. 对于每一行，拆分单词并将不同的单词添加到"dictionary"（我的意思是，使用dictionary Class在.NET中）及其计数

现在要检索最频繁的单词，请对字典进行排序并获取它。

但大多数解决方案都是支持Trie Data结构的，请澄清原因（此外，如果不澄清哈希表相对于字典的原因，那就太好了）。

谢谢。

当Dictionary类可以用于大型文件中的字符串计数时，为什么要尝试DataStructure

我忍不住提到，这不仅是一个map reduce问题，而且是map reduced问题。

除此之外，使用trie实现的原因是为了提高查找每个单词以增加其计数的效率（或者添加一个trie中还不存在的单词）。在基本trie中，每个单词的查找时间为O(n)，其中n是单词中的字符数。在整个文档中，如果没有并行处理，您将只查看O(n)时间以进行查找，其中n是文档中的字符数。然后，检索所有单词将是（可能）深度优先搜索，这样您就可以提取所需的信息。深度优先搜索的最坏情况性能将是相同的O(n)，但由于通用前缀，预期情况会更好。

如果使用不同的结构，例如标准System.Collections.Generic.Dictionary<TKey, TValue>，它涉及哈希查找，则成本与哈希查找和实现以及哈希冲突的普遍性有关。然而，即便如此，也可能不是成本的主要部分。假设arguendo散列查找是恒定时间且琐碎的。因为相等的哈希码不能保证字符串相等，正如MSDN文档反复警告的那样，仍然需要比较字符串的相等性，这几乎可以肯定地实现为O(n)，其中n是字符数（为了简单起见）。因此，根据trie和一些基于哈希查找的字典的实现，基于哈希查找字典可能并不比trie好，也可能更糟。

对我的分析的一个有效批评可能是，trie中每个节点的查找可能不是恒定的时间；它将取决于用于确定后续节点的边的集合。然而，如果我们以后不关心对键进行排序，那么基于哈希查找的字典在这里可能会很好地工作。当输入是一个字符时，不太可能发生哈希冲突，并且与完整字符串相比，等式比较所涉及的内容要少得多。插入性能可能也是合理的，同样取决于实现。

但是，如果您知道要通过字数来确定前n个单词，那么除了在trie中跟踪它们之外，您可能还需要在执行时跟踪前n个单词的字数。这样，您就不需要在填充trie之后重新计算顶部的n。

您可以使用类似于流读取器的File.ReadLines。

var mostFrequent = File.ReadLines("Path")
    .SelectMany(l => l.Split()) // splits also by tabs
    .GroupBy(word => word)
    .OrderByDescending(g => g.Count())
    .First(); // or Take(10) if you want the top 10
Console.Write("Word:{0} Count:{1}", mostFrequent.Key, mostFrequent.Count());
相关文章：