Optimisation advice (HashMap)

Question

I have a big list of coordinates (this form):

    if(x == 1055 && y == 63 && z == 1117)
        return blackwood;
    if(x == 1053 && y == 63 && z == 1117)
        return blackwood;
    if(x == 1049 && y == 64 && z == 1113)
        return blackwood;
    if(x == 1054 && y == 63 && z == 1112)
        return blackwood;
    if(x == 1058 && y == 63 && z == 1112)
        return blackwood;
    if(x == 1062 && y == 64 && z == 1117)
        return blackwood;
    if(x == 1050 && y == 64 && z == 1117)
        return blackwood;
    if(x == 1062 && y == 64 && z == 1118)
        return glass;
    if(x == 1050 && y == 64 && z == 1118)
        return andesite;

(Much longer than that)

But, when I call the method that execute these instructions, I have a lag (Not very long, but enough to have a freeze impression in-game).

So, my question is, how can I optimize this?

I was thinking about stocking these in a HashMap and use HashMap.get(key), but, does HashMap.get(key) iterate the list to find it out?

Answer 1

You could indeed use a Map with as key a custom class that uses as component value these 3 data : x, y and z.

With a fair implementation of the hashCode() method, it should be a constant time [O(1)] or very close to.

If you have to recreate the map as often as you need to request it, using a map could be helpless as from one side you could loose what you gain from another side.

So, create this custom class and override hashCode() and equals() by taking these 3 fields into consideration :

public class Coordinate {

    private int x;
    private int y;
    private int z;

    public Coordinate(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + x;
        result = prime * result + y;
        result = prime * result + z;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (!(obj instanceof Coordinate))
            return false;

        Coordinate other = (Coordinate) obj;
        if (x == other.x && y == other.y && z == other.z)
            return true;

        return false;
    }


}

Then you could initialize the map with expected key-values :

Map<Coordinate, MyValue> mapValuesByCoord = new HashMap<>();
mapValuesByCoord.put(new Coordinate(1055,63,1117), blackwood);
mapValuesByCoord.put(new Coordinate(1053,63,1117), blackwood);
mapValuesByCoord.put(new Coordinate(1062, 64, 1118), glass);

...

And use the map in this way :

MyValue value = mapValuesByCoord.get(new Coordinate(1055,63,1117));

Answer 2

There's an issue here with the common use of the word "map", as in a piece of paper showing a miniature representation of a piece of land, versus the programmer or mathematician's use of "map", in which values are associated with other values.

If pretty much every 3D coordinate has a corresponding return value, you would be better off having a direct lookup table. You could do this with a 3D array, i.e. an array-of-arrays-of-arrays:

 Rock[][][] rockMap =  ... // Google for guidance on initialising a 3D array

 ...
 rockMap[1054][63][1112] = blackwood;
 // etc.

Here "rockMap" is closer to the common use of the word "map". If you drew that 3D array, it would be your "world map".

Then your lookup is:

 return rockMap[x][y][z];

Alternatively you could use a 1D array and calculate an index from x, y, z:

 Rock[] rockMap = new Rock[SIZE_X * SIZE_Y * SIZE_Z];

 rockMap[1054 * SIZE_Y * SIZE_Z + 63 * SIZE_Z + 1112] = blackwood;

Lookup is similar to assignment:

 return rockMap[x * SIZE_Y * SIZE_Z + y * SIZE_Z + z];

If you don't have a rock for every coordinate, this approach would still work (you'd just have a null, or some other absence marker, in all the empty slots). But it would be a bit wasteful of space.

In this case it could be more efficient to create a Coordinate type, and construct a Map<Coordinate>.

 Map<Coordinate> rockMap = ...;
 rockMap.put(new Coordinate(x,y,z), blackwood);

 ...

 return rockMap.get(new Coordinate(x,y,z));

You should do your own tests to find out what type of Map works best in your program -- HashMap? TreeMap? Test them.

For these to work, Coordinate needs to implement certain methods -- check the Javadoc and make sure it does.

Answer 3

HashMap rarely iterates to get an element from its structure. Proper implementations iterate so rarely that people usually don't bother mentioning that part exists. Hence the O(1) complexity.

Imagine a table of your elements (every element has a key). Ideally HashMap will put every one of your elements in a unique row (so only 1 element per row). When given a key to get an element, HashMap will calculate a hash (int) of the key and find out in which row is its appropriate value located. Multiple elements in one row can occur because sometimes two different keys can have same hashes and then you iterate that row to find your element.

I think you could use a HashMap on your problem to speed it up a bit (where x, y and z should be unique keys).

Answer 4

I would create blackwood, glass and andesite object that have check(x, y, z) method.

Edit:

Maybe I should have also added that to make it more efficient you can implement blackwood.check(x, y, z) like this:

  public boolean check(int x, int y, int z){
      if ( y == 63 || y == 64){
          if (z == 1117 || z == 1113 || z == 1112){
              if (x == 1055 || x == 1053 || x == 1049 || x = 1054 || 
                  x == 1058 || x == 1062 || x == 1050){
                  return true;
              }
          }
      }
    return false;
}

What you will gain from this:

1) The logic for each type is encapsulated into separate classes and you wont have one huge method with long "ifs". And it will be easy to add a new type.

2) By moving the "y" check to top you will do a quick exit if its not 63 or 64. Same applies to z. Since "or" check in Java will not check the rest you will buy some performance by not checking all "x" values if x is 1055 for example.

3) Using Map or Set approach you have to create X, Y, Z wrapper key object on each call to your method. With the method being called very frequently you might have issues with garbage collector not being able to clean them up fast enough.