查找大數中下一個增量的最有效方法

我有一個數字long nbr = 10000。我在增加和減少這個數字，增加或減少的數量取決於它的數值。如果nbr > x，那麼nbr + = xx，如果nbr > y，那麼nbr + = yy等。取決於其他因素，增量值（xx，yy等）將改變並且增量值改變的界限（x，y等）將會改變。我想要一個函數public int increaseNbr（int nbr），根據上面的邏輯返回一個遞增的數字，並儘可能有效地做到這一點。目前我正在執行它，但我有一種感覺，它不是非常有效。查找大數中下一個增量的最有效方法

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)); 
    }

來源

2017-03-24 user3607022

從不檢查'compareTo'調用結果再次-1或1. Comparable.compareTo'的合約允許任何*負數如果此對象低於提供的對象且* any *正數if這個對象更大。除此之外：性能問題最重要還是您想要簡潔易讀的解決方案？價格在多大範圍內？他們是整數是否正確？ –

性能是重中之重。感謝您指出compareTo問題，實際上這是我的一個錯字。數字的範圍在0到1,000,000之間，我有時重新填充地圖。 – user3607022

如果很少進行重新填充，並且您的方法被非常頻繁地調用，那麼可以考慮預先計算一個長度爲1,000,000的int [] incvals]，其中包含每個可能的nbr的增量值，並使用帶有* nbr + incvals [nbr] O（1）*複雜性。儘管這種方法需要大約4MB的RAM。另外使用這種方法，方法代碼變得非常短，並且很可能遲早會內聯，這樣即使方法調用也可以免費。 –

您可以通過查找下限使用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返回小於或等於給定鍵的最大關鍵。當nbr的值爲> x時，這裏我們正在滔滔不絕。

希望它有幫助！

來源

2017-03-24 19:24:24

您的TreeMap方法具有log（N）的複雜度，其中N是邊界的數量。如果邊界的數量足夠小，這可能是完全可以接受的。

您在評論中提到您的號碼空間相當有限。只有一百萬個可能的數字，你也可以使用數字作爲索引建立一個查找表（數組）。這會給你O（1），但查找表確實會產生自己的開銷和內存消耗。

根據表更改之間的查找次數，查找表可能會更快或更慢。

除非你的程序花費了大量的運行時調用getIncrementValueAboveNbr（），否則你可能會浪費你的時間。剖析任何使用該方法的方法，並且只有當這揭示了在那裏花費的大部分時間時，才考慮重寫它。

來源

2017-03-24 19:40:22 Durandal

查找大數中下一個增量的最有效方法

回答

相關問題