10.2.2.1 添加元素到列表

到目前为止，我们已经看到如何追加元素到已有（函数式）列表的前面；如果我们想在列表的末尾追加元素，又该如何做呢？这要求听起来是合理的，那么，我们尝试实现它。清单 10.10 显示了在列表的前面和在后面插入na?ve 企图之间性能的差别。

清单10.10 在列表中添加元素(F# Interactive)

> let prepend el list = el::list;;     [1]

val prepend : ‘a -> ‘a list -> ‘alist

> let rec append el list =     [2]

     match listwith 

     | [] ->[el]     <-- 追加到空列表

     | x::xs ->x::(append el xs)     <-- 递归追加到其余部分

val append : ‘a -> ‘a list -> ‘a list

> #time;;     [3]

> let l = [ 1 .. 30000 ];; 

val l : int list

> for i = 1 to 100 do ignore(prepend 1l);;   |

Real: 00:00:00.000, CPU: 00:00:00.000    |

                                   | 追加的性能更慢

> for i = 1 to 100 do ignore(append 1l);;   |

Real: 00:00:00.434, CPU: 00:00:00.421    |

prepend 的实现非常简单[1]，因为可以使用 cons 运算符（::），直接构造新的列表单元；而追加元素到列表的末尾，则需要写递归函数[2]，遵循通常的递归列表处理模式，一个分支处理空列表，另一个处理 cons cell。

接下来，我们输入一个非常有用的 F# Interactive 命令，#time，打开记时器（timing）。在这种模式下，对我们输入的命令，F# 会自动输出执行所用的时间。可以看到，对于大型列表，在末尾追加元素要慢得多。我们在 for 循环中运行一百次，在前面追加所需的时间为零，但在后面追加元素，需要一个相当长的时间。任何“简单”的操作，那怕只需要半秒钟，迭代一百次都值得关注。

我们的追加函数不是尾递归，但在这里不是问题。尾递归能够避免堆栈溢出，但对性能的影响轻微。问题是函数式列表并不适合我们要尝试执行的操作。

图 10.5 显示了为什么这个操作对于函数式列表，不能有效地实现，而在前面追加元素却很容易。因为列表是不可变数据结构，我们可以创建一个单元，并指向原始列表。不可变性保证以后不会有人能改变原始列表，背着我们改变的是“新”列表的内容。与此相比，在后面追加元素，需要改变最后一个元素。以前，最后一个元素“知道”它自己在最后，而我们需要在它的后面有新的元素。列表是不可变的，所以，不能改变保存在最后元素中的信息。相反，必须克隆最后一个元素，这样，还要克隆前面的元素（这样，它就知道，后面跟着的是克隆最后一个元素），等等。

图 10.5 在前面追加元素，我们创建了新的 cons cell 和对原始列表的引用；在后面追加元素，需要遍历并克隆整个列表。

当然，有不同的数据结构，每一种数据结构都有不同的可以高效执行的操作。总要有一个权衡，这就是为什么对于不同的问题，选择正确的数据结构，是非常重要的。

算法的复杂性

计算机科学家使用非常精确的数学术语来讨论算法的复杂性，但这些术语背后的概念更重要的，即使当我们非正式使用时。在一般情况下，操作的复杂性告诉我们，算法需要的“原始”步骤数，依赖于输入的大小。它并不预测步骤数，只与输入的大小有关系。

让我们来分析一下前面的例子。追加一个元素到列表前面，总是涉及到一个单独的步骤：创建一个新的列表 cons cell。在正规表示法中，写成 O(1)，这意味着，步数是不变的，不管列表如何大。在有一百万个元素的列表的前面添加元素，与在只有一个元素的列表前面添加元素花费一样！

在列表的后面追加元素是棘手。开始的时候，如果列表中有 N 个元素，我们需要处理和重复 N 个 cons cell。这可写成 O(N)，表示步骤数大致与列表的大小是成正比：在有 1000 个元素的列表后面添加元素大约是为在有 1000 个元素的列表后面添加元素的两倍。

例如，如果我们想追加 M 个新元素列表中的，其复杂性应该乘以 M。这意味着，在前面追加将需要 O(M) 步，因为，1*M = M。使用类似的道理，追加到后面将需要 O(N * M) 步，这可能是一个更大的数量级。

到目前为止，我们已经讨论了函数式列表，在函数编程中是最重要的集合。让我们来一个大的飞跃，看一看在几乎所有命令式编程语言都存在的集合：不起眼的数组。F# 是一种 .NET 语言，所以，它也可以使用正常 .NET 数组。

10.2.2.1 添加元素到列表