问题:有人知 Prop 有以下特征的集合的 Java 实现(我现在没有时间/知识来开发自己的)吗?
- 快速添加
- 快速随机访问删除
- 快速最小值
- 重复
用例的精简(过度简化)版本是:
- 我有一个跟踪“时间”的类,称它为
TimeClass
- 事件以单调递增的时间开始(时间不唯一),但可以按任何顺序结束
- 当 Activity 开始时,他们将开始时间报告给
TimeClass
- 当 Activity 结束时,他们再次将开始时间报告给
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;
}
最佳答案
最好的选择是 TreeMap :
http://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html
O(log n) 几乎适用于所有操作。您可以让您的 key 恢复排序。
Google (guava) 还有一个 MinMaxPriorityQueue
尽管移除是 O(n),所有其他操作都是 O(log n)
关于支持 : duplicate values, 快速添加、快速删除、快速最小值的 Java 集合?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25077543/