Java最快获取匹配范围的方法

Question

我有一组整数范围，它们代表类的下限和上限。例如：

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 次查找。如果班级人数相等，我可以使用分组。是否有标准技术可以更快地找到正确的范围？

Answer 1

您正在寻找的是 aSortedMap及其方法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

解释：数组搜索速度仅为两倍，并且该系数在数组大小上相当稳定。在给出的代码中，数组大小为 1024，因子为 1.9。我还使用数组大小​​ 128 进行了测试，其中因子为 2.05。