How to implement an effecient matrix data structure in java?

Question

Is there a builtin data structure in java that lets me do this:

Matrix matrix = new Matrix(); // No fixed size, and O(1) to initate

matrix.set(x,y,32); // adds 32 to arbitrary positions x and y in O(1)
matrix.isempty(x,y); // returns true or false wether x,y has been set to a value
matrix.clear(); // clears all elements in O(1)

You cannot use a two dimensional array, because you need to initate it to a fixed size, which takes O(x*y). You cannot use a list of lists, because you cannot add objects to arbitrary positions.

I would use a HashMap, or TObjectIntHashMap unless you have a more specific requirement. BTW There is libraries like Colt which support sparse arrays/matricies. — Peter Lawrey
– Peter Lawrey, Commented Sep 24, 2014 at 19:52
The second-person imperative implies this is homework. Some people mind this. I however do not =D — ne1410s
– ne1410s, Commented Sep 24, 2014 at 19:53
I see nowhere where you set the size. Is there any concept of "reading off the end"? — Oliver Charlesworth
– Oliver Charlesworth, Commented Sep 24, 2014 at 19:53

Roland Krüger · Accepted Answer · 2014-09-24 19:57:22Z

2

Have a look at Google Guava's collection class Table. Might be an option unless this class is too heavyweight for you.

answered Sep 24, 2014 at 19:57

Roland Krüger

9045 silver badges15 bronze badges

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

3 Comments

Dan O Over a year ago

OP says they're looking for "a builtin data structure" or else I would have recommended the same thing.

Dici Over a year ago

@DanO : Maybe built-in means "I don't want to implement it myself". I think this is a quite good answer.

Roland Krüger Over a year ago

Indeed. I missed that. Hopefully, it helps anyway :)

Dici · Accepted Answer · 2014-09-24 19:52:36Z

0

Considering just these operations, you could implement it thanks to a HashMap<java.awt.Point,SomeType>, but I don't think it already exists this way.

answered Sep 24, 2014 at 19:52

Dici

26k7 gold badges45 silver badges86 bronze badges

2 Comments

Dici Over a year ago

@ScottHunter : Nothing in the doc enables me to be positive about that but knowing the general implementation details of HashMap, I think that clear only consists in allocating a new array and updating some fields.

Dici Over a year ago

I could be wrong, I just saw an implementation of HashMap that keeps the same capacity after clear, so it has to set all the values of the table to null, which is a O(n).

Collectives™ on Stack Overflow

How to implement an effecient matrix data structure in java?

2 Answers 2

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related