在函数式编程中如何实现内存高效的非破坏性集合操作？

StackOverflow https://stackoverflow.com/questions/1993760

题

我试图弄清楚如何在函数式编程中实现对大型集合的非破坏性操作，即。如何更改或删除单个元素，而无需创建一个全新的集合，其中所有元素（甚至未修改的元素）都将在内存中复制。（即使原始集合将被垃圾收集，我预计此类集合的内存占用和总体性能会很糟糕。）

这是我到目前为止所取得的进展：

使用 F#，我想出了一个函数 insert 将列表分成两部分并在中间引入一个新元素，似乎没有克隆所有未更改的元素：

// return a list without its first n elements:
// (helper function)
let rec skip list n =
    if n = 0 then
        list
    else
        match list with
        | []    -> []
        | x::xs -> skip xs (n-1)

// return only the first n elements of a list:
// (helper function)
let rec take list n =
    if n = 0 then
        []
    else
        match list with
        | []    -> []
        | x::xs -> x::(take xs (n-1))

// insert a value into a list at the specified zero-based position:
let insert list position value =
    (take list position) @ [value] @ (skip list position)

然后，我使用 .NET 检查原始列表中的对象是否在新列表中“回收” Object.ReferenceEquals:

open System

let (===) x y =
    Object.ReferenceEquals(x, y)

let x = Some(42)
let L = [Some(0); x; Some(43)]
let M = Some(1) |> insert L 1

以下三个表达式的计算结果全部为 true, ，表示所引用的值 x 在列表中重复使用 L 和 M, ， IE。内存中只有该值的 1 个副本：

L.[1] === x
M.[2] === x
L.[1] === M.[2]

我的问题：

函数式编程语言通常会重用值而不是将它们克隆到新的内存位置，还是我只是幸运地使用了 F# 的行为？假设是前者，这就是在函数式编程中如何合理地实现集合的内存高效编辑吗？

（顺便提一句。：我知道关于 克里斯·冈崎的书 纯函数式数据结构, ，但还没有时间仔细阅读。）

有帮助吗？

解决方案

  

我试图找出如何   大非破坏性操作   收藏在实施   函数式编程，即。它是如何   可以改变或删除单   而无需创建一个元件   全新的集合，其中所有   元素，即使是未经修改的，   将在存储器被复制。

此页具有F＃几个描述和数据结构的实施方式。他们中的大多数来自Okasaki的纯功能性数据结构的，虽然AVL树是我自己的实现，因为它是不存在的书。

现在，既然你问，关于重复使用未经修改的节点，让我们来简单的二进制树：

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

let rec insert v = function
    | Node(l, x, r) as node ->
        if v < x then Node(insert v l, x, r)    // reuses x and r
        elif v > x then Node(l, x, insert v r)  // reuses x and l
        else node
    | Nil -> Node(Nil, v, Nil)

请注意，我们再使用我们的某些节点。比方说，我们先从这棵树：

当我们插入一个e成树，我们得到了一个全新的树，有的指着我们原来的树后面的节点：

如果我们没有给xs树的引用之上，然后将.NET垃圾收集任何节点没有活动的引用，特别是thed，g和f节点。

请注意，我们只修改节点的沿着我们插入的节点的路径。这是最不可变的数据结构，包括列表相当典型。所以，我们创建节点的数量精确地等于节点的数目，我们需要以插入到我们的数据结构遍历。

  

待办事项功能编程语言   通常再利用值，而不是   他们克隆到一个新的存储位置，   或者是我只是幸运，F＃的   行为？假如是前者，是   该如何合理的内存效率   藏品的编辑可   在功能的编程执行？

是

解释，然而，是不是一个很好的数据结构，因为对它们大多数非平凡操作需要O（n）的时间。

平衡二叉树支持O（log n）的插入物，这意味着我们在每个插入件创建O（log n）的拷贝。由于日志<子> 2 （10 ^ 15）〜= 50，开销是用于这些特定数据结构非常非常小。即使你以后插入/删除每个对象的每个副本保持周围，你的内存使用量将在澳的速度增长（N log n）的 - 非常合理的，在我看来

其他提示

它是如何可能改变或消除单元，而无需创建一个全新的集中的所有元素，甚至未经修饰的，将是重复记忆。

这是因为，无论什么样的收集， 指针 元素分开存储的元素自己。(例外：一些编译器将优化一些的时间，但他们知道他们在做什么。) 因此，例如，你可以有两个列表中的不同仅在第一个元件和分享tails:

