scala - 在 Scala 中制作更多 "functional"代码以使用不可变集合

Question

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

在 Java 中，我向函数传递了一个数组列表，它在其中累积结果，可能会向下递归其中一个或两个子树。这是进入 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. 有点烦人。一直以来，所以我开始研究它。似乎建议使用不可变集合几乎总是好的:尽管我使用此代码进行数百万次查找，但在我看来，复制和连接结果数组会减慢它的速度。

类似 this 的答案例如，建议需要更“功能性地”解决问题。

那么，我应该怎么做才能以更 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函数， search函数返回 Set[TObject]然后它连接到其他集合。如果您要构建函数调用，看起来树的每个节点都在相互连接(假设它们在您的半径内)。

从效率的角度来看，这可能不如可变版本有效。使用 List而不是 Set可能会更好，然后你可以转换最终的 List到 Set当你完成时(虽然仍然可能没有可变版本那么快)。

更新
回答您关于福利的问题:

确定性 - 由于它是不可变的，因此在使用相同的参数调用此函数时，您始终可以保证获得相同的结果。话虽如此，您的原始版本应该是确定性的，您只是不知道还有谁在修改您的结果，尽管这可能不是什么大问题。

难读？ - 我认为这更多是不同编程风格的意见和经验问题。我发现你的版本很难阅读，因为你没有从函数返回任何值，而且你有多个 if 语句。我同意一开始 Option/filter/fold可能看起来有点奇怪，但是在您开始使用它们一段时间后(就像任何东西一样)，它变得很容易阅读。我会将其与能够在 .NET 中读取 LINQ 进行比较。

性能 - 使用@huynhjl 的回答 List如果不是更好的性能，您应该从原始版本获得相同的性能。看来你真的不需要使用 Set它具有确保集合中的所有内容都是唯一的开销。

垃圾收集 - 在纯函数版本中，您会快速创建新对象并快速删除它们，这意味着它们很可能无法在 GC 的第一代之后继续存在。这很重要，因为在代之间移动对象是强制 GC 暂停的原因。在可变版本中，您传递对原始集合的引用，该集合会停留更长时间，并且可能会压缩到下一代。这并不是最好的例子，因为你的可变版本可能没有那么长，而且谁知道你想用返回对象做什么(也许保留一段时间)。在可变版本中，您很可能最终会得到指向第二代对象的第二代集合，而在不可变版本中，您最终会得到指向第二代对象的第一代集合。清理不可变版本将更快且无暂停(同样，这是对您的对象的使用以及 GC 正在做什么做出一些广泛的假设和概括，您的里程可能会有所不同)。

并行性 - 函数版本可以很容易地并行化，而可变版本则不能。根据您的树的大小，这可能不是什么大问题。

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