列表与双端队列性能比较

作者

如果您至少使用 Python 编程一段时间，您必须知道什么是列表。它是整个Python编程中最常见的数据结构。但是，当您继续编码并学习新事物时，您就会了解时间复杂度。然后你想知道做任何事情需要多少时间。你继续检查一下。Python 中列表的内置功能非常强大。它使编程变得非常容易。但使用列表并不总是最好的主意。今天我们将比较 list 和 Python 中另一种常用的数据结构 – deque。

为什么我们需要将列表与双端队列进行比较？

列表是Python中最常用的数据结构。但该列表并不总是最佳选择。它确实有很多功能，但有时当我们编程时，我们可能会受到时间限制，因此我们必须确保选择最合适的选项。双端队列是Python中另一种具有很多功能的数据结构。因此，我们可以对它们进行比较，然后继续前进，无论哪种情况下结果最好，都可以使用。

如何比较列表和双端队列？

List 和 Deque 有点相似。它们都是线性数据结构并且是可变的。您可以在任意位置追加元素，也可以删除其中的任意元素。它们的性能取决于在某个位置添加或删除元素所需的时间。因此，我们将比较它们在开始、中间和结束时的追加时间和删除时间。

什么是列表？

列表是一种存储数据集合的数据结构。它源自最基本的数据结构数组。数组是相似数据类型的连续且具有传染性的数据集合。一般来说，我们将列表称为类似于数组，但它们两者是不同的。与数组不同，列表中的元素不必具有相同的数据类型。

1
2
num_list = [1,2,3,4,5,6,7,8,9,10]
print(num_list)

输出
[1,2,3,4,5,6,7,8,9,10]

什么是双端队列？

在了解什么是双端队列之前，首先我们必须了解什么是队列。队列是一种遵循 FIFO（先进先出）规则的数据结构。这意味着第一个进入队列的元素首先被取出。在队列中，插入是从前面进行的，删除是从后面进行的。双端队列只不过是一个允许从前面和后面删除和插入的队列。Python 没有内置的双端队列，但 Python 中有一个内置库，称为集合。集合中有双端队列，效率很高。

在本文中，我们将把集合库中的这个双端队列与列表进行比较。但首先，我们来看看如何在 Python 中使用 deque。

1
2
3
from collections import deque #importing deque from collections library
dq = deque([1,2,3,4,5]) # creating a deque
print(dq)

输出
deque([1, 2, 3, 4, 5])

大 O 表示法

展望未来，许多时间测量将使用大 O 表示法来完成。大O表示法是一种计算最坏情况下所需时间的相对方法。它不会为程序所花费的时间提供任何实际值，但可用于很好地了解所花费的相对时间。它采用计步方法。基本上，我们计算程序需要执行多少步才能完成。O(1) 是最佳时间复杂度，需要恒定的时间才能运行完成。

相关：了解有关时间复杂度的更多信息。

比较最后追加

理论上，在列表和双端队列的末尾添加一个元素必须花费恒定的时间，即O(1)。它们在末尾附加一个元素所花费的时间几乎相同。我们自己尝试一下吧。

1
2
3
4
5
6
7
8
9
10
11
12
from time import time #importing time function from module time
from collections import deque #importing deque from collections library
nums_list = [1,2,3,4,5] # creating a list
start = time()
nums_list.append(6) #appending 6 at the beginning of the list
end = time()
print("Time taken to append an element at beginning of the list:", end-start)
nums_deque = deque([1,2,3,4,5]) # creating a deque
start = time()
nums_deque.append(6) #appending 6 at the beginning of the deque
end = time()
print("Time taken to append an element at end of the deque:", end-start)
比较在列表和双端队列末尾追加的时间的代码和输出

在上面的代码中，首先，我们从 time 模块导入 time 函数来获取任意给定点的时间，然后从集合库中导入 deque。为了计算在列表中追加元素所需的时间，首先，我们用当前时间初始化一个名为 start 的变量。然后我们使用append 函数将6 添加到列表末尾。之后，我们将当前时间存储在 end 变量中。然后，我们通过从末尾减去起始位置来获得将元素追加到列表中所需的时间。然后我们对双端队列做了同样的事情。我们创建了一个双端队列，用当前的时间初始化start，在双端队列的末尾追加6，然后将当前的时间存储在end变量中。然后，从 end 中减去 start 就得到了在双端队列末尾追加元素所需的时间。

在列表末尾追加一个元素所需的时间为 2.07 x 10 -4，而当时追加一个元素的时间为 1.35 x 10 -4。

这种差异非常不显着。这只是意味着它们花费的时间几乎相同。这证明了一开始的观点，两者都必须花费 O(1) 的时间。

比较开头的追加

现在让我们检查一下在列表和双端队列的开头附加元素的运行时差异。对于列表，我们将使用 insert 函数，对于双端队列，我们​​将使用appendleft 函数。

1
2
3
4
5
6
7
8
9
10
11
12
from time import time #importing time function from module time
from collections import deque #importing deque from collections library
nums_list = [1,2,3,4,5] # creating a list
start = time()
nums_list.insert(0,0) #appending 0 at the beginning of the list
end = time()
print("Time taken to append an element at beginning of the list:", end-start)
nums_deque = deque([1,2,3,4,5]) # creating a deque
start = time()
nums_deque.appendleft(0) #appending 0 at the beginning of the deque
end = time()
print("Time taken to append an element at beginning of the deque:", end-start)
在列表和双端队列开头追加的代码和输出

