表示区间映射的数据结构

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)没有害处在您的IntervalMap类上使用apply方法。

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

番石榴

看起来Guava库有一个RangeMap类，似乎适合你的用例。

得到一个O(log N)查找特性，您可以将类别数据表示为二叉树:

• 每个节点定义一个min和max
• 根节点代表绝对最小值到绝对最大值，如Int.MinValue到Int.MaxValue
• 叶节点定义value(例如"child")
• 非叶节点定义一个split值，其中左子节点的max等于split，右子节点的min等于split
• 根据输入数(如age)是否大于或小于当前节点的split，从左/右遍历树中查找值

你必须处理平衡树，因为它被建立…顺便提一下，这可能就是Guava在幕后的工作方式(我没有研究实现)