Java集合支持:重复值，快速添加，快速删除，快速最小值

问题:有人知道具有以下特征的集合的Java实现(我现在时间/知识太少，无法开发自己的集合)吗?

快速添加
快速随机访问删除
快速最小值
复制

用例的浓缩(过度简化)版本是:

我有一个类跟踪"时间"，称之为TimeClass
事件以单调递增的时间开始(时间不是唯一的)，但可以以任何顺序结束
当事件开始时，它们向TimeClass报告它们的开始时间
当事件结束时，它们再次向TimeClass报告它们的开始时间
TimeClass在事件开始时将事件的开始时间添加到集合* (fast add)
TimeClass在事件结束时从集合中删除事件的开始时间* (fast random-access remove)
TimeClass能够报告最低的未完成启动时间(快速最小值)

* 的集合为:Collection<Time> implements Comparable<Time>

因为我不确定我的系统(TimeClass所在的系统)的运行时行为是什么，所以我使用这些集合快速对以下场景进行了基准测试:TreeMultiSet (Guava)、MinMaxPriorityQueue (Guava)、ArrayList。

注意，根据所使用的集合的不同，最小值有不同的实现方式(记住元素是按递增顺序添加的):TreeMultiSet.firstEntry().getElement(), MinMaxPriorityQueue.peekFirst(), ArrayList.get(0)。

添加1000000:

TreeMultiSet: 00:00.897 (m: s.m)
List: 00:00.068 (m: s.m)
MinMaxPriorityQueue: 00:00.658 (m: s.m)

添加1，删除1，重复1,000,000次:

TreeMultiSet: 00:00.673 (m: s.m)
List: 00:00.416 (m: s.m)
MinMaxPriorityQueue: 00:00.469 (m: s.m)

按顺序添加10,000，按顺序删除所有:

TreeMultiSet: 00:00.068 (m: s.m)
List: 00:00.031 (m: s.m)
MinMaxPriorityQueue: 00:00.048 (m: s.m)

按顺序添加10,000，按随机顺序删除所有:

TreeMultiSet: 00:00.046 (m: s.m)
List: 00:00.352 (m: s.m)
MinMaxPriorityQueue: 00:00.888 (m: s.m)

当前思想:

我倾向于使用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)几乎适用于所有的操作。你可以把你的钥匙重新排序。

还有一个MinMaxPriorityQueue来自Google (guava)

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

remove是O(n)，其他操作都是O(log n)

相关内容

最新更新

热门标签：