Geek Answers Handbook

Java collection support: duplicate values, quick add, quick delete, fast minimum value?

Question: Does anyone know of a Java implementation (I have too little time / knowledge to develop my own now) collection with the following characteristics?

  • add quickly
  • quick random access removes
  • fast minimum value
  • duplicates

A compressed (simplified) version of the use case:

  • I have a class that tracks "time", name it TimeClass
  • Events begin with monotonically increasing time ( times are not unique ), but can end in any order
  • When events start, they report the start time TimeClass
  • When events end, they again report their start time TimeClass
  • TimeClassadds the start time of the event to the collection * when the event starts ( add quickly )
  • TimeClassremoves the start time of an event from this collection * when the event ends ( quick random access removes )
  • TimeClassable to report the lowest but not yet finished start time ( fast minimum value )

* think of the collection as: Collection<Time> implements Comparable<Time>

Since I'm not sure that will work during my system (a system in which they live TimeClass), I quickly compared the following scenarios using these collections: TreeMultiSet(the 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, , , .

- EDIT -

- , :

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;
}
+4

More articles:


All Articles