我正在编写一个将数字(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次查询。
TreeMap<Long, Object>
吗?而且你的缓存几乎是只读的,对吧? - Jason HuHashMap
比TreeMap
更合适——因为没有必要对键进行排序。查找应该是O(1)
,所以理论上不受大小的影响。 - Boris the SpiderHashMap
的最坏时间复杂度为*O(n),但平均复杂度为O(1)*。 - Willem Van Onsem