CODEWITHSUNDEEP
javaarraysoptimizationmultidimensional-arraydata-structures
Ashish Saini
Ashish Saini

Reputation: 21

Is there an alternate way to handle large 2D arrays in Java, given a memory constraint?

I'm trying to implement a 2D coordinate system using a 2D int array in Java. I have a memory constraint of 256MB, and the 2D grid is large enough for the memory requirement to go beyond that. Is there another data structure that can do this, while consuming lesser memory?

(Edit: The intent is to track movement within the grid by setting flags for the coordinates that have been visited at least once.)

Upvotes: 2

Views: 311

Answers (1)

Max Vollmer
Max Vollmer

Reputation: 8598

You don't need an array for that at all. You are wasting memory for every point right now, while you actually only need to store coordinates of visited points. Use a set of points to store only the coordinates that have been visited, and check if the set contains coordinates to see if a point was visited before or not.

So instead of:

int[][] array = new int[width][height];

and

array[x][y] = true;

and

if (array[x][y] == true) {...}

you have something like:

class Point
{
    public int x;
    public int y;
    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
    @Override
    public boolean equals(Object o)
    {
        return o instanceof Point && this.x == ((Point)o).x && this.y == ((Point)o).y;
    }
    @Override
    public int hashCode()
    {
        return Integer.valueOf(x).hashCode() ^ Integer.valueOf(y).hashCode();
    }
}

Set<Point> set = new HashSet<Point>();

and

if (set.contains(new Point(x, y))) {...}

and

set.add(new Point(x,y));

Alternatively you could use a map:

HashMap<Integer, HashSet<Integer>> map = new HashMap<>();

and

if (map.contains(x) && map.get(x).contains(y)) {...}

and

if (!map.contains(x)) {
    map.add(x, new HashSet<Integer>());
}
map.get(x).add(y);

Further optimization options

If you know that your application will visit all points or at least more than half of all points, you can switch the logic when it reached 50% of points visited. Basically (pseudocode):

if (pointsVisited < numAllPoints / 2)
    values in map or set are visited
else
    values in map or set are **not** visited (all others are)

You of course need some method that actually does a swap when the threshold is reached, removing all points from your map or set and adding all that weren't in there before. Afterwards instead of adding points, you remove points when they get visited.

That way at most half of all points are stored at any given time.

Upvotes: 1

Related Questions