6

我正在将一种算法从 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.，所以我开始研究它。似乎建议使用不可变集合几乎总是可以的：尽管我正在使用此代码进行数百万次查找，但在我看来，复制和连接结果数组会减慢它的速度。

例如，像这样的答案表明需要更“从功能上”解决问题。

那么，我应该怎么做才能以更 Scala 风格的方式解决这个问题呢？理想情况下，我希望它与 Java 版本一样快，但无论如何我都对解决方案感兴趣（并且总是可以分析它们以查看它是否有很大的不同）。

请注意，我才刚刚开始学习 Scala（我想我不妨在一些有用的东西上切齿）但我对函数式编程并不陌生，之前使用过 Haskell（尽管我不认为我很擅长它！ ）。

4

2 回答 2

5

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

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返回 aSet[TObject]然后将其连接到其他集合上。如果您要构建函数调用，看起来树的每个节点都相互连接（假设它们在您的半径内）。

从效率的角度来看，这可能不如可变版本高效。使用 aList而不是 aSet可能会更好，然后您可以在完成后将 final 转换List为 a Set（尽管仍然可能不如可变版本快）。

更新 要回答您有关福利的问题：

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

由于您似乎很感兴趣，我建议您阅读Scala 中的函数式编程。它涵盖了所有这些基础知识，我认为这是初学者的好方法。

于 2013-08-17T01:33:02.510 回答
3

我想知道您是否会通过使用标准 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
}
于 2013-08-17T06:57:12.137 回答