java - 找到下一个最小的键(需要性能建议)

Question

我需要一些性能方面的建议。我有一个 Map<DateTime, String> .我需要类似以下方法的方法:

Map<DateTime, BigDecimal> map; // about 50 entries. Btw: Which impl to choose?

BigDecimal findNextSmaller(DateTime input) {

    DateTime tmp = null;

    for(DateTime d : map.keySet()) {
        if(tmp == null && d < input) {
            tmp = d;
        }
        if(d < input && d > tmp) {
            tmp = d;
        }
    }

    return map.get(tmp);
}

所以基本上我只是迭代我的 Map 的 keySet并尝试找到与 input 相比下一个最小的键.

这个方法将被连续调用大约 1.000.000 次:

BigDecimal sum;

List<Item> items; // about 1.000.000 Items

for(Item i : items) {
    sum = sum.add(findNextSmaller(i.getDateTime()));
}

现在我正在寻找一种让事情变得更快的方法。

我的第一个想法是制作一个 OrderedList来自 Map的键集。所以平均而言，我只需要迭代 DateTime 的一半以上秒。然后就做一个 map.get(dateTimeFromOrderedList)得到匹配值。

但这就是我能做的一切吗？

Answer 1

您可以使用具有 built-in method 的 TreeMap为此:

TreeMap<DateTime, BigDecimal> map = new TreeMap<>();
//populate the map

BigDecimal findNextSmaller(DateTime input) {
    return map.ceilingEntry(input).getValue(); //add exception checking as required
}

注意:您可能需要 ceilingEntry或 higherEntry取决于你是否想要(resp.)>=或 > .