目标
我正试图为《我的世界》创建一个类似Skyblock的岛屿插件,我希望能够计算出一个";"岛级";每个玩家自己的三维岛屿区域。
情况
我有一个小散列图,它为块类型和它们可能处于的状态之间的可能组合的一些子集提供了一个十进制值
块的数据集很大:大约有16777216个块,我需要计算它们的每个"块"的总和;值";,如前面提到的映射所给出的。
在";伪Java">
double total = 0;
for (BlockData block : blocks) {
for (Entry<Key, Double> entry : map) {
Key key = entry.getKey();
// Type check
if (!key.getString().equals(block.getString()) continue;
// States check (Only ones explicitly defined by entry must match)
States blockStates = block.getStates();
States keyStates = key.getStates();
for (Entry<String, String> state : keyStates) {
if (!state.getValue().equals(blockStates.get(state.getKey()))
continue;
}
total += entry.getValue();
}
}
如何有效地实现液位计算
p.S.Delta编码在这种环境中是不可行的,因为由于API的限制和混淆,我无法收听块的设置。
在第一次运行时,我已经设法将其减少到1秒以下,甚至减少了6700万个块。我想我会在这里分享我的解决方案。
天真的方法
我的第一次尝试是简单地在多个线程上运行天真的方法(等于或是程序可用逻辑处理器数量的2倍(。这很慢,即使需要处理少量的块,也需要大约12秒左右的时间。
发现瓶颈
IntelliJ IDEA,我正在使用的IDE,预装了一个很棒的工具,叫做Java飞行记录器。特别是,调用树在发现和消除瓶颈方面非常有帮助。
调用树列出了用于任何特定方法调用的程序时间百分比。这是一个很好的、易于阅读的视图,有助于快速发现瓶颈。
对于我的特定情况,块数据对象是由外部API提供的,该API没有读取特定状态的方法。最初,我尝试解析块数据的字符串表示,但从性能的角度来看,这是一个糟糕的想法。我的解决方案是为块数据编写一个包装类QuickBlockData,它有一个自定义的equals
和hashCode
方法。
equals
方法访问外部API的内部块数据,而不是API公开呈现的块数据。它只比较了两个块数据对象中存在的状态键。
hashCode
方法在不破坏哈希代码契约的情况下无法使用任何状态,因此它只返回块数据的类型枚举,而不查看任何状态。
FastUtil
我决定使用FastUtil的Object2DoubleOpenHashMap作为我的值映射,因为它最能代表我想要的数据结构,并且与Java自己的哈希映射实现相比,它还提供了合理的性能改进。
我没有直接使用Object2DoubleOpenHashMap
,而是在ValueMap
类中进行了扩展,这允许我在getter中运行一些抢先检查,比如根据映射中包含的类型的HashSet检查输入的类型。
并行化和块
使用提供块数据的相同API,可以异步加载16x16列的块、块,然后单独解析它们。这非常有用,因为这意味着我可以在加载每个区块时对其进行处理。
API还提供了区块快照,这些快照是线程安全的对象,在创建时提供了关于区块的一些数据。至关重要的是,他们提供了一种方法来找到块中特定块列中最高的块,这是减少我需要处理的块的一种简单方法。
摘要
我用过:
- 一个块数据的包装类,带有一个性能良好的equals方法,可以满足我的要求(尽管它迫使我使用糟糕的哈希代码(
- 一个ValueMap类,它扩展了它.unimi.dsi.fastutil.Object2DoubleOpenHashMap,使我能够快速获得一些块数据的值,使用可自定义的默认值,并对块的类型进行抢先检查
- 由外部API提供的并行计算和分块,使用原子双来计算区域的总值