在Java中快速比较大数据集中的值和小数据集中的值

Question

目标

我正在尝试为Minecraft创建一个类似Skyblock的岛屿插件，我希望能够为每个玩家自己的三维岛屿区域计算一个“岛屿级别”

情况

我有一个小的hash map，它为块类型和它们可能处于的状态之间的可能组合的某些子集提供了一个十进制值

块的数据集很大：大约有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.增量编码在这种环境中不可行，因为由于API限制和混淆，我无法侦听块的setter

Answer 1

在第一次跑步时，我已经成功地将速度降低到1秒以下，即使是6700万次。我想我应该在这里分享我的解决方案

天真的方法

我的第一次尝试是简单地在多个线程上运行naive方法（等于或是程序可用逻辑处理器数量的2倍）。这是缓慢的，大约需要12秒左右，即使有少量的块处理

发现瓶颈

我使用的IDE IntelliJ IDEA预装了一个很棒的工具，名为Java Flight Recorder。特别是，调用树在发现和消除瓶颈方面非常有帮助

调用树列出了花费在任何特定方法调用上的程序时间百分比。这是一个很好的、易于阅读的视图，有助于快速发现瓶颈

对于我的特定情况，块数据对象是由外部API提供的，该API没有读取特定状态的方法。起初，我尝试解析块数据的字符串表示形式，但从性能角度来看，这是一个糟糕的想法。我的解决方案是为块数据编写一个包装类QuickBlockData，它有一个定制的equals和hashCode方法

equals方法访问外部API的内部块数据，而不是API公开提供的块数据。它仅比较两个块数据对象中存在的状态键

hashCode方法在不破坏哈希代码约定的情况下无法使用任何状态，因此它只返回块数据的类型enum，而不是查看任何状态

FastUtil

我决定使用FastUtil的Object2DoubleOpenHashMap作为我的值映射，因为它最接近地代表了我想要的数据结构，并且比Java自己的哈希映射实现提供了合理的性能改进

我没有直接使用Object2DoubleOpenHashMap，而是在ValueMap类中进行了扩展，这允许我在getter中运行一些抢占式检查，比如根据映射中包含的HashSet类型检查输入的类型

并行化和块

使用提供块数据的相同API，可以异步加载16x16列的块、块，然后分别解析它们。这非常有用，因为这意味着我可以在加载每个块时对其进行处理

API还提供了区块快照，这是线程安全的对象，在创建区块时提供了有关区块的一些数据。关键的是，他们提供了一种在块中的特定块列中查找最高块的方法，这是减少我需要处理的块的简单方法

摘要

我用过：

• 块数据的包装类，带有performant equals方法，实现了我想要的功能（尽管它迫使我使用糟糕的哈希代码）
• ValueMap类，它扩展了它。尤尼米。dsi。fastutil。物体。Object2DoubleOpenHashMap，允许我快速获取某些块数据的值，使用可自定义的默认值，并对块的类型进行抢占式检查
• 由外部API提供的并行计算和分块，使用原子双精度来计算区域的总值