scala 为什么附加到列表不好？

Why is appending to a list bad?

提问by Travis Dixon

I've recently started learning scala, and I've come across the ::(cons) function, which prepends to a list.
In the book "Programming in Scala" it states that there is no append function because appending to a list has performance o(n) whereas prepending has a performance of o(1)

我最近开始学习 Scala，并且遇到了::(cons) 函数，它位于列表之前。
在“Scala 编程”一书中，它指出没有附加函数，因为附加到列表的性能为 o(n) 而前置的性能为 o(1)

Something just strikes me as wrong about that statement.

这句话让我觉得有些不对劲。

Isn't performance dependent on implementation? Isn't it possible to simply implement the list with both forward and backward links and store the first and last element in the container?

性能不是取决于实现吗？难道不能简单地用前向和后向链接实现列表并将第一个和最后一个元素存储在容器中吗？

The second question I suppose is what I'm supposed to do when I have a list, say 1,2,3 and I want to add 4 to the end of it?

我想的第二个问题是当我有一个列表时我应该做什么，比如 1,2,3 并且我想在它的末尾添加 4？

回答by sepp2k

The key is that x :: somelistdoes not mutate somelist, but instead creates a new list, which contains x followed by all elements of somelist. This can be done in O(1) time because you only need to set somelistas the successor of xin the newly created, singly linked list.

关键是x :: somelist它不会 mutate somelist，而是创建一个新列表，其中包含 x 后跟 的所有元素somelist。这可以在 O(1) 时间内完成，因为您只需要在新创建的单向链表中设置somelist为后继x。

If doubly linked lists were used instead, xwould also have to be set as the predecessor of somelist's head, which would modify somelist. So if we want to be able to do ::in O(1) without modifying the original list, we can only use singly linked lists.

如果改为使用双向链表，x还必须将其设置为somelist的头的前身，这将修改somelist. 所以如果我们想::在不修改原链表的情况下做到O(1)，我们只能使用单向链表。

Regarding the second question: You can use :::to concatenate a single-element list to the end of your list. This is an O(n) operation.

关于第二个问题：您可以使用:::将单元素列表连接到列表的末尾。这是一个 O(n) 操作。

List(1,2,3) ::: List(4)

回答by Chris Conway

Other answers have given good explanations for this phenomenon. If you are appending many items to a list in a subroutine, or if you are creating a list by appending elements, a functional idiom is to build up the list in reverse order, cons'ing the items on the frontof the list, then reverse it at the end. This gives you O(n) performance instead of O(n2).

其他答案对这种现象给出了很好的解释。如果您在子程序中将许多项附加到一个列表中，或者如果您通过附加元素来创建一个列表，则功能习惯用法是以相反的顺序构建列表，将列表前面的项放在一起，然后最后反转它。这为您提供 O(n) 性能而不是 O(n2)。

回答by Sarah G

Since the question was just updated, it's worth noting that things have changed here.

由于问题刚刚更新，值得注意的是这里的情况已经发生了变化。

In today's Scala, you can simply use xs :+ xto append an item at the end of any sequential collection. (There is also x +: xsto prepend. The mnemonic for many of Scala's 2.8+ collection operations is that the colon goes next to the collection.)

在今天的 Scala 中，您可以简单地使用xs :+ x在任何顺序集合的末尾附加一个项目。（还有x +: xs前面加上该助记符许多Scala的2.8+收集操作的是，在山坳上的信息放进旁边的山坳经文。）

This will be O(n) with the default linked implementation of Listor Seq, but if you use Vectoror IndexedSeq, this will be effectively constant time. Scala's Vectoris probably Scala's most useful list-like collection—unlike Java's Vectorwhich is mostly useless these days.

对于or的默认链接实现，这将是 O( n) ，但是如果您使用or ，这将是有效的恒定时间。Scala 的可能是 Scala 最有用的类似列表的集合——不像 Java 的，后者现在几乎没用了。ListSeqVectorIndexedSeqVectorVector

If you are working in Scala 2.8 or higher, the collections introductionis an absolute must read.

如果您使用 Scala 2.8 或更高版本，集合介绍绝对是必读的。

回答by skalb

Prepending is faster because it only requires two operations:

前置更快，因为它只需要两个操作：

1. Create the new list node
2. Have that new node point to the existing list

1. 创建新的列表节点
2. 让新节点指向现有列表

Appending requires more operations because you have to traverse to the end of the list since you only have a pointer to the head.

追加需要更多的操作，因为您必须遍历到列表的末尾，因为您只有一个指向头部的指针。

I've never programmed in Scala before, but you could try a List Buffer

我以前从未在 Scala 中编程过，但您可以尝试使用List Buffer

回答by Brian

Most functional languages prominently figure a singly-linked-list data structure, as it's a handy immutable collection type. When you say "list" in a functional language, that's typically what you mean (a singly-linked list, usually immutable). For such a type, append is O(n) whereas cons is O(1).

大多数函数式语言都突出显示了单链表数据结构，因为它是一种方便的不可变集合类型。当您在函数式语言中说“列表”时，这通常就是您的意思（单向链表，通常是不可变的）。对于这种类型，append 是 O(n) 而 cons 是 O(1)。