所以这一次，我们首先从集合中导入时间和双端队列。然后我们使用 insert 函数在列表的开头附加 0，并使用appendleft 函数在双端队列的开头附加 0。就像前面的例子一样，我们创建了一个包含 5 个数字的列表，在开头插入 0 记下开始时间，记下结束时间，然后用结束时间减去开始时间即可得到所用时间。类似地，对于双端队列，我们​​创建了一个由 5 个数字组成的双端队列，记下开始时间，在开头插入 0，记下结束时间，然后用结尾减去开始时间即可得到所用时间。您可以看到运行时再次没有任何显着差异。但是，让我们用更大的列表和双端队列再试一次。

from time import time #importing time function from module time
from collections import deque #importing deque from collections library
nums_list = list(range(10**8)) # creating a list
start = time()
nums_list.insert(0,0) #appending 6 at the start of the list
end = time()
print("Time taken to append an element at the start of the list:", end-start)
nums_deque = deque(range(10**8)) # creating a deque
start = time()
nums_deque.appendleft(0) #appending 6 at the start of the deque
end = time()
print("Time taken to append an element at the start of the deque:", end-start)
在开头附加的代码和输出

哇！现在这是一个很大的区别。您可以看到，对于列表，运行时间达到 0.43 秒，对于双端队列，运行时间为 5.67 x 10 -5。list 是 deque 的 7.5k 倍。在这种情况下，我们确信双端队列比列表更好。这是因为对于列表来说，在开头追加一个元素需要 O(n) 时间，而对于双端队列来说，在开头追加一个元素需要 O(1) 时间。

比较中间的追加

1
2
3
4
5
6
7
8
9
10
11
12
13
from time import time #importing time function from module time
from collections import deque #importing deque from collections library
A_really_big_number=10**8
nums_list = list(range(A_really_big_number)) # creating a list
start = time()
nums_list.insert(A_really_big_number//2,0) #appending at the middle of the list
end = time()
print("Time taken to append an element at middle of the list:", end-start)
nums_deque = deque(range(A_really_big_number)) # creating a deque
start = time()
nums_deque.insert(A_really_big_number//2,0) #appending at the middle of the deque
end = time()
print("Time taken to append an element at middle of the deque:", end-start)
在双端队列和列表中间追加的代码和输出

我们再次做了同样的事情，但这一次，我们将元素附加到列表和双端队列的中间。在中间添加几乎需要很多时间，但几乎相等的时间。对于列表，在我们的例子中，双端队列的值为 0.28 和 0.35。最后，对于列表和双端队列来说，追加的时间复杂度都是 O(n)。

比较流行时间

从列表中弹出元素是另一个常见任务。让我们将其与在末尾和开头从队列中弹出元素进行比较。为此，我们将使用 pop 函数。

from time import time #importing time function from module time
from collections import deque #importing deque from collections library
 
A_really_big_number=10**8
nums_list = list(range(A_really_big_number)) # creating a list
nums_deque = deque(range(A_really_big_number)) # creating a deque
 
start = time()
nums_list.pop(0) #popping from the start of the list
end = time()
print("Time taken to append an element at the start of the list:", end-start)
 
start = time()
nums_deque.popleft() #popping from  the start of the deque
end = time()
print("Time taken to append an element at the start of the deque:", end-start)
 
start = time()
nums_list.pop() #popping from the end of the list
end = time()
print("\nTime taken to append an element at the end of the list:", end-start)
 
start = time()
nums_deque.pop() #popping from the end of the deque
end = time()
print("Time taken to append an element at the end of the deque:", end-start)
从双端队列和列表的开头和结尾弹出

pop 函数的统计数据几乎与append 函数类似。对于列表和双端队列来说，从末尾弹出一个元素所花费的时间非常少且几乎相同。但是，对于双端队列来说，从头开始弹出一个元素所需的时间要少得多，而对于列表来说，则需要花费大量的时间。因此，在双端队列中从头弹出比列表更好，并且从末尾弹出对于两者来说几乎相似。

复杂度表

追加功能

位置 列表 双端队列
开始 在） 复杂度(1)
中间 在） 在）
结尾 复杂度(1) 复杂度(1)

弹出功能

位置 列表 双端队列
开始 在） 复杂度(1)
中间 在） 在）
结尾 复杂度(1) 复杂度(1)

结论：双端队列和列表哪个更好？

正如我们刚才看到的，列表在开头追加或弹出起始元素比双端队列花费更多时间，其余时间几乎相同。两者都易于操作并且具有非常好的应用性。那么双端队列比列表更好吗？如果时间有限，最好使用双端队列。但双端队列缺乏功能。Python 中的列表通过其切片能力而变得重要。Deque没有切片属性。

因此，如果您不需要执行切片等复杂功能并且有时间限制，那么使用双端队列总是一个好主意。我们可以使用该列表来完成其余的工作。

这两种数据结构都非常强大，我们必须学习它们。了解何时使用哪个并继续练习。

参考

Python 官方文档

堆栈溢出