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

您正在寻找的是 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。

于 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};

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

更新

我还写了一个基准，无论我如何尝试，我都会输掉赌注，因为比率大约是 3 而不是 5。S001024我的结果中奇怪的东西代表大小 1024。

于 2013-10-12T12:52:41.750 回答