Scala TreeSet 过滤器复杂度

Question

我有一个间隔的TreeSet(带有开始和结束的案例类)。如果对此树集进行过滤，例如

treeSet.filter(x => input <= x.end && input >= x.start) 

这预计会在 logN 时间内运行吗？

Answer 1

不，它是 O(N)；你可以看到代码:

private def filterImpl(p: A => Boolean, isFlipped: Boolean): Repr = {
  val b = newBuilder
  for (x <- this)
    if (p(x) != isFlipped) b += x

  b.result
}

---

使用from，to是O(log(n))

val ts = TreeSet(1,2,3,4,5)
ts.from(1).to(3) // TreeSet(1, 2, 3)