我正在将一个算法从 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(虽然我认为我并不擅长它! )。
最佳答案
这是我认为更实用的方法:
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
当你完成时(虽然仍然可能没有可变版本那么快)。更新
回答您关于福利的问题:
Option
/filter
/fold
可能看起来有点奇怪,但是在您开始使用它们一段时间后(就像任何东西一样),它变得很容易阅读。我会将其与能够在 .NET 中读取 LINQ 进行比较。 List
如果不是更好的性能,您应该从原始版本获得相同的性能。看来你真的不需要使用 Set
它具有确保集合中的所有内容都是唯一的开销。 由于您似乎很感兴趣,我建议您阅读 Functional Programming in Scala .它涵盖了所有这些基础知识,我认为这对初学者来说是一种很好的方式。
关于scala - 在 Scala 中制作更多 "functional"代码以使用不可变集合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18283953/