我的程序评估了数亿条记录。所以内存和性能的问题很重要。 让每条记录都有键 - ticketID。还记录有字段值和字段 source_name。 在源 ticketID 中有 1 到许多(近 100)个 source_name。 我只需要按 ticketID 进行聚合 - 接收近 100 万条记录,但还必须具有指定 source_name 的可能减法值 - 所以我有跟踪贡献。
是否存在一些算法或数据结构可以解决这个问题?
最佳答案
我不能完全解析这个问题,所以我假设:
- “近百万条记录”表示有近百万个
ticketID
字段。 - 系统中有“近 100”个不同的
source_name
。 - 并非所有
ticketId
都有source_name
。我们没有 1 亿个ticketID
xsource_name
组合。 - 您希望能够对所有
ticketId
进行总计,但也希望对source_name
进行总计。
根据这些假设,我将使用 map 的 Map
。外层 Map
有一个键 source_name
和内层 Map
的值。内部 Map
具有 ticketId
的键和累积的 value
。
所以伪代码看起来像这样:
Map<String, Map<Integer,Double>> valueMap =
new HashMap<String, Map<Integer,Double>>();
while (...reading in and processing data...) {
int ticketId = ...;
String sourceName = ...;
double entryValue = ...;
Map<Integer,Double> sourceNameMap = valueMap.get(sourceName);
Double value = sourceNameMap.get(ticketId);
if (oldValue == null) {
value = entryValue;
} else {
value += entryValue;
}
sourceNameMap.put(ticketId, value);
}
您可以通过将每个 source_name
map 相加来轻松获得总数。当然,如果有帮助,您也可以为每个 source_name
保留一个总计。如果您的系统可以为 JVM 分配一个千兆字节,那么它应该能够处理大量的 ticketID
x source_name
对。
您可能会考虑创建一个可变的内部值类来节省 GC 周期:
private static class MutableValue {
double value;
public MutableValue(double value) {
this.value = value;
}
public void add(double value) {
this.value += value;
}
}
那么你可以说:
MutableValue value = sourceNameMap.get(ticketId);
if (oldValue == null) {
sourceNameMap.put(new MutableValue(entryValue));
} else {
value.add(entryValue);
}
如果你编辑你的问题,我会编辑我的答案以防我做出了一些不正确的假设。
关于用于跟踪部分聚合值的 Java 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7652169/