java - 我想要有效的数据结构来存储项目及其计数并搜索其中的最小值？

Question

我想要有效的数据结构来存储项目及其计数并搜索其中的最小值？

我有许多项目，以及每个项目的计数，我想要一个数据结构来存储项目及其计数。在我的脚本中，每次我都会搜索一个项目并更新它的计数，我也想找到具有最小计数的项目，有时我想要一些项目的计数。你能告诉我在低空间和低成本搜索操作中使用哪种数据结构？

标签： javalist

Answer 1

您有相互冲突的请求。

您希望通过键（名称、项目编号、ID 等）快速查找项目 您希望通过现有数量（计数）快速查找项目

由于可能的最快查找可能类似于具有 O(1) 查找的地图，因此问题是“您将使用哪个键？” 计数是冲突的，所以你会得到比理想的 O(1) 少一点；并且，名称或 ID 将意味着您必须查找大量物品才能获得少量物品。

这意味着您需要两个数据结构。

一个是名称/id 到项目的典型映射。一个是数量索引到具有该数量的项目列表。

这意味着您必须同时更新这两种数据结构，以使您的数据在应用程序中保持一致。

然后你想有效地提取项目列表。好吧，我们不知道您的列表是否稳定，或者可能是随机选择的，所以我会逐项检查列表。如果您知道您有稳定、长期（重用）的列表，那么另一种方法可能会更好。

我希望你能读懂这篇评论的字里行间。不考虑用例就没有“高效”的数据结构。虽然您已经表明您知道这一点；它还有另一个层次。当您组合多个相互冲突的用例时，有时您会牺牲一个的效率来换取另一个的效率。例如，为了快速查找，您现在需要通过重建另一个不同的数据结构来减少插入/更新时间。

当然，您也可能要求（将来）您的数据结构超出单台机器的容量。如果是这样，您可能会发现您的所有解决方案都不是那么好，因为它们都假设一个内存地址空间。然后你可能不得不转向分布式数据模型，比如 Apache Spark/Hadoop。在那个空间中，构建索引可能不太有意义，因为过滤结果是一项非常便宜的操作，而构建分布式索引可能变得更加昂贵。因此，您可能只是转向“阅读所有条目，丢弃我不想要的条目”，这可能会为您提供良好的服务，具体取决于数据、所需的延迟和实际操作中的使用。

这里的关键是进行基准测试，并知道什么是“足够好”。如果您陷入“最佳”或“最高效”的困境，您将花费更多的钱来快速做出快速的事情。而是设置一些基准，读作“必须在 X 毫秒内从一组（某个数字）返回”，然后构建您的解决方案以击败该规则。