Optimal Integer Map

[yzzzzz]

Hi,

I want to store an int->V map (V is a class).
This map will contain about 10 to 15 values.
The integer key will vary from 1 to about 160.
I will be using up to 50 such maps at a time.
I am trying to optimize speed and memory usage (though speed is more
important).

1. I could use an ArrayList, but it would be a waste of space (about 150
of the values would be null). This is what I am doing at the moment

2. I could use a Map<Integer,V>. What kind of map? Hashmap? I didn't
think it was worth hashing Integers. Plus I don't like the idea of
boxing/unboxing all the time.

3. Is there a better way of doing this? A map whose keys are ints?

Thanks.

 

[Greg Stark]

The fastest would be a V[] array, i.e. V[] vMap = new V[161]; It is
true that 90% of the space is "wasted" but it is not that much space. I
don't know how much space an array element takes up but I'm going to
guess it is 4 bytes. Thus, your waste is about 50*145*4 = 29,000 bytes.
That's nothing. It's 2005. In another few years that's how much space
one Java char will use

If that space is really bothering you, then the Hashmap you mentioned
is probably your best bet. Just create it with the "right" amount of
space in the begining.

If you're really into this and want to spend a lot of research effort
into optimizing this, you might google on "perfect hash function" or
"perfect hashing".

 

[yzzzzz]

The fastest would be a V[] array, i.e. V[] vMap = new V[161]; It is
true that 90% of the space is "wasted" but it is not that much space. I
don't know how much space an array element takes up but I'm going to
guess it is 4 bytes. Thus, your waste is about 50*145*4 = 29,000 bytes.

Yep, that's partly what I thought. However I don't think using an
ArrayList<V> will be much slower than a V[], as ArrayList is based on
arrays but provides a much better interface and is an Object (which has
many advantages). I think the general guideline is "only use an array
for low-level stuff (files, sockets, streams), otherwise use ArrayList
when you can".

So I'll probably stick with the ArrayList for now.

 

[Ryan Stewart]

The fastest would be a V[] array, i.e. V[] vMap = new V[161]; It is
true that 90% of the space is "wasted" but it is not that much space. I
don't know how much space an array element takes up but I'm going to
guess it is 4 bytes. Thus, your waste is about 50*145*4 = 29,000 bytes.

Yep, that's partly what I thought. However I don't think using an ArrayList<V>
will be much slower than a V[], as ArrayList is based on arrays but provides a
much better interface and is an Object (which has many advantages). I think
the general guideline is "only use an array for low-level stuff (files,
sockets, streams), otherwise use ArrayList when you can".

So I'll probably stick with the ArrayList for now.

My general guidance is, "Use an array if you have a fixed size. Otherwise use an
ArrayList." If you're really worried about wasted space, write your own Map
implementation that uses ints for keys.

 

[Andrew McDonagh]

Hi,

I want to store an int->V map (V is a class).
This map will contain about 10 to 15 values.
The integer key will vary from 1 to about 160.
I will be using up to 50 such maps at a time.
I am trying to optimize speed and memory usage (though speed is more
important).

1. I could use an ArrayList, but it would be a waste of space (about 150
of the values would be null). This is what I am doing at the moment

2. I could use a Map<Integer,V>. What kind of map? Hashmap? I didn't
think it was worth hashing Integers. Plus I don't like the idea of
boxing/unboxing all the time.

3. Is there a better way of doing this? A map whose keys are ints?

Thanks.

The others excellent suggests are all worth considering, and I can't
really add anything to them, aside from a question...

Why do you care about the speed and memory performance?

In other words, have you profiled your app to see that this area is a
bottleneck or are you guessing it will be?

We all make correct guesses, but sometimes we we don't and optimisation
is 'generally' the area where we get it wrong.

 

[yzzzzz]

The others excellent suggests are all worth considering, and I can't
really add anything to them, aside from a question...

Why do you care about the speed and memory performance?

This is in a struts webapp running in tomcat. One of the pages has to
extract some basic information from a database, analyze it then display
it in an extremely complex way (using tables). The page takes a few
seconds to load.

In other words, have you profiled your app to see that this area is a
bottleneck or are you guessing it will be?

It's just that when I click the link I have to wait 1 second

We all make correct guesses, but sometimes we we don't and optimisation
is 'generally' the area where we get it wrong.

Sorry I don't quite get what you mean...

 

[Ryan Stewart]

Why do you care about the speed and memory performance?

This is in a struts webapp running in tomcat. One of the pages has to extract
some basic information from a database, analyze it then display it in an
extremely complex way (using tables). The page takes a few seconds to load. [...]

We all make correct guesses, but sometimes we we don't and optimisation is
'generally' the area where we get it wrong.

Sorry I don't quite get what you mean...

He means don't assume that your int->V map problem is what is slowing your app
down. I recommend using logging to discover which steps are taking up all your
time. Configure your logging framework to show milliseconds, and it's very easy
to see where your time is gong.

 

[Andrew McDonagh]

Why do you care about the speed and memory performance?

This is in a struts webapp running in tomcat. One of the pages has to extract
some basic information from a database, analyze it then display it in an
extremely complex way (using tables). The page takes a few seconds to load.
[...]

We all make correct guesses, but sometimes we we don't and optimisation is
'generally' the area where we get it wrong.

Sorry I don't quite get what you mean...

He means don't assume that your int->V map problem is what is slowing your app
down. I recommend using logging to discover which steps are taking up all your
time. Configure your logging framework to show milliseconds, and it's very easy
to see where your time is gong.

Yes this is exactly what I meant. Interestingly enough, I find it
usually better (as like everything in life there are exceptions) to
'getItWorking' first, then if I have proof an area is too slow I
'getItWorkingFaster'.



And the usual state of play is that the areas I 'think' are slow and
will be called n000s times, are not nearly as bad as some other area,
which is the real performance problem.