表示区间映射的数据结构

Question

这是一个函数，可以根据年龄推断出一个人的状态

def getStatus(age: Int): String = {
  age match {
    case age if 0 until 2 contains age => "infant"
    case age if 2 until 10 contains age => "child"
    case age if 10 until 18 contains age => "teen"
    case _ => "adult"
  }
}

假设边界可以改变。我们可以决定一个人在 3 岁之前可以被视为婴儿。随着它们的变化，我们不希望边界被硬编码，它们将存储在外部。

什么是可以基于区间存储映射的数据结构？

类似

val intervalMap = IntervalMap(
  (0, 2) -> "infant",
  (2, 10) -> "child",
  (10, 18) -> "teen",
  (18, 200 ) -> "adult"
)
intervalMap(1) // "infant"
intervalMap(12) // "teen"

我正在使用 Scala 进行开发，但非常感谢与语言无关的答案。

Answer 1

简单回答

Scala 标准库中没有任何东西可以做到这一点，但是如果像您的示例中那样“类别”的数量很少，那么实现一个简单的 O(N) 并没有什么害处 apply 方法 IntervalMap class.

def apply(in: Int) = categories.collectFirst { 
  case ((min, max), value) if in >= min && in < max => value 
}

番石榴

Guava 库似乎有一个 RangeMap class 似乎适合您的 use-case。

更有趣的 DIY 创意

要获得 O(log N) 查找特征，您可以将类别数据表示为二叉树：

每个节点定义一个min和max
根节点代表绝对最小值到绝对最大值，例如Int.MinValue 到 Int.MaxValue
叶节点定义一个value（例如"child"）
Non-leaf 节点定义了一个 split 值，其中左侧 child 的 max 将等于 split，右侧 child的min将等于split
根据您输入的数字（例如age）是否大于或小于当前节点的split

你必须在构建树时处理它的平衡问题……老实说，这可能是 Guava 在幕后所做的（我没有研究实现）

表示区间映射的数据结构

Data structure to represent mapping of intervals

scala

data-structures