1

我遇到了以下问题 - 我收到了一个文本文件，其中包含大量允许重复的单词。我需要编写一个算法，以降序输出出现频率最多的 1000 个单词。这是一个例子

**input.txt**

aa aa bb cc bb bb bb dd dd

**output.txt** (note - frequencies can be repeated)

bb 4
aa 2
dd 2
cc 1

  1. 这是我解决这个问题的方法。首先读取所有单词并HashMap以单词为键将它们存储起来。这样做的最终结果是我拥有了所有带有频率的单词。

  2. 现在我遍历HashMap并为每个键值对创建一个对象 {word, frequency} 然后我将它插入到 a 中SortedSet（我为此编写了一个比较器）。

  3. 现在我只是迭代SortedSet1000 次以获得结果。

我想知道解决这个问题的更好方法。

谢谢

4

2 回答 2

4

有没有更好的方法来解决这个问题？

有两种方法来看待这个......取决于你所说的“更好”的意思。

如果“更好”意味着“使用更少的时间和/或内存”，那么有可能解决这个问题的方法，具体取决于问题的大小和您可用的资源。例如：

  • 如果文本文件（或多个文件）足够大以证明这一点，您可以考虑将问题分区以在多处理器上运行。但这不是直截了当的……如果问题太小，分区的开销实际上可能会使解决方案变慢！

  • 链接的问答描述了一种可能加快您的步骤 2 和 3 的方法。问题是，如果您对代码进行基准测试，您可能会发现步骤 1 是花费大部分 CPU 时间的地方。（并且输入文件越大，这种效果可能越明显......）

如果“更好”意味着“更快地解决问题”，那么答案是“可能不会”。假设您有一个您描述的算法的良好实现版本，那么为（可能）更快的更复杂算法所付出的努力可能不值得。

计算机时间比软件开发时间便宜！

我的建议是执行以下操作：

  1. 对您现有的程序进行基准测试。它在真实的输入文件上运行得足够快吗？如果“是”，则调用程序完成。

  2. 分析在真实输入文件上运行的现有程序。分析是否显示任何明显的性能热点？有代码调优的机会吗？如果“是”，请尝试它们，然后重复基准测试步骤，看看它们是否真的有帮助。

  3. 查看 GC 日志。是否有迹象表明您的代码具有过多的 GC 开销？如果“是”，请查看一些简单的 GC 调整（如增加堆大小）是否会产生影响。

如果您在完成上述所有操作后仍未获得可接受的性能，那么现在是开始寻找替代算法的时候了。

于 2013-09-29T01:55:24.067 回答
2

让我们关注第 2 步和第 3 步。假设有 N 个单词，每个单词都有给定的频率，并且您必须找到前 K（在您的情况下为 1000）。

您的方法在 O(N log N) 中运行。正如斯蒂芬所说，这已经足够好了:)无论如何，这里有一些可能的改进。

第一种方法：正如链接中所建议的，您可以使用最小堆（您可以使用优先级队列）来维护前 1000 个。实现起来并不难。一旦你有了带有频率的地图，就开始对其进行迭代。如果最小堆的大小小于 K，则继续推动该对（单词，频率）。如果堆的大小为 K，则比较当前条目从映射到堆根的频率（堆中的最低频率）。如果新频率较低，请忽略它。如果它更高，则从堆中弹出最低的并推送当前的。这种方法将在 O(N log K) 中运行。

第二种方法： 选择算法在 O(N) 的列表（未排序）中找到第 K 个最大（或最小）的数字。您可以找到第 K_th 最大的，然后遍历地图以得到小于或等于 K 的所有内容。如果超过 K，则必须是第 K_th 最大的数字重复了很多次的情况。如果你跟踪它，你可以删除这个数字所需的计数来获得前 K。这需要 O(N)。

第三种方法：您可以进行随机快速排序的变体来找到前 K。我认为，预期的运行时间是 O(N)。

于 2013-09-29T02:47:03.047 回答