我注意到,在Haskell和OCaml等函数式语言中,您可以使用列表执行两个操作。首先,你可以做x:xs,其中x是一个元素,xs是一个列表,结果是我们得到了一个新的列表,其中x在固定时间内附加到xs的开头。第二个是x++y,其中x和y都是列表,结果是我们得到了一个新的列表,其中y按照x中元素的数量以线性时间附加到x的末尾。现在我不是语言设计和编译器构建方面的专家,但在我看来,这很像是一个简单的链表实现,只有一个指针指向第一项。如果我要用像C++这样的语言实现这个数据结构,我会发现添加一个指向最后一个元素的指针通常很简单。在这种情况下,如果这些语言是以这种方式实现的(假设它们确实使用了所述的链表),则向最后一项添加“指针”将使将项添加到列表末尾变得更加有效,并允许与最后一个元素进行模式匹配。
我的问题是,这些数据结构真的是作为链表实现的吗?如果是,为什么它们不添加对最后一个元素的引用?
发布于 2011-04-07 11:43:20
是的,它们确实是链表。但它们是不可变的。不变性的优点是,您不必担心还有谁拥有指向相同列表的指针。您可以选择编写x++y,但程序中的其他部分可能依赖于x保持不变。
从事这类语言编译器工作的人(我就是其中之一)不会担心这个成本,因为有很多其他的数据结构可以提供有效的访问:
put和get操作提供了摊销的恒定时间。DList.)如果你对这类问题感兴趣,你可以从Chris Okasaki的书《纯函数式数据结构》和Ralf Hinze的一些不那么吓人的论文中获得有用的信息。
发布于 2011-04-07 05:09:11
你说过:
第二个是x++y,其中x和y都是列表,结果是y被附加到x的末尾,相对于x中元素的数量是线性的。
这在像Haskell这样的函数式语言中并非如此;y被附加到x的副本上,因为任何保持x的东西都依赖于它不变。
如果你打算复制所有的x,那么保留它的最后一个节点并不能给你带来任何好处。
发布于 2011-04-07 05:12:32
是的,它们是链表。在像Haskell和OCaml这样的语言中,你不会将项目添加到列表的末尾,句号。列表是不可变的。有一个创建新列表的操作- cons,您前面提到的:操作符。它接受一个元素和一个列表,并创建一个新的列表,其中元素作为头部,列表作为尾部。x++y占用线性时间的原因是,它必须将x的最后一个元素与y相联,然后将x的倒数第二个元素与该列表相联,以此类推,与x的每个元素相联。x中的任何cons单元格都不能重用,因为这会导致原始列表也发生变化。指向x的最后一个元素的指针在这里不是很有用-我们仍然需要遍历整个列表。
https://stackoverflow.com/questions/5572876
复制相似问题