时间戳

首页 > 解决方案 > Java：如何以极高的性能进行基于位置 (x,y) 的索引？

java - Java：如何以极高的性能进行基于位置 (x,y) 的索引？

问题描述

我有一个游戏板，它是一个最多 64 x 64 块的方形二维空间。每个图块都可以，但并不总是包含一个游戏块。作为生成可能的未来状态以进行分析的 AI 算法的一部分，我需要能够：

显而易见的解决方案是使用一个简单的二维数组来保存对对象的引用。虽然这在访问/删除部件时易于使用且性能良好，但板克隆/生成结果证明是主要的性能瓶颈。通过生成所有这些板，我基本上达到了内存写入带宽上限。

我需要克隆板并且不能重复使用板，因为板的更改应该只发生在我正在使用的板上。所以我需要找到一种方法来生成足够多的对象，以允许位置索引，同时确保它足够快。从理论上讲，一种不制造新板，但使用和清洁过时的板的解决方案可能会起作用，但它必须需要一种清洁成本低廉的容器，同时提供非常便宜的 O(1) 访问、插入和移除。

我尝试过的事情：

还有其他我可以尝试的解决方案吗？

标签： javaarraysperformancedata-structureshashmap

解决方案

等级制度

无论您选择哪种解决方案，克隆所有 64*64 = 4096 个元素实在是太多了。由于您的更改很小，您可以使用分层不可变表示，例如 64 乘以 64 数组，并且始终只克隆更改的部分：

Piece[][] getModifiedClone(Piece[][] original, int x, int y, Piece newPiece) {
    Piece[][] result = original.clone(); // clones 64 pointers only
    result[x] = result[x].clone(); // also clones 64 pointers only
    result[x][y] = newPiece;
    return result;
}

这将开销从 64*64 减少到 64+64。您不必在此处遵循您的行/列结构。以牺牲一些索引位操作为代价，您可以使用不同的结构。您不必将内部层次结构组织为 2D；您可以使用 3 或 4 级，并将开销减少到 16+16+16 或 8+8+8+8。

微优化

只有一种类型的对象，但它具有三个重要的变量。这三个都是整数，总是 <= 2000。我可以将整个东西打包在一个 int 中，但是来回转换会破坏访问时间。

你可能是对的，但是像

int pack(int a, int b, int c) {
    return (a << 22) + (b << 11) + (c << 0);
}

int unpackA(int packed) {
    return (packed >> 22) & 0x7FF;
}

int unpackB(int packed) {
    return (packed >> 11) & 0x7FF;
}

int unpackC(int packed) {
    return (packed >> 0) & 0x7FF;
}

由于使用对象，听起来比间接要快得多。在使用少量内存并适合 L1 缓存的微基准测试中，它可能会更快。由于大量内存和缓存未命中，打包是恕我直言的明显赢家。

使用撤消

可能是它仍然太慢，然后你可能会重新考虑你在做什么。也许只有一块板并在完成后恢复更改可能比任何克隆都快。也许你需要不止一个板，也许每个线程一个......

概括

我想，我会选择 4D 层次结构和包装的组合，即

int getPackedPieceAt(int[][][][] board, int x, int y) {
   return board[x >> 3][x & 7][y >> 3][y & 7];
}

处理 4D 数组非常难看，但你只需要上面的方法和这个

int[][][][] getModifiedClone(int[][][][] original, int x, int y, int newPiece) {
    ... just like above

}

假设您的游戏状态不仅仅是棋盘，您应该将数组封装在一个State对象中，然后可以隐藏所有丑陋。

推荐阅读