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

怎么样：

s.find(_._1.contains(11)).map(_._2)

Answer 2

取决于您的用例，但鉴于您关心效率，我假设您将进行大量查找。

我还假设您使用一个 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

Scala efficient set inclusion detection