在给定内存限制的情况下，是否有另一种方法来处理Java中的大型2D数组

Question

我正在尝试使用Java中的2Dint数组来实现2D坐标系。我有256MB的内存限制，2D网格足够大，内存需求可以超过这个限制。有没有其他数据结构可以做到这一点，同时消耗更少的内存？

(编辑：目的是通过为至少访问过一次的坐标设置标志来跟踪网格内的移动。(

Answer 1

您根本不需要一个数组。您现在正在为每个点浪费内存，而实际上您只需要存储访问点的坐标。使用一组点仅存储已访问过的坐标，并检查该集是否包含坐标，以查看某个点以前是否访问过。

所以不是：

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

和

array[x][y] = true;

和

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

你有类似的东西：

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>();

和

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

和

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

或者您可以使用地图：

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

和

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

和

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

进一步的优化选项

如果您知道您的应用程序将访问所有点或至少超过所有点的一半，则可以在访问点达到50%时切换逻辑。基本(伪代码(：

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

当然，你需要一些方法，当达到阈值时，真正进行交换，从地图或集合中删除所有点，并添加所有以前不在其中的点。之后，不再添加点，而是在访问点时删除点。

这样，在任何给定的时间，最多存储一半的点。