Scala TreeSet 过滤器复杂性

Question

我有一个间隔TreeSet(带有开始和结束的案例类(。如果 a 在此树集上执行过滤器，例如

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)

Answer 2

TreeSet仅对搜索操作具有O(LogN(复杂性。
筛选器需要将谓词函数应用于每个元素，并仅返回谓词函数为真的元素。因此，复杂度为 O(N(

当您认为谓词函数可以是任何东西(不仅仅是范围过滤器(时，这是有道理的。

可以使用 TreeSet.from 和 TreeSet.to 方法来执行范围筛选器

import scala.collection.immutable.TreeSet
val st = TreeSet[Int](4,2,3,7,6,5,3,4)
println(st)
println(st.from(5))
println(st.from(4).to(6))