What data structure to use

Question

I'm looking for a data structure that has the following properties.

Stores a list of tuple<Double,Integer,Integer>. Order is only on double. Two tuples with the same double value are consider the same.
Supports duplicates.
Needs to be able to traverse in ascending order. If there are duplicates, the one added later should have higher order.
Find/Insert fast
Remove fast, note that remove always follows this pattern

Method contains remove:

for(int i=list.size()-1;i>=0;i--){// assume list is in ascending order
    if(list[j:i] can be merged){
        remove list[j:i-1];
        update list[i]'s two integers;
        i = j-1;
    }
}

I currently use ArrayList and keep it sorted. Finding is fast with binary search. However insertion and deletion will involve lots of copy in memory, e.g. insertion in the front of the list shifts all the elements.

btw be careful when you write "same double values are considered the same" The concept of equality for floating-point numbers is a very broad topic. You may very well need to write a custom comparator taking an error margin into account. — SyntaxT3rr0r
– SyntaxT3rr0r, Commented Jul 28, 2011 at 14:23
you search for the minimum j<i such that list[j:i] can be merged — Wei Shi
– Wei Shi, Commented Jul 28, 2011 at 14:41
So j is in an outer loop (around the one shown) like this: for(int j = 0; j < list.size(); j++)? Also, by list[j:i] are you using python-like syntax to indicate a range? When can they be merged? The overarching problem might lead me to suggest an alternative structure. — 101100
– 101100, Commented Jul 28, 2011 at 19:07

101100 · Accepted Answer · 2011-07-28 14:25:09Z

1

One solution would be to have a sorted map to lists of tuples:

SortedMap<Double,List<Tuple<Integer,Integer>>>

The declaration line is bit ugly, but it will work. I've used maps to lists many times before. The nice thing about it is that you can then delete items from the lists and as long as your lists are each short, you have a smaller number of moves. To iterate over the entire structure, you'd need to create your own iterator, or adapt your original code.

answered Jul 28, 2011 at 14:25

101100

2,71624 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Joshua Kaplan · Accepted Answer · 2011-07-28 19:56:27Z

If you decide to write your own Double comparator there are a few things to be aware of.

The first is that floating point equality is a very tricky area. By default Java does not ensure consisten floating point math when your code is running in different virtual machines although this can be done by using the strictfp keyword. This inconsistency in floating point arithmetic can cause issues in applications that are unaware of this and run on multiple virtual machines communicating with one another, such as servers and client communication.

The second tricky bit is that Comparators operate on Objects which means you will be working with Doubles not doubles. The following four operations cause Double to be unboxed into double: <, <=, >, and >=. The following two do not cause unboxing: == and !=. These two operators perform Object memory pointer comparisons. Bottom line, manually unbox the Doubles into doubles before performing comparisons; it will greatly reduce bugs.

Collectives™ on Stack Overflow

What data structure to use

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related