Scala 中 Set union 的性能问题

Question

我刚刚在 Scala Set API 中遇到了一个奇怪的行为。这是我的功能剥离了与项目其余部分相关的内容

def grade(...): Double = {
  val setA: HashSet = // get from somewhere else
  val setB: HashSet = // get from somewhere else
  if ((setA size) == 0 || (setB size) == 0) return 0
  else return (setA & setB size) / (setA | set B size)
}

这个函数在一个循环内被调用了很多次，整个循环在大约 4.5 秒内执行。但是当用大小的总和(粗略近似)替换联合的大小时，为了测试联合操作的影响，执行时间减少到 0.35 秒左右......

def grade(...): Double = {
  val setA: HashSet = // get from somewhere else
  val setB: HashSet = // get from somewhere else
  if ((setA size) == 0 || (setB size) == 0) return 0
  else return (setA & setB size) / (setA size + set B size)
}

Answer 1

好吧，您无法比较像 2 Ints 这样的简单运算与 union 2套操作。我希望这些操作的性能非常不同，特别是如果您的 Set 包含很多元素。

你不需要联合，因为你已经做了一个交集。请尝试以下操作:

def grade: Double = {
  val setA: HashSet = // get from somewhere else
  val setB: HashSet = // get from somewhere else
  if ((setA size) == 0 || (setB size) == 0) return 0
  else {
     val inter = setA & setB size
     return inter / ((setA size) + (setB size) - inter)
  }
}

但是，我发现您的测量有点奇怪，因为我预计两个操作(并集和相交)花费的时间大约相同 O(n)。去掉union应该能将性能提升一半(2s)...