java - 映射大量多头的最快方法

Question

我正在编写一个将数字(长)转换为一小组结果对象的 Java 应用程序。这个映射过程对应用的性能非常关键，因为它经常被需要。

public static Object computeResult(long input) {
    Object result;
    // ... calculate
    return result;
}

大约有 150,000,000 个不同的键对象和大约 3,000 个不同的值。 从输入数字(长)到输出(不可变对象(immutable对象))的转换可以通过我的算法以每秒 4,000,000 次转换的速度计算。 (使用 4 个线程)

我想缓存 150M 不同的可能输入的映射以使翻译更快，但我发现创建这样的缓存有些困难:

public class Cache {
    private static long[] sortedInputs; // 150M length
    private static Object[] results; // 150M length

    public static Object lookupCachedResult(long input) {
        int index = Arrays.binarySearch(sortedInputs, input);
        return results[index];
    }
}

我尝试创建两个长度为 150M 的数组。第一个数组包含所有可能的输入 long，并按数字排序。第二个数组在与第一个数组的输入对应的索引处保存对 3000 个不同的、预先计算的结果对象之一的引用。

为了获得缓存的结果，我对第一个数组中的输入数字进行了二进制搜索。然后在第二个数组中的相同索引处查找缓存的结果。

遗憾的是，这种缓存方法并不比计算结果快。甚至不到一半，每秒只有大约 150 万次查找。 (同样使用4个线程)

谁能想到在这种情况下缓存结果的更快方法？

我怀疑是否有一个数据库引擎能够每秒回答超过 4,000,000 个查询，假设是一个普通的工作站。

Answer 1

散列是这里的方法，但我会避免使用 HashMap，因为它只适用于对象，即每次插入 long 时都必须构建一个 Long，这会减慢它的速度。由于 JIT，这个性能问题可能并不重要，但我建议至少尝试以下操作并针对 HashMap 变体衡量性能:

将您的多头数据保存在长度为 n > 3000 的长数组中，并通过非常简单的散列函数(因此非常高效)手动进行散列，例如 索引 = 键 % n。由于您事先知道 3000 个可能的值，因此您可以根据经验找到一个数组长度 n，这样这个简单的哈希函数就不会导致冲突。因此，您可以绕过重新散列等，并拥有真正的 O(1) 性能。

其次，我建议您查看 Java 数字库，例如

• https://github.com/mikiobraun/jblas
• https://github.com/fommil/matrix-toolkits-java

两者都由本地 Lapack 和 BLAS 实现支持，这些实现通常由非常聪明的人高度优化。也许您可以根据矩阵/vector 代数来制定您的算法，以便它一次(或逐 block )计算整个长数组。