大きな数字で次の増分を見つける最も効率的な方法

Question

私は数字がlong nbr = 10000です。私はこれを増減しており、増減する金額は金額に左右されます。 nbr > xの場合は、nbr + = xx、nbr > yの場合はnbr + = yyなどとなります。他の要因によっては、インクリメント値（xx、yyなど）も変化します。 、など）が変更されます。私は上記のロジックに従って増分された数値を返す関数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)); 
    } 

Answer 1

あなたは下限見つけることによってfloorEntryを使用して対数時間でそれを行うことができます。

このような TreeMapでこの店の前に

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

キーと値 -

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

floorEntryが以下与えられたキーに等しい最大のキーを返しますので、あなたはx + 1の代わりxを格納する必要があります。ここでは、nbrの値が> xのときに増加しています。

希望すると助かります！

Answer 2

あなたのTreeMapアプローチはlog（N）の複雑さを持ちます。ここでNは境界の数です。境界の数が十分に少ない場合、これは完全に許容可能です。

あなたのコメントは、あなたの数字スペースがかなり制限されていると述べました。 100万の可能な数字だけで、numberをインデックスとして使用してルックアップテーブル（配列）を作成することもできます。これはあなたにO（1）を与えますが、ルックアップテーブルは独自のビルドコストとメモリ消費を必要としません。

テーブルの変更の間のルックアップの数に応じて、ルックアップテーブルが高速または低速になる場合があります。

プログラムがランタイムのかなりの部分を費やしていない限り、getIncrementValueAboveNbr（）を呼び出すとおそらくあなたの時間を無駄にしています。どのような方法でもプロファイルを作成してください。このメソッドが時間の大部分を明らかにする場合にのみ、それを書き直すことを検討してください。