java - 考虑到内存限制，是否有另一种方法可以在 Java 中处理大型二维数组？

Question

我正在尝试使用 Java 中的二维 int 数组实现二维坐标系。我有 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));

或者您可以使用 map :

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)

您当然需要某种方法在达到阈值时实际进行交换，从您的 map 或集合中删除所有点并添加之前不存在的所有点。之后不是添加点，而是在访问点时删除点。

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