大量长整型映射的最快方法

Question

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

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

大约有1.5亿个不同的键对象和约3,000个不同的值。

从输入数字（长整型）到输出（不可变对象）的转换可以使用我的算法计算，每秒可以进行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个不同、预先计算的结果对象之一的引用。

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

遗憾的是，这种缓存方法并没有比计算结果更快。即使使用了4个线程，每秒只能进行约1.5M次查找。

有人能想到一种在这种情况下更快的缓存结果的方法吗？

我怀疑，在平均工作站上，没有数据库引擎能够每秒处理超过4,000,000次查询。

- andre.r

---

你尝试过使用 TreeMap<Long, Object> 吗？而且你的缓存几乎是只读的，对吧？ - Jason Hu

我认为使用HashMap比TreeMap更合适——因为没有必要对键进行排序。查找应该是O(1)，所以理论上不受大小的影响。 - Boris the Spider

4M/sec是一个相当大的数字，我怀疑你的算法不够复杂，以至于成为了瓶颈。想一想，每个对象500个时钟周期并不算多。你的程序之所以慢，是因为数据集很大。如果你想让你的应用程序看起来响应迅速，还有其他技术可以使用。 - Jason Hu

@BoristheSpider：与普遍观念相反，HashMap的最坏时间复杂度为*O(n)，但平均复杂度为O(1)*。 - Willem Van Onsem

我会选择HashMap而不是TreeMap来获得更快的速度，因为TreeMap本质上与在数组上使用二分查找相同。 - neuronaut

Answer 1

这里需要使用哈希算法，但我建议避免使用HashMap，因为它只能处理对象，即每次插入long时必须构建一个Long对象，这可能会导致速度变慢。也许由于JIT的缘故，性能问题不是很明显，但我建议至少尝试以下方法，并将其与HashMap变体的性能进行比较：

将长整型保存在长度大于3000的长整型数组中，并通过一个非常简单（因此高效）的哈希函数手动进行哈希，例如index = key % n。由于您事先知道了3000个可能的值，因此可以经验性地找到一个数组长度n，使得这个简单的哈希函数不会引起冲突。因此，您可以避免重新哈希等操作，并获得真正的O(1)性能。

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

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

两者都由本地Lapack和BLAS实现支持，通常由非常聪明的人高度优化。也许您可以通过矩阵/向量代数的术语来制定算法，以便一次性（或分块）计算整个长数组。

- stewori

---

谢谢。我尝试通过在我的描述中使用long[]来避免将输入长整数装箱为对象。 输入数字是质数的乘积，我不确定如何为这些值创建无冲突的哈希函数，它们可能非常大，如何将它们压缩为唯一的整数？ 我不完全理解第二段是如何导致唯一整数列表的，请解释一下。 - andre.r

抱歉，当我提到3000时，我混淆了您的数字（忽略了3000是指结果值）。因此，查找数组实际上必须要大得多。我的建议是“经验性地”自动尝试一些n值，并观察是否会发生有害碰撞。由于您的映射大大压缩了值空间，某些碰撞可能不会有害，因为它们可能将不同的输入映射到正确的共享结果。然而，故意使用这种方法将涉及压缩理论，并且比使用普通哈希更加复杂。 - stewori

我也不是构建哈希函数的专家。使用质数的方法听起来仍然很有前途。至少它可以排除一些n值。例如，n可能不是由相同组合中出现在多个值中的质因子组成的数字。要确定是否可以进一步利用这一点来找到合适的n，需要更多的细节（质因子可以具有重复性吗？是否存在不作为因子出现的质数？）。我猜，由输入中未出现的质因子组成的n值可能是很好的候选项。但这只是一个猜测，抱歉。 - stewori

另一个想法：如果您在每个结果下面保存输入值（即在具有相应索引的另一个数组中），则甚至可以使用具有适度冲突的n，因为您可以轻松高效地确认查找。如果输入不匹配，只需通过计算结果来计算正确的结果。这样，映射绝大多数没有冲突的n就足够了。（但是，在这种情况下，除非您保存了一组输入值列表，否则无害冲突将无法受益，但这会再次变得更慢和复杂。） - stewori

Answer 2

大约有150,000,000个不同的关键对象，以及大约3,000个不同的值。

由于只有少量的值，您应该确保它们得到重复使用（除非它们是相当小的对象）。为此，Interner非常适合（尽管您可以运行自己的）。

我尝试了哈希映射和树映射，但两者都遇到了OutOfMemoryError。

它们都有巨大的内存开销。而且使用TreeMap没有太多意义，因为它使用了一种二进制搜索，而您已经尝试过了。

至少有三种长整型到对象映射的实现可用，可以在Google上搜索“primitive collections”。这应该比您的两个数组稍微使用更多的内存。由于哈希通常为O（1）（让我们忽略最坏情况，因为没有理由发生，是吗？）并且具有更好的内存局部性，它将以20倍的速度打败(*)二分查找。您的二分查找需要log2（150e6），即大约27个步骤，并且哈希可能平均需要两个步骤。这取决于您如何紧密地打包哈希表；这通常是在创建时给出的参数。

如果您运行自己的哈希表（您很可能不应该这样做），我建议使用大小为1 << 28的数组，即268435456个条目，以便您可以使用位操作进行索引。

---

(*) 这样的预测很困难，但我相信值得一试。

- maaartinus