gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-04 14:29:15 24 4
gpt4 key购买 nike

我正在将一个算法从 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可能会更好,然后你可以转换最终的 ListSet当你完成时(虽然仍然可能没有可变版本那么快)。

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

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

    关于scala - 在 Scala 中制作更多 "functional"代码以使用不可变集合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18283953/

    24 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com