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

您正在寻找的是 SortedMap 及其方法 tailMap 和 firstKey。查看documentation了解全部详情。

与普通数组相比，这种方法的优势在于易于维护您的范围:您可以在任何时候插入/删除新的边界，几乎没有运行时成本；对于数组，这意味着完整复制两个并行数组。

更新

我已经为这两个变体编写了代码并对其进行了基准测试:

@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。