3

在我的应用程序中，我需要检查 2D 坐标 (x,y) 的集合以查看给定坐标是否在集合中，它需要尽可能快，并且只能从一个线程访问。（用于碰撞检查）

有人可以推动我朝着正确的方向前进吗？

4

5 回答 5

5

我能想到的绝对最快的方法是维护这些点的二维矩阵：

//just once
int[][] occurrences = new int[X_MAX][Y_MAX];
for (Point p : points ) {
    occurrences[p.x][p.y]++;
}

//sometime later
if ( occurrences[x][y] != 0 ) {
    //contains Point(x, y)
}

如果您不在乎有多少，那么只需一个boolean矩阵即可。显然，如果矩阵只创建一次，并且可能会随着点添加到集合中而更新，这只会很快。

简而言之，基本的 Collections 并不完美（尽管 aHashSet会接近）。

编辑

Set<Point>如果您还没有找到可以为您执行此操作的库，则可以轻松地将其改编为 a 。像这样的东西：

public class PointSet implements Set<Point> {
    private final boolean[][] data; 
    public PointSet(int xSize, int ySize) {
        data = new boolean[xSize][ySize];
    }

    @Override
    public boolean add(Point e) {
         boolean hadIt = data[e.x][e.y];
         data[e.x][e.y] = true;
         return hadIt;
    }

    @Override
    public boolean contains(Object o) {
        Point p = (Point) o;
        return data[p.x][p.y];
    }

    //...other methods of Set<Point>...
}
于 2010-06-07T17:17:06.310 回答
2

我会使用一些Trove 集合数据结构。

如果您的点存储为一对int或一对，float您可以将它们打包成一个long：x 坐标为 32 位，y 坐标为 32 位。然后，您可以使用为处理原始数据TLongHashSet而HashSet优化的 a（与普通 java 集合相比，它会更快并且消耗更少的内存）。

如果您有int坐标，它将类似于

static private long computeKey(int h1, int h2)
{           
    return ((long)h1) << 32 | h2;
}

计算密钥然后使用它

TLongHashSet set = new TLongHashSet()
set.add(long v);
set.addAll(long[] v);
set.containsAll(..);

如果你有float值，你可以做同样的事情，但你必须在long.

于 2010-06-07T17:24:29.943 回答
1

哈希集。它的 O(1) 平均值。如果你想要真正的 O(1)，你可以为你的对象创建一个包装器，它引用了一个集合。这样一来，您就不能将其与您拥有的收藏进行比较。

于 2010-06-07T17:25:24.637 回答
0

与搜索相比，您需要多久更新一次集合？您应该基于此选择适当的数据结构。

Point2D 实现了可比性，对吧？那么你最好的选择可能是 TreeSet，它们非常快，而且我相信它们依赖于 B+ 树，你可能知道它在实际的数据库和文件系统中使用。

如果您认为您将对结构进行大量更新，请查看 SkipList。它保证 O(log(operations)) **注意这是针对您所做的所有操作，没有关于单个操作的运行时间的保证）

于 2010-06-07T17:24:39.033 回答
-1

您可以尝试某种排序集，例如树集，因为您可以对其进行二进制搜索。

于 2010-06-07T17:23:51.613 回答