更快地处理这些数据的算法？ （排序一个 4.2M 大小的堆栈）
Algorithm to process this data faster? (sorting a 4.2M size stack)
情况：在程序生成我的游戏世界结束时，我留下了 2048^2（约 420 万）大小的瓷砖堆栈。然后我需要计算他们需要去我的处理程序的堆栈列表中的哪个位置。这是我的方法：
public static final void addTile(Tile t){
for(int i = 0; i < sections.length; i++)
for(int j = 0; j < sections[i].length; j++)
if(sections[i][j].contains(t.x, t.y)){ //<-- determine which list according to tile's pos
world.get(i).get(j).get(TILE_LIST).push(t);
return;
}
}
Rectangle[][]对应'world'arraylist中的每个点。如您所见，这是一个 O(n^2) 循环，需要执行 420 万次。 即使 4 个线程 运行 并发 处理所有图块大约需要 20 秒。
这不是完全不可行的处理时间，但我认为必须有更好的算法。有什么建议吗？
您当然需要一个好的数据结构来快速搜索包含给定点的矩形。
R-tree 旨在非常快速地处理此类查询。
如 MBo 所述，r 树是用于任意 point/poly 搜索的良好空间索引，但是，由于我们正在寻找矩形（轴对齐的多边形），您可能最好使用四叉树（或 3 维的八叉树）。
https://gamedev.stackexchange.com/questions/63536/how-do-shapes-rectangles-work-in-quad-trees
情况：在程序生成我的游戏世界结束时，我留下了 2048^2（约 420 万）大小的瓷砖堆栈。然后我需要计算他们需要去我的处理程序的堆栈列表中的哪个位置。这是我的方法：
public static final void addTile(Tile t){
for(int i = 0; i < sections.length; i++)
for(int j = 0; j < sections[i].length; j++)
if(sections[i][j].contains(t.x, t.y)){ //<-- determine which list according to tile's pos
world.get(i).get(j).get(TILE_LIST).push(t);
return;
}
}
Rectangle[][]对应'world'arraylist中的每个点。如您所见，这是一个 O(n^2) 循环，需要执行 420 万次。 即使 4 个线程 运行 并发 处理所有图块大约需要 20 秒。
这不是完全不可行的处理时间，但我认为必须有更好的算法。有什么建议吗？
您当然需要一个好的数据结构来快速搜索包含给定点的矩形。
R-tree 旨在非常快速地处理此类查询。
如 MBo 所述，r 树是用于任意 point/poly 搜索的良好空间索引，但是，由于我们正在寻找矩形（轴对齐的多边形），您可能最好使用四叉树（或 3 维的八叉树）。
https://gamedev.stackexchange.com/questions/63536/how-do-shapes-rectangles-work-in-quad-trees