在Scala中创建更多"功能"代码以使用不可变集合

Question

我正在将一个算法从Java移植到Scala,它在VP树上进行范围搜索.简而言之,树中的节点具有空间坐标和半径:该半径内的节点可以在左子树上找到,而该半径外的节点可以在右子树上找到.范围搜索尝试在查询对象的指定距离内查找树中的所有对象.

在Java中,我向函数传递了一个arraylist,它在其中累积了结果,可能会递归其中一个或两个子树.这是Scala的直接端口:

def search(node: VPNode[TPoint, TObject], query: TPoint, radius: Double,
    results: collection.mutable.Set[TObject]) {

  var dist = distance(query, node.point)

  if (dist < radius)
    results += node.obj

  if (node.left != null && dist <= radius + node.radius)
    search(node.left, query, radius, results)

  if (node.right != null && dist >= radius + node.radius)
    search(node.right, query, radius, results)
}

Scala的默认集合类型是不可变的,我认为不得不一直打字有点烦人collection.mutable.,所以我开始研究它.似乎建议使用不可变集合几乎总是正常的:我使用此代码进行数百万次查找,而且在我看来,复制和连接结果数组会降低它的速度.

例如,这样的答案表明问题需要更多地"功能性"接近.

那么,我应该怎么做才能以更加Scala风格的方式解决这个问题呢？理想情况下,我希望它与Java版本一样快,但我对解决方案感兴趣(并且可以随时对它们进行分析以查看它是否有很大不同).

请注意,我刚刚开始学习Scala(想想我可能会对有用的东西不屑一顾)但我不熟悉函数式编程,之前曾使用过Haskell(尽管我认为我不擅长它! ).

Answer 1

这是我认为更实用的方法:

val emptySet = Set[TObject]()

def search(node: VPNode[TPoint, TObject], query: TPoint, radius: Double): Set[TObject] = {
  val dist = distance(query, node.point)

  val left = Option(node.left) // avoid nulls
    .filter(_ => dist <= radius + node.radius) // do nothing if predicate fails
    .fold(emptySet)(l => search(l, query, radius)) // continue your search

  val right = Option(node.right)
    .filter(_ => dist >= radius + node.radius)
    .fold(emptySet)(r => search(r, query, radius))

  left ++ right ++ (if (dist < radius) Set(node.obj) else emptySet)
}

该函数返回一个然后连接到其他集合的函数,而不是传递mutable.Set给每个search函数.如果要构建函数调用,看起来树的每个节点都在相互连接(假设它们在你的半径范围内).searchSet[TObject]

从效率的角度来看,这可能不如可变版本那么高效.使用a List而不是a Set可能会更好,然后你可以在完成时将final转换List为a Set(尽管可能不像可变版本那样快).

更新 要回答有关好处的问题:

1. 决定论 - 因为它是不可变的,所以当用相同的参数调用这个函数时,你总能得到相同的结果.话虽如此,你原来的版本应该是确定性的,你只是不知道还有谁在修改你的结果,尽管这可能不是什么大问题.
2. 难以阅读？ - 我认为这更多的是关于不同风格的编程的观点和经验问题.我发现您的版本难以阅读,因为您没有从函数返回任何值,并且您有多个if语句.我同意,首先Option/ filter/ fold看起来有点奇怪,但在你开始使用它们一段时间后(就像任何东西一样)它变得容易阅读.我会将其与能够在.NET中读取LINQ进行比较.
3. 性能 - 使用@ huynhjl的答案,List如果你的原始版本没有更好的性能,你应该得到平等.看起来你真的不需要使用Set哪个具有确保集合中的所有内容都是唯一的开销.
4. 垃圾收集 - 在纯功能版本中,您可以快速创建新对象并快速删除它们,这意味着它们很可能无法在GC的第一代中存活.这很重要,因为在代之间移动对象会导致GC暂停.在可变版本中,您传递的是对原始集合的引用,该集合会挂起更长时间并可能会压缩到下一代.这不是最好的例子,因为你的可变版本可能不是那么长寿,谁知道你想对返回对象做什么(可能会保留一段时间).在可变版本中,你很可能最终得到指向第二代对象的第二代集合,而不可变版本最终会有第一代集合指向第二代对象.清理不可变版本将更加快速和暂停(再次,这是对您的对象的使用和GC正在做什么做出一些广泛的假设和概括,您的里程可能会有所不同).
5. 并行性 - 功能版本可以轻松并行化,而可变版本则不能.根据树的大小,这可能不是一个大问题.

由于你似乎很感兴趣,我建议你阅读Scala中的Functional Programming.我认为这对于初学者来说是一个很好的方式,它涵盖了所有这些基础知识.

Answer 2

我想知道使用标准的 immutable 是否会获得良好的性能List。所有search操作都是一次检查一个节点，如果满足某些条件则追加当前元素，然后进行双重递归。所以你可以使用不可变的累加器：

def search(node: VPNode[TPoint, TObject], query: TPoint, radius: Double,
    acc: List[TObject] = Nil): List[TObject] = {

  val dist = distance(query, node.point)
  val mid = if (dist < radius) node.obj :: acc else acc

  val midLeft =
    if (node.left != null && dist <= radius + node.radius)
      search(node.left, query, radius, mid)
    else mid

  if (node.right != null && dist >= radius + node.radius)
    search(node.right, query, radius, midLeft)
  else midLeft
}  

据我所知，这仅前置于累加器的开头，并且应该很快。

请注意，我认为在内部使用可变集合并向调用者返回一个不可变集合是可以的：

def search(node: VPNode[TPoint, TObject], query: TPoint, radius: Double): Vector[TObject] = {
  import collection.immutable.{VectorBuilder => Builder}
  def rec(n: VPNode[TPoint, TObject], acc: Builder[TObject]): Builder[TObject] = {
    val dist = distance(query, node.point)
    val mid = if (dist < radius) acc += node.obj
    if (node.left != null && dist <= radius + node.radius) rec(node.left, acc)
    if (node.right != null && dist >= radius + node.radius) rec(node.right, acc)
    acc
  }
  rec(node, new Builder()).result
}