7

简单地说，这就是我想要做的：

我有一组Range连续的对象（不重叠，它们之间没有间隙），每个对象都包含一个start和endint，以及对另一个对象的引用obj。这些范围不是固定大小的（第一个可以是 1-49，第二个可以是 50-221，等等）。这个集合可能会变得非常大。

我希望找到一种方法来查找包含给定数字的范围（或更具体地说，它引用的对象），而不必遍历整个集合来检查每个范围以查看它是否包含数字。这些查找将经常执行，因此速度/性能是关键。

有谁知道可能在这里帮助我的算法/方程？我正在用 Java 编写。如果需要，我可以提供更多细节，但我想我会尽量保持简单。

谢谢。

4

3 回答 3

4

如果听起来您想使用 a TreeMap，其中键是范围的底部，值是Range对象。

然后要识别正确的范围，只需使用该floorEntry()方法非常快速地获取最接近的（小于或等于）Range，它应该包含密钥，如下所示：

    TreeMap<Integer, Range> map = new TreeMap<>();
    map.put(1, new Range(1, 10));
    map.put(11, new Range(11, 30));
    map.put(31, new Range(31, 100));

    // int key = 0; // null
    // int key = 1; // Range [start=1, end=10]
    // int key = 11; // Range [start=11, end=30]
    // int key = 21; // Range [start=11, end=30]
    // int key = 31; // Range [start=31, end=100]
    // int key = 41; // Range [start=31, end=100]
    int key = 101; // Range [start=31, end=100]
    // etc.

    Range r = null;
    Map.Entry<Integer, Range> m = map.floorEntry(key);
    if (m != null) {
        r = m.getValue();
    }
    System.out.println(r);

由于树总是按底部范围边界的自然顺序排序，因此您的所有搜索最多将是 O(log(n))。

当您的键完全超出范围时，您需要添加一些完整性检查（例如，当它们的键超出地图的末尾时，它会返回地图中的最后一个Range），但这应该让您了解如何继续。

于 2014-07-28T21:12:23.777 回答
1

假设您的查找是最重要的，并且您可以节省 O(N) 内存和大约 O(N^2) 的预处理时间，那么算法将是：

  • 引入一个类ObjectsInRange，其中包含：范围开始（int startOfRange）和一组对象（Set<Object> objects）
  • 引入一个ArrayList<ObjectsInRange> oir，其中将包含ObjectsInRange按startOfRange
  • 对于每个Range r，确保存在ObjectsInRange（让我们称它们为aand b）使得a.startOfRange = r.startand b.startOfRange = b.end。然后，对于所有ObjectsInRange xbetweena和 until (但不包括) b，添加r.obj到他们的x.objects集合

那么，查找如下：

  • 对于 integer x，找到这样i的oir[i].startOfRange <= x和oir[i+1].startOfRange > x
  • 注意：i可以在 O(log N) 时间内通过二等分找到！
  • 你的对象是oir[i].objects
于 2014-07-28T21:01:15.090 回答
0

如果集合是有序的，那么您可以实现二进制搜索以在 O(log(n)) 时间内找到正确的范围。对于非常大的集合，它不如散列有效，但如果您的范围少于 1000 个左右，它可能会更快（因为它更简单）。

于 2014-07-28T21:04:52.897 回答