python - python有列表构造函数吗？

Question

python是否在OCaml(cons)(或lisp)中具有类似于::的列表构造函数，该构造函数接受head元素和tail列表，并返回新的列表head::tail？

我搜索了python列表构造函数，最终找到了有关__init__的其他信息。参见例如Creating a list in Python- something sneaky going on?

为了澄清，我正在寻找的是Python found in this question中以下列表分解的逆过程:

head, *tail = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

这给出了:

>>>head
1
>>> tail
[1, 2, 3, 5, 8, 13, 21, 34, 55]

我正在寻找一个列表构造函数，例如 cons或 ::这样

head :: tail  =>   original list

Answer 1

要回答您的问题，没有直接等同于通常在所谓的“功能”语言(lisp，OCaml，Haskell等)中发现的缺点的方法。

这是因为有两个相互竞争的模型来表示编程语言中的元素列表。

链表

您似乎熟悉的一个称为链表。

链表由cons单元组成，每个单元包含两个引用:

指向列表元素的第一个，称为头

另一个指向列表中的下一个cons单元，是尾部

由于列表很少是无限的，因此最后一个const单元通常会指向一个特殊值，即空列表，有时称为nil。

如果要将列表保存在变量中以备将来引用，则应保留对第一个cons单元的引用。

Here's a visual representation from Wikipedia。

在此模型中，必须通过创建新的cons单元格在前面添加元素来构造每个列表，指向该新元素作为其头部，并指向先前构造的子列表作为其尾部。这就是为什么cons运算符有时被称为列表构造函数的原因。

数组

这是命令式语言(例如Python)通常首选的模型。在此模型中，列表只是对内存范围的引用。

假设您像这样创建一个列表:

l = [1, 2, 3]

每当您创建列表时，Python都会为其分配一小部分内存来存储元素，并留有一些额外的空间，以防万一您以后想要添加元素。要存储它，您只需存储对第一个元素的引用以及对内存范围大小的引用，就像这样:

l  <-- your variable
|     ___ ___ ___ ___ ___ ___ ___ ___ ___
|->  |   |   |   |   |   |   |   |   |   |
     | 1 | 2 | 3 |   |   |   |   |   |   |
     |___|___|___|___|___|___|___|___|___|

如果决定在列表的末尾添加元素，则可以使用 append

l.append(4)

产生以下列表:

 ___ ___ ___ ___ ___ ___ ___ ___ ___
|   |   |   |   |   |   |   |   |   |
| 1 | 2 | 3 | 4 |   |   |   |   |   |
|___|___|___|___|___|___|___|___|___|

现在，假设您忘记了最初的0，现在希望将其添加到前面。您真的可以很好地使用insert方法(插入位置为0):

l.insert(0, 0)

但是列表的开头没有空格! Python别无选择，只能获取每个元素，并在直接右边的位置一次复制一个元素:

 ___ ___ ___ ___ ___ ___ ___ ___ ___
|   |   |   |   |   |   |   |   |   |
| 1 | 2 | 3 | 4 |   |   |   |   |   |
|___|___|___|___|___|___|___|___|___|
  |   |   |__ |___
  |   |___   |    |  First, Python has to copy the four elements
  |___    |  |    |  one space to the right 
 ___ _\/ _\/ \/_ _\/ ___ ___ ___ ___
|   |   |   |   |   |   |   |   |   |
|   | 1 | 2 | 3 | 4 |   |   |   |   |
|___|___|___|___|___|___|___|___|___|

Only then can it insert the 0 at the beginning

 ___ ___ ___ ___ ___ ___ ___ ___ ___
|   |   |   |   |   |   |   |   |   |
| 0 | 1 | 2 | 3 |   |   |   |   |   |
|___|___|___|___|___|___|___|___|___|

对于这么小的数组，它看起来似乎并不多，但是可以想象一下，您的数组更大，并且您重复此操作多次:您将花费大量时间来构建列表!

这就是为什么您找不到使用将数组用于数组的语言(例如Python)的列表构造函数的原因。

进一步跳水:为什么两种不同的型号？

您现在可能想知道为什么不同的语言会偏爱不同的列表模型，以及两种模型之一是否优越。

这是因为这两个数据结构在不同的上下文中具有不同的性能。两个例子:

在中间访问元素

假设您要获取列表的第五个元素。

在链接列表中，您需要获取:

第一个缺点单元格

然后是该单元格的尾部，以获取第二个元素

然后此单元格的尾部获得第三个元素

然后此单元格的尾部得到第四个元素

，最后是该单元格的尾部，以获取第五个元素

因此，您将必须阅读5个引用!

使用数组，这要简单得多:您知道第一个元素的引用。给定所有元素都在连续的内存范围内，您只需要访问右侧的引用4个点!

如果您需要多次访问非常大的列表中的随机元素，那么数组会更好。

在中间插入一个元素

假设您现在想在中间插入一个元素。

带有链表:

您可以找到与插入点之前的最后一个元素相对应的cons单元格。

创建一个新的cons单元格，其头部指向您要添加的元素，并且尾部与您刚刚找到的cons单元格相同。

您现在可以更改此单元格的尾部以指向新创建的单元格。

使用数组时，就像在中间添加元素时一样，您将需要将每个元素复制到插入点的右边，在右边留一个空格!

在这种情况下，这就是明显更好的链表。