let shared = ["two", "three", "four"]
let l      = "one" :: shared
let l'     = "1a"  :: shared

这两个列表有 shared 部分在共和他们的第一要素不同。什么是不太明显的是，各表还开始与一个独特的对，通常被称为"cons细胞":

  • 列表 l 开始有一对包含一个指向 "one" 和一个指向的共用的尾巴。

  • 列表 l' 开始有一对包含一个指向 "1a" 和一个指向的共用的尾巴。

如果我们只有宣布 l 想 修改或删除的第一个元素 得到 l', 我们这样做：

let l' = match l with
         | _ :: rest -> "1a" :: rest
         | []        ->  raise (Failure "cannot alter 1st elem of empty list")

有不断成本：

  • 分裂 l 进入其头部和尾部通过检查弊元。

  • 分配一个新缺点小指 "1a" 与该尾巴。

新的利弊的细胞变为值的列表 l'.

如果你做点像变化中的一个大集合，通常只能使用某种平衡树，它使用对数的时间和空间。少你可以使用更精密的数据结构：

  • 杰拉德休特的 拉链 可以定义为任何树类的数据结构和可用于横和使pointlike改进在不断的成本。拉链都很容易理解。

  • Paterson和Hinze的 指树 提供非常复杂的陈述的序列，其中除其他的技巧使你改变元素在中东有效地—但是他们难以理解。

虽然引用的对象是在代码是相同的， 我beleive为引用自己的存储空间 和列表的结构 由take复制。 作为结果，而引用的对象是相同的， 和尾部的两个列表之间共享 “细胞”的初始部分被复制。

我不是函数编程的专家， 但也许有某种树的，你可以实现 只的log（n）的元素的重复， 因为你将不得不重新仅从根路径 到插入的元件。

这听起来好像是你的问题主要是关于不可改变的数据的，而不是函数式语言的本身的。数据确实是纯功能性的代码一定不变（参见引用透明），但我不知道，到处都是强制绝对纯度（虽然哈斯克尔最接近，如果你喜欢，诸如此类的事情）任何非玩具语言。

粗略地讲，引用透明单元，其没有实际存在差异可变/表达和其持有的值之间/评估为。因为一块不可变的数据将（根据定义）永远不会变化，可以识别平凡与它的值，应该从具有相同值的任何其他数据无差别表现。

因此，通过选择在绘制具有相同值的数据的两片之间没有语义区别，我们没有理由曾经故意构建一个重复的值。所以，在明显的平等的情况下（例如，添加东西的清单，将它作为一个函数的参数，＆C），其中不变性保证是可能的语言通常会重用现有的参考，像你说的。

同样地，不可变的数据结构具有它们的结构（尽管不是其内容）的固有引用透明。假设所有包含的值也是不可变的，这意味着该结构件可以安全地在新的结构，以及重新使用。例如，一个缺点列表的尾部通常可以重复使用;在你的代码，我希望是：

(skip 1 L) === (skip 2 M)

...将也的是真实的。

重用并不总是可能的，虽然;你skip功能删除列表的起始部分不能真正被重用，例如。出于同样的原因，附加的东西一个缺点列表的末尾是昂贵的操作，因为它必须重建一个全新的列表，类似于用串联空终止字符串的问题。

在这种情况下，天真的方式迅速进入的你关心可怕的表现领域。通常情况下，有必要重新考虑大幅基本算法和数据结构，以他们成功地适应不可改变的数据。技术包括断裂结构为层状或分层件分离的变化，反转结构的部分暴露便宜更新频繁修改的部分，甚至是存储原始结构一起更新的收集和更新与原来的飞行组合只当数据被访问。

由于你在这里使用F＃我要假设你至少有点熟悉C＃;不可估量埃里克利珀有职位摆的不可变数据结构在C＃中，可能会启发你远远超出了我可以提供。在几个职位的过程中，他展示了（相当有效）堆栈，二叉树和双端队列等等不可改变的实现。愉快的读数为任何.NET编程！

您可能对函数式编程语言中表达式的缩减策略感兴趣。关于这个主题的一本好书是 函数式编程语言的实现, ，作者：Simon Peyton Jones，Haskell 的创建者之一。特别是看下面的章节 Lambda 表达式的图简化 因为它描述了公共子表达式的共享。希望它有帮助，但恐怕它只适用于惰性语言。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top