在大数中找到下一个增量的最有效方法

Question

我有一个号码long nbr = 10000。我正在增加和减少这个，增加或减少的数量取决于它的价值。如果 nbr > x，则 nbr += xx，如果 nbr > y，则 nbr += yy 等。根据其他因素，增量值（xx、yy 等）将发生变化，并且其中的限制也会发生变化增量值变化（x、y 等）将发生变化。我想要一个函数 public int increaseNbr(int nbr) returns 根据上述逻辑递增的数字，并尽可能高效地执行此操作。目前我正在像下面这样实现它，但我觉得它不是很有效。

private TreeMap<Integer, Integer> aboveNbr_increment_map;

private Integer getIncrementValueAboveNbr(int nbr) {

    // finds the valid increment below a certain price
    Map.Entry<Integer, Integer> entry = aboveNbr_increment_map.lastEntry();

    while (entry != null) {

        if (price>=entry.getKey()) {
            return entry.getValue();
        }

        entry = aboveNbr_increment_map.lowerEntry(entry.getKey());
    }

    // otherwise return the lowest increment size
    return aboveNbr_increment_map.get(aboveNbr_increment_map.firstKey());
}

    public Integer getNextNbrAbove(int nbr) {

        return nbr + this.getIncrementValueAboveNbr(nbr));
    }

Answer 1

您可以使用 floorEntry 通过查找下限以对数时间完成此操作。

private TreeMap<Integer, Integer> aboveNbr_increment_map;

private Integer getIncrementValueAboveNbr(int nbr) {

    Entry<Integer, Integer> entry = aboveNbr_increment_map.floorEntry(nbr);

    if(entry != null) {
        return nbr + entry.getValue();
    }

    return aboveNbr_increment_map.get(aboveNbr_increment_map.firstKey());
}

在此之前将键值存储在 TreeMap 中，像这样 -

aboveNbr_increment_map.put(x + 1, xx);
aboveNbr_increment_map.put(y + 1, yy);

您需要存储 x + 1 而不是 x 因为 floorEntry returns 小于或等于给定键的最大键。当 nbr 值为 > x.

时，我们在这里增加

希望对您有所帮助！

Answer 2

您的 TreeMap 方法的复杂度为 log(N)，其中 N 是边界数。如果边界的数量足够小，这可能是完全可以接受的table。

您在评论中提到您的号码 space 受到相当限制。只有一百万个可能的数字，您还可以使用数字作为索引构建查找 table（数组）。这会给你 O(1)，但查找 table 确实会产生自己的构建成本和内存消耗。

根据 table 变化之间的查找次数，查找 table 可能更快或更慢。

除非您的程序花费相当大的运行时间来调用 getIncrementValueAboveNbr()，否则您可能是在浪费时间。分析任何使用该方法的人，只有当这揭示了在那里花费的大部分时间时才考虑重写它。

在大数中找到下一个增量的最有效方法

Most efficient way to find next increment in a big number

java

algorithm

performance

coding-efficiency