2

我有一组房间和通道，我可以将它们转换为矩形（x，y，宽度，高度）或点列表（x，y）。Room并且Passage都扩展了Pointable接口。getPoints() 方法为 Room 类实现为

public Set<Point> getPoints() {
    Set<Point> array = new HashSet<Point>();
    for (int i = 0; i < width; i++) {
        for (int j = 0; j < height; j++) {
            array.add(new Point(x + i, y + j));
        }
    }
    return array;
}


问题：
我必须确定Pointable一个给定的Point所属。没有房间相交。我最初使用 aHashMap<Point,Pointable>将每个Point与 a相关联Pointable，它能够在 O(n) 时间内快速访问答案。但是，现在需要HashMap在生成关卡时重新计算多次。

此时，使用 HashMap（考虑到生成和访问）是否仍然更有效，还是应该使用另一种方法，例如一组 2-D 区间树？

4

1 回答 1

1

此时，使用 HashMap（考虑到生成和访问）是否仍然更有效，还是应该使用其他方法，例如一组 2-D 区间树？

除了进行测量的人之外，没有人能说出来。这完全取决于您需要多久更新一次数据、多久更改一次以及多久查询一次。

并且还在大小上Room。在一个典型的场景中，只要有几个点，HashMap就有数千个点，更新点的开销占主导地位。

你不能对所有Points 使用一个数组吗？如果是这样，那么它肯定会比 . 快得多HashMap，尤其是对于更新（除非它变得非常大）。

这可能有用也可能没用。

实际上，不仅每个Room都有一些Points，而且每个Point可能都有一个Room（n：1）。它是如何实现的，这是一个不同的问题。

鉴于此，我们有一个标准问题：如果您双向链接，那么您必须保持两个链接同步。最简单的解决方案是使设置器（“adders”/“removers”）尽可能私有，并且只从方法中调用它们

void link(Room room, Point point) {
    Room oldRoom = point.getRoom();
    if (oldRoom!=null) oldRoom.removePoint(point);
    room.addPoint(point);
    point.setRoom(room);
}

您的 from Pointto链接Room是外部的，但这几乎不会改变任何东西（除了保持Point更小和可能更清洁以及为每次访问添加 HashMap 的微小开销）。

它通常也是最快的，因为通常查询比更新多得多。您的问题是更新成本会随着Room大小而增加。如果您不告诉我们一些数字，就无法进行估计。

对于太多的点和大小变化不大的房间，您可以将点坐标四舍五入为一些的倍数，n并保留一个数组来保存与网格相交的所有房间的集合。您可以像以前一样继续操作，但更新开销会降低几乎一个由房间面积 (*) 给出的因子，而搜索开销会更高，因为您必须从集合中选择真正匹配的房间（如果有的话）。

(*) 对于未与网格对齐的房间，相交矩形的数量明显更高。

于 2014-11-24T04:33:57.513 回答