java - 整数集。在增加新条目的情况下可能会提高性能

Question

如果您是一位技术娴熟的低延迟 Java 开发人员(我不是)并且被告知要实现一组 int(无论是否为原始类型)，您是否有可能在保证的前提下获得额外的性能提升前提是每个新条目都高于先前存储在集合中的任何其他值？

在最好/最坏的情况下，add、contains 和 remove 操作的 yield 有多大？

一方面，这种限制会带来更好的性能似乎很自然。另一方面，非递减条目是一种非常常见的情况(例如在生成唯一 ID 时)，如果 yield 值得为之奋斗，那么或多或少已知的实现就会已经开发出来。

Answer 1

当你检查这个 question ，您会发现 add 和 contains 已经是 O(1)。所以那里没有太多需要改进的地方。

而且我认为这两个将是唯一一次可以从此约束中受益的:

• “添加”变得更容易，因为您可以简单地记住最后添加的值；所以当一个新值进来时只需要检查一次
• 类似地，当询问“包含”时；当给定值不在集合中
时，您有第一次预检查会立即告诉您

但仅此而已。

除此之外:当您的约束确实是要添加的每个"new"条目都大于最后一个条目时 - 那么您不需要Set 首先。因为您的约束 保证所有项目都是唯一的。所以从这个意义上说，您也可以研究列表......

关于问题在 O(1) 和 O(1.5) 之间的可能增量之间提出的评论；我的回复:

O(1) 和 O(n) 之间的区别是理论上的，您可以使用笔和纸来回答。 O(1.0) 和 O(1.005) 之间的区别......我将从实验和基准开始。

含义:这些“真实”因素取决于与底层实现“接近”的各种元素。您将首先研究您当前使用的 Set 是如何为您的平台实现的；以及 您的 平台上的 JVM 如何进行即时编译。从那里开始，您可以得出关于可以通过考虑此约束来改进的事情的结论。

最后；关于约束降低现有的实现。我想这也可能发生；如上所述:这些细节确实取决于具体实现。除此之外:您命名了三种不同的操作；实际结果可能大不相同；取决于操作类型。

如果我必须解决这个问题；我首先会使用“测试数据”(随机数、递增数；及其变体)创建相当大的文件。然后我会使用一个真正的 分析器(或者至少是复杂的 benchmarking )并开始测量。