问题:有人知道具有以下特征的集合的Java实现(我现在没有时间/知识来开发我自己的时间太少)吗？
用例的精简版(简化版)为:
TimeClass TimeClass TimeClass 报告其开始时间
TimeClass在事件开始时将事件的开始时间添加到集合*(快速添加)TimeClass在事件结束时从该集合中删除事件的开始时间*(快速随机访问删除)TimeClass能够报告尚未完成的最短开始时间(快速最小值)*将集合视为:Collection<Time> implements Comparable<Time>
因为我不确定系统(即TimeClass所在的系统)的运行时行为如何，所以我使用这些集合迅速对以下方案进行了基准测试:TreeMultiSet(Guava)，MinMaxPriorityQueue(Guava)，ArrayList。
注意，根据使用的集合，最小值可以通过不同的方式实现(记住元素以递增顺序添加):TreeMultiSet.firstEntry().getElement()，MinMaxPriorityQueue.peekFirst()，ArrayList.get(0)。
加1,000,000:
TreeMultiSet: 00:00.897(m:s.ms) List: 00:00.068(m:s.ms) MinMaxPriorityQueue: 00:00.658(m:s.ms) 加1，删除1，重复1,000,000次:
TreeMultiSet: 00:00.673(m:s.ms) List: 00:00.416(m:s.ms) MinMaxPriorityQueue: 00:00.469(m:s.ms) 依次添加10,000，删除所有顺序:
TreeMultiSet: 00:00.068(m:s.ms) List: 00:00.031(m:s.ms) MinMaxPriorityQueue: 00:00.048(m:s.ms) 在顺序订单中添加10,000，在随机订单中删除所有订单:
TreeMultiSet: 00:00.046(m:s.ms) List: 00:00.352(m:s.ms) MinMaxPriorityQueue: 00:00.888(m:s.ms) 当前思想:
我倾向于使用TreeMultiSet，因为它具有最稳定的性能，并且降级得最多。 我会喜欢更多建议
谢谢
-编辑-
示例:在顺序订单中添加全部，在随机订单中删除全部的伪代码示例:
benchmark(){
int benchmarkSize = 1000000;
int benchmarkRepetitions = 100;
Duration totalDuration = Duration.fromMilli(0);
TimeClass timeClass = new TimeClassImplementation();
for (int i = 0; i < benchmarkRepetitions; i++)
totalDuration += benchmarkRun(timeClass,benchmarkSize);
System.out.println(totalDuration);
}
Duration benchmarkRun(TimeClass timeClass, int count){
List<Time> times = createMonotonicallyIncreasingTimes(count)
// monotonically increasing times to add from
List<Time> timesToAddFrom = copy(times)
// random times to remove from
List<Time> timesToRemoveFrom = shuffleUniformly(copy(times))
Time startTime = now()
// add all times
for(Time time: timesToAddFrom) {
Time min = timeClass.addTimeAndGetMinimumValue(time);
// don't use min value
}
// remove all times
for(Time time: timesToRemoveFrom) {
Time min = timeClass.removeTimeAndGetMinimumValue(time);
// don't use min value
}
Time finishTime = now()
return finishTime - startTime;
}
参考方案
最好的选择是树状图:
http://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html
O(log n)几乎适用于所有操作..您可以将键重新排序。
还有一个来自Google(guava)的MinMaxPriorityQueue
http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/MinMaxPriorityQueue.html
尽管remove是O(n)，但其他所有操作都是O(log n)
Java:正则表达式模式匹配器是否有大小限制？ - java我的模式类似于OR:“word1 | word2 | word3”我大约有800个字。可能有问题吗？ 参考方案 您仅受记忆和理智的限制。 :)
Java:线程池如何将线程映射到可运行对象 - java试图绕过Java并发问题，并且很难理解线程池，线程以及它们正在执行的可运行“任务”之间的关系。如果我创建一个有10个线程的线程池，那么我是否必须将相同的任务传递给池中的每个线程，或者池化的线程实际上只是与任务无关的“工人无人机”可用于执行任何任务？无论哪种方式，Executor / ExecutorService如何将正确的任务分配给正确的线程？ 参考方案 …
Java:我可以在Hashmaps中使用数组吗？ - java我可以在Hashmaps中使用数组吗？如果是这样，则声明这种哈希图的确切语法是什么？谢谢 参考方案 数组也是对象。甚至像int[]这样的原始数组。Map<String,String[]> map = new HashMap<String,String[]>();
JAVA:字节码和二进制有什么区别？ - javajava字节代码（已编译的语言，也称为目标代码）与机器代码（当前计算机的本机代码）之间有什么区别？我读过一些书，他们将字节码称为二进制指令，但我不知道为什么。 参考方案 字节码是独立于平台的，在Windows中运行的编译器编译的字节码仍将在linux / unix / mac中运行。机器代码是特定于平台的，如果在Windows x86中编译，则它将仅在Win…
java:继承 - java有哪些替代继承的方法？ java大神给出的解决方案 有效的Java：偏重于继承而不是继承。 （这实际上也来自“四人帮”）。他提出的理由是，如果扩展类未明确设计为继承，则继承会引起很多不正常的副作用。例如，对super.someMethod()的任何调用都可以引导您通过未知代码的意外路径。取而代之的是，持有对本来应该扩展的类的引用，然后委托给它。这是与Eric…