是否存在用于查找匹配任意范围的值的数据结构? [英] Is there a data structure for looking up values matching arbitrary ranges?

问题描述

对于键相等性查找，我们可以使用像哈希图这样的数据类型，但是是否存在用于查找匹配任意范围的值的数据结构?

For key equality lookup, we can use a data type like a hashmap, but is there a data structure for looking up values matching arbitrary ranges?

下面的Rust代码使用match表达式模拟了这一点，但我希望不必在代码中对案例进行硬编码.

The Rust code below emulates this using a match expression but I'm looking to not have to hard code the cases in code.

let x = 5;

match x {
    d if d <= 0 => println!("d <= 0"),
    d if 1 < d && d <= 3 => println!("1 < d <= 3"),
    d if 4 < d && d <= 6 => println!("4 < d <= 6"),
    _ => {}
}

(生锈的操场)

推荐答案

您可以创建一个包含开始和结束值的范围列表.按起始值对该列表进行排序.

You could create a list of ranges, with start and end values. Sort that list by start value.

当您查询时，请对起始值进行二进制搜索.当您的值大于或等于起始值且小于或等于终止值时，您就知道正确的范围.

When you get a query, do a binary search on the starting values. When your value is greater than or equal to the starting value, and less than or equal to the ending value, you know you got the right range.

如果总范围相对较小(例如，从1到1000的整数)，则可以预先填充对范围的引用数组.假设您有4个范围，可能的查询值为0到10:

If you have a relatively small total range (say, integers from 1 to 1000), you could pre-fill an array of references to ranges. Say you have the 4 ranges and the possible query values are 0 through 10:

range1: 0, 2
range2: 3, 5
range3: 6, 8
range4: 7, 10

那么您的数组将是[range1, range1, range1, range2, range2, range2, range3, range3, range3, range4, range4, range4, range4].

您可以将其扩展到所需的大小，具体取决于要花费的内存量.这样可以直接查找.

You could extend that to however large you want it, depending on how much memory you want to spend. That gives you a direct lookup.

这篇关于是否存在用于查找匹配任意范围的值的数据结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！