Scala高效集包含检测

Question

例如,设置第一项是集合的元组集合

val xs = Seq(
  ((1 to 5).toSet ++ Set(9), "apple"),
  ((15 to 17).toSet,         "pear"),
  ((21 to 30).toSet,         "grape"))

给定一个值x:Int,如何有效地识别第二个项目？(真实用例包括数千套.)

对于val x = 22其结果将是Some("grape"),对于val x = 19结果将是None.

注意每组中的值不一定是连续的.

注意集不重叠(任何集合交集都证明为空).

Answer 1

取决于你的用例,但鉴于你关心效率,我假设你会做很多查找.

我还假设你使用了一个xs,并在很多时候查找.

预处理xs成地图Int->String

val xsMap = (xs flatMap { case (s, v) => s.map((_,v))}).toMap[Int, String]

然后查找元素是微不足道的(和O(1))

xsMap.get(22)            //> res0: Option[String] = Some(grape)
xsMap.get(19)            //> res1: Option[String] = None