支持 : duplicate values, 快速添加、快速删除、快速最小值的 Java 集合？

Question

问题:有人知 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;
}

Answer 1

最好的选择是 TreeMap :

http://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html

O(log n) 几乎适用于所有操作。您可以让您的 key 恢复排序。

Google (guava) 还有一个 MinMaxPriorityQueue

http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/MinMaxPriorityQueue.html

尽管移除是 O(n)，所有其他操作都是 O(log n)