用于跟踪部分聚合值的 Java 算法

Question

我的程序评估了数亿条记录。所以内存和性能的问题很重要。让每条记录都有键 - ticketID。还记录有字段值和字段 source_name。在源 ticketID 中有 1 到许多(近 100)个 source_name。我只需要按 ticketID 进行聚合 - 接收近 100 万条记录，但还必须具有指定 source_name 的可能减法值 - 所以我有跟踪贡献。

是否存在一些算法或数据结构可以解决这个问题？

Answer 1

我不能完全解析这个问题，所以我假设:

• “近百万条记录”表示有近百万个ticketID字段。
• 系统中有“近 100”个不同的 source_name。
• 并非所有 ticketId 都有 source_name。我们没有 1 亿个 ticketID x source_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);
}

如果你编辑你的问题，我会编辑我的答案以防我做出了一些不正确的假设。