（到目前为止，这在本质上是相当假设的，所以我没有太多细节可以提供。）
我有一个随机（英文）单词的平面文件，每行一个。我需要编写一个高效的程序来计算每个单词的出现次数。该文件很大（可能大约 1GB），但我有足够的 RAM 来存放所有内容。它们存储在永久媒体上，因此读取速度很慢，所以我只需要线性读取一次。
我的两个不经意间的想法是使用带有单词的哈希 => 否。发生次数，或尝试与否。在结束节点发生的次数。我有足够的 RAM 用于哈希数组，但我认为 trie 的查找速度会一样快或更快。
什么方法最好？
问问题
1113 次
9 回答
2
我会使用一个 Dictionary 对象，其中键是转换为小写的单词，值是计数。如果字典不包含该单词，则将其值添加 1。如果它确实包含该单词，则增加该值。
于 2009-11-02T20:19:50.507 回答
2
鉴于阅读速度较慢，它可能不会产生任何明显的差异。无论如何，总时间将完全由读取数据的时间支配，因此这就是您应该优化的工作。对于内存中的算法（实际上主要是数据结构），只需使用您认为最舒适的语言中最方便的任何内容。
于 2009-11-02T20:25:52.337 回答
2
哈希表（如果做得对，并且您说您有很多 RAM）O(1) 来计算特定单词，而 trie 将是 O(n)，其中 n 是单词的长度。
有了足够大的散列空间，您将从散列表中获得比从特里树更好的性能。
于 2009-11-02T20:25:53.117 回答
2
我认为尝试使用计数作为叶子可能会更快。
任何体面的哈希表实现都需要完全阅读单词，使用哈希函数对其进行处理，最后在表中查找。
可以实现一个 trie，以便在您阅读单词时进行搜索。这样，一旦确定了唯一的单词前缀，您就经常会发现自己跳过了字符，而不是对单词进行完整的查找。
例如，如果你读过字符：“torto”，trie 会知道唯一可能以这种方式开头的单词是 tortoise。
如果您可以比散列算法更快地对单词执行此内联搜索，那么您应该能够更快。
但是，这完全是矫枉过正。既然你说这纯粹是假设性的，我就继续说下去，我想你想要一个假设性的答案。选择在合理时间内执行任务的最可维护的解决方案。微优化通常在工时上浪费的时间比在 CPU 上节省的时间要多。
于 2009-11-02T20:26:24.887 回答
1
我认为 trie 对于您的用例来说太过分了。单词的哈希 => # 的出现正是我会使用的。即使使用像 Perl 这样的慢速解释语言，您也可以在几分钟内以这种方式处理一个 1GB 的文件。（我以前做过。）
于 2009-11-02T20:22:57.100 回答
1
我有足够的 RAM 用于哈希数组，但我认为 trie 的查找速度会一样快或更快。
这段代码将运行多少次？如果你只做一次，我会说优化你的时间而不是你的 CPU 时间，并且只做最快的实现（在合理范围内）。如果您有一个实现键值接口的标准库函数，请使用它。
如果您要多次执行此操作，请获取数据文件的一个子集（或多个子集），并对您的选项进行基准测试。在不了解您的数据集的情况下，推荐一个而不是另一个是可疑的。
于 2009-11-02T20:23:41.530 回答
0
一个简单的python脚本：
import collections
f = file('words.txt')
counts = collections.defaultdict(int)
for line in f:
counts[line.strip()] +=1
print "\n".join("%s: %d" % (word, count) for (word, count) in counts.iteritems())
于 2009-11-02T20:21:08.797 回答
0
使用 Python！
将这些元素逐行添加到集合数据类型中，然后询问它是否在哈希表中。在您知道它在集合中之后，然后添加一个字典值 2，因为您之前已经将它添加到集合中一次。
这将花费一些内存和计算，而不是每次都询问字典，而是会更好地处理唯一值的单词，在调用结束时，只需将字典中没有的所有单词转储到集合之外值为 1。（相对于集合相交两个集合）
于 2009-11-02T20:27:21.180 回答
0
在很大程度上，这取决于您希望在捕获数据后如何处理这些数据。请参阅为什么在 Trie（前缀树）上使用哈希表？
于 2009-11-02T20:29:43.437 回答