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次查找。如果类别大小相等，我可以使用除法。是否有一种标准技术可以更快地找到正确的范围？

- Rob Audenaerde

---

不需要等大小，范围由用户提供。 - Rob Audenaerde

有一种叫做“区间树”的结构，专门用于存储和查询范围。我不知道是否有Java实现，但可能已经有了，在任何情况下，逻辑相当简单。 - Boris the Spider

Answer 1

你需要的是一个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

解释：数组搜索只快两倍，这个因素在不同的数组大小中保持相对稳定。在所提供的代码中，数组大小为1024，因子为1.9。我还测试了数组大小为128的情况，其中因子为2.05。

- Marko Topolnik

---

@RobAu：将所有上限放在那里应该就可以了。但这永远无法像纯二分搜索那样快。 - maaartinus

@maaartinus 但它也是通过树进行二分查找。确实存在差异，但只是一个常数因子，并且不是很大。另一方面，改变结构的时间复杂度为O(logN)，而使用数组则为O(N)。 - Marko Topolnik

同意，这里只有一个恒定的开销，但它可能非常大：树不完美平衡，节点间接引用，包装整数间接引用，强制转换，对象创建等等。我敢打赌这至少是5倍 - 你想进行基准测试吗？ - maaartinus

关于变异，我也同意，但是我敢打赌，在多达100个元素的情况下，数组会更快。对于巨大的尺寸和需要更高的灵活性的情况下，树会胜出。 - maaartinus

如果您使用了 TreeMap 的 ceilingEntry() 方法，您将避免创建新的临时映射和迭代器。通过这种改变，排序映射只会慢 1.6 倍。 - Oliv

Answer 2

这里，Arrays.binarySearch 是您的好帮手。只需将所有边界放入并处理可能的情况即可。假设您的范围之间没有空隙，您只需要放入上限即可。

对于您的示例：

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

你会使用

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

查找输入内容。处理两种情况（找到/未找到），然后就完成了。忘记范围，它们很好，但不适合您的问题。

更新

我还编写了一个基准测试，无论如何我都会输掉我的赌注，因为比率大约是3而不是5。在我的结果中出现的奇怪事物，如S001024，表示大小为1024。

- maaartinus

---

啊，这很有道理。即使是“空洞”也可以像这样被覆盖，通过将它们定义为具有与周围有效范围相匹配的边界的“null”类别。 - Rob Audenaerde

关于空缺：当然。但我想在一个设计良好的范围系统中不应该有任何空缺。实际上，我更喜欢考虑这样的事情：“如果x小于500，则为xsmall；否则，如果x小于1000，则为small；否则，如果...则为xxxlarge”，不留下任何问题的余地。 - maaartinus

请注意，Caliper的(int reps)方法在循环展开和提取内容时会以奇怪和不可预测的方式干扰测量。相比之下，jmh没有这些问题，是一个优秀的基准测试工具，胜过Caliper。请参见作者的这个精彩演讲。 - Marko Topolnik

谢谢你提供的链接，真的很棒！不过，我还不太确定。循环展开正是在“现实生活”中发生的事情。你只需要小心不要做一些可以简化的事情，比如将一个常数相加。这就是视频在27:20出现的情况。在我的基准测试中，除了将整个内部循环折叠成result += someConstant之外，我没有看到类似的情况，这对于JVM来说太困难，显然也不会发生。 - maaartinus