我目前正在 ColdFusion 9 中实现类似枢轴数据可视化的通用模型。
我对支持多个度量不感兴趣,并且该模型公开了一个 numeric valueAt(string colKey, string rowKey)
函数, View 可以调用该函数,以便检索基于列和行维度的度量结果聚合。
例如,对于下面的数据集,如果度量为 AVG(Age)
并且列维度为 Rank
,则 model.valueOf('3', '')
将返回 2.33
。
Wine Age Rank
WineA 3 3
WineB 4 2
WineC 2 3
WineD 2 3
现在,我自然想到的数据结构是使用 java.util.HashMap 来存储计算数据,使用转换为字符串的列和行值的组合作为键。这意味着根据数据集,我可能有大量以相同前缀开头的键。
我特意创建了一个大型数据集(100 万个条目),其中包含多个具有相同前缀的字符串,并检查了使用默认 java String.hashCode()
算法和 MurmurHash3 获得的存储桶冲突的百分比。 .
以下是我构建数据集示例的方法:
<cfset maxItemsCount = 1000000>
<cfset tokens = ['test', 'one', 'two', 'tree', 'four', 'five']>
<cfset tokensLen = arrayLen(tokens)>
<cfset items = []>
<cfset loopCount = 1>
<cfloop condition="arrayLen(items) lt maxItemsCount">
<cfset item = ''>
<cfloop from="1" to="#tokensLen#" index="i">
<cfset item = listAppend(item, tokens[i] & loopCount, '_')>
<cfset arrayAppend(items, item)>
</cfloop>
<cfset ++loopCount>
</cfloop>
当数组初始化为 2 * 条目数
时,我与 String.hashCode()
发生了 27% 冲突,对于 Murmur 发生了 22% 冲突。 java.util.HashMap
仅存储和检索一次 key 就花费了大约 2580 毫秒。
我正在寻找有关如何提高性能的想法,无论是使用不同的数据结构(可能是嵌套 HashMap ?)还是找到一种方法来减少冲突次数而不损害 API 签名?
谢谢!
最佳答案
对于一百万个条目,总会存在一些冲突(除非您的数组比 1e12 个条目长得多:D)。我猜 MurmurHash 在这里做得很完美,但你可以尝试 MD5 进行比较(这在某种程度上保证了完美的工作)。
Now, the data structure that naturally came to my mind was to use a java.util.HashMap to store the computed data, using a combination of column and row values converted to string as keys. This means that depending on the data set, I might potentially have a very large number of keys that will start with the same prefix.
您正在连接字符串,因此会产生相当多的垃圾。创建一个可能会更好
@Value static class Key {
private final String row;
private final String column;
}
作为 HashMap
的键,其中 @Value
是 Lombok注释生成所有无聊的东西,例如 equals
、hashCode
和构造函数。
无需 Lombok,您也可以轻松完成,甚至更好:
static class Key {
Key(String row, String column) {
// Do NOT use 31 as a multiplier as it increases the number of collisions!
// Try Murmur, too.
hashCode = row.hashCode() + 113 * column.hashCode();
this.row = row;
this.column = column;
}
public int hashCode() {
return hashCode;
}
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Key)) return false;
Key that = (Key) o;
// Check hashCode first.
if (this.hashCode != that.hashCode) return false;
if (!this.row.equals(that.row)) return false;
if (!this.column.equals(that.column)) return false;
return true;
}
private final int hashCode;
private final String row;
private final String column;
}
关于java - 从基于字符串的键路径快速访问值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25627408/