6

クラスの下限と上限を表す一連の整数範囲があります。例えば：

0..500 xsmall
500..1000 small
1000..1500 medium
1500..2500 large

私の場合、500 を超えるクラスが存在する可能性があります。これらのクラスは重複しませんが、サイズが異なる場合があります。

たとえば、リストを介した単純な線形検索として、一致する範囲の検索を実装できます。

class Range
{
  int lower;
  int upper;
  String category;

  boolean contains(int val)
  {
    return lower <= val && val < upper;
  }
}

public String getMatchingCategory(int val)
{
   for (Range r : listOfRanges)
   {
      if (r.contains(val))
      {
         return r.category;
      }
   }
   return null;
}

ただし、これは遅いようです。平均して N/2 回のルックアップが必要です。クラスの規模が同じであれば、分割を使用できます。正しい範囲をより速く見つけるための標準的な手法はありますか?

4

2 に答える 2

4

あなたが探しているのはSortedMapとそのメソッドtailMapとfirstKeyです。詳細については、ドキュメントを参照してください。

プレーン配列に対するこのアプローチの利点は、範囲を維持しやすいことです。実行時のコストがほとんどかからずに、いつでも新しい境界を挿入/削除できます。配列では、両方の並列配列を完全にコピーすることを意味します。

アップデート

両方のバリアントのコードを作成し、ベンチマークしました。

@State(Scope.Thread)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public class BinarySearch
{
  static final int ARRAY_SIZE = 128, INCREMENT = 1000;
  static final int[] arrayK = new int[ARRAY_SIZE];
  static final String[] arrayV = new String[ARRAY_SIZE];
  static final SortedMap<Integer,String> map = new TreeMap<>();
  static {
    for (int i = 0, j = 0; i < arrayK.length; i++) {
      arrayK[i] = j; arrayV[i] = String.valueOf(j);
      map.put(j, String.valueOf(j));
      j += INCREMENT;
    }
  }
  final Random rnd = new Random();
  int rndInt;

  @Setup(Level.Invocation) public void nextInt() { 
    rndInt = rnd.nextInt((ARRAY_SIZE-1)*INCREMENT); 
  }

  @GenerateMicroBenchmark
  public String array() {
    final int i = Arrays.binarySearch(arrayK, rndInt);
    return arrayV[i >= 0? i : -(i+1)];
  }

  @GenerateMicroBenchmark
  public String sortedMap() {
    return map.tailMap(rndInt).values().iterator().next();
  }
}

ベンチマーク結果:

Benchmark     Mode Thr    Cnt  Sec         Mean   Mean error    Units
array        thrpt   1      5    5       10.948        0.033 ops/usec
sortedMap    thrpt   1      5    5        5.752        0.070 ops/usec

解釈: 配列検索は 2 倍の速さであり、この係数は配列サイズ全体で非常に安定しています。提示されたコードでは、配列サイズは 1024 で、係数は 1.9 です。また、係数が 2.05 の配列サイズ 128 でテストしました。

于 2013-10-12T12:46:34.670 に答える
1

ほら、Arrays.binarySearchあなたの友達です。すべての境界を入れて、可能なケースを処理するだけです。範囲がそれらの間に穴を残さないと仮定すると、上限を入れるだけで済みます。

あなたの例のために

0..500 xsmall
500..1000 small
1000..1500 medium
1500..2500 large

あなたが使うだろう

int[] boundaries = {500, 1000, 1500, 2500};

入力を調べます。2 つのケース (見つかった/見つからなかった) を処理すれば完了です。範囲は忘れてください。それらは素晴らしいですが、あなたの問題には合いません。

アップデート

ベンチマークも書きましたが、比率が 5 ではなく約 3 であるため、どのように試しても賭けに負けます。S001024私の結果のような奇妙なものは、サイズ 1024 を表しています。

于 2013-10-12T12:52:41.750 に答える