Python 集合比列表快得多，对吗？
原文：towardsdatascience.com/python-set-is-way-faster-than-list-true-or-false-042c6f8975cd由作者在 Canva 中创建
几周前，我写了一篇另一篇文章来解释一些流行的“Python 小技巧”背后的机制和逻辑。其中之一是在可能的情况下使用 Python 集合而不是列表。
许多文章告诉你 Python 小技巧，但很少告诉你为什么
在这篇文章变得流行之后，许多读者向我提问或争论说 Python 集合并不总是很快。这是绝对正确的。因此，我决定写这篇文章，深入探讨 Python 列表和集合的数据结构。
在这篇文章中，我将首先使用实际代码在不同场景下比较 Python 列表和集合的性能。然后，我将介绍它们使用的几种数据结构，即动态数组和哈希表。基于这些数据结构的特性，我将解释为什么 Python 列表或集合在某些场景下具有更好的性能。
1. 性能
由作者在 Canva 中创建
让我们从性能实验开始。不能说 Python 集合的性能总是比 Python 列表高。我们需要考虑不同的场景，例如创建、查找、追加和删除。
使用 Jupyter Notebook 进行这项测试要方便得多。因此，我们可以使用 %timeit 魔法命令来轻松评估经过的时间。
创建 – 列表胜出（快 2 倍）
要测试创建性能，我们可以简单地使用 range(10000) 来生成 10,000 个数字。请注意，这是一个生成器，但我们可以从这个生成器创建一个列表或一个集合。
# Create list for 100 times%timeit -n 100 my_list =list(range(10000))# Create set for 100 times%timeit -n 100 my_set =set(range(10000))可以看到，创建集合所需的时间大约是创建列表的两倍。这是因为集合的数据结构比列表消耗更多的时间和空间。这一点将在下一节中讨论。
查找 – 集合胜出（快 1000 倍）
在我们能够测试查找性能和后续测试用例之前，我们需要正确地创建一个列表和一个集合。除此之外，我们还需要一些数字用于测试目的。例如，我们需要一个数字用于在列表和集合中查找。让我们生成 1,000 个这样的数字，这应该足够了。
import random # Creat a list and a set my_list =list(range(10000)) my_set =set(my_list)# Random 1000 numbers for testing purpose test_numbers = random.sample(range(10000),1000)现在，我们可以使用以下代码在 Jupyter Notebook 中测试查找性能。
%timeit -n 100for num in test_numbers: num in my_list %timeit -n 100for num in test_numbers: num in my_set 由于 1ms = 1000μs，Python 集合的查找性能比 Python 列表快 1000 倍。
追加 – 列表胜出（快 0.2 倍）
现在，让我们测试追加。我们需要另一个测试数字数据集，因为我们的集合是从 1 到 10,000 的数字创建的。我们当前的测试数字是从同一范围内随机选择的，用于测试查找性能。然而，我们需要测试范围之外的数字。否则，我们对集合没有影响，因为我们不能在集合中追加重复的项。
# Random 1000 numbers from 10,000 to avoid duplicates in the set test_numbers = random.sample(range(10000,20000),1000)# Insertion into list%timeit -n 100for num in test_numbers: my_list_copy.append(num)# Insertion into set%timeit -n 100for num in test_numbers: my_set_copy.add(num)这次列表赢了，但不是很多，只快了 0.2 倍。可以说性能即将相同。
删除 – 集合胜出（快 800 倍）
要测试删除性能，我们需要我们的原始测试数字，因为我们需要删除在列表和集合中存在的数字。
# Create the test numbers again test_numbers = random.sample(range(10000),1000)# Deletion from list%timeit -n 100for num in test_numbers: my_list.remove(num)if num in my_list elseNone# Deletion from set%timeit -n 100for num in test_numbers: my_set.discard(num)这次 Python 集合再次获胜，大约快 800 倍。这是因为删除操作与查找有点相似。数字需要在列表或集合中找到，然后才能删除。
然而，集合的性能并不像查找那样快，查找的速度快了 1000 倍。原因是从列表中删除一个项比从集合中删除要容易一些。
现在，我们已经清楚不同场景下的性能比较。让我们谈谈原因。
由作者在 Canva 中创建
2. 列表与集合 – 数据结构比较
由作者在 Canva 中创建
Python 列表和集合的数据结构是动态数组和哈希表。它们之间的差异导致了性能比较的结果。
对于其余的比较，尽管它们是动态数组和哈希表之间的比较，我仍然会使用 Python 列表和 Python 集合来使其简单且具有上下文。
2.1 结构
Python 列表利用连续的内存块。Python 列表中的项是相邻存储的。因此，它的结构非常紧凑和有效。
值得注意的是，列表的索引不需要显式存储。相反，当我们使用索引访问列表中的项时，索引将用作输入来计算内存位置。一个简单的例子是，如果我们需要访问第 5 个项，内存位置将是 _5 * item_length_inbytes。
Python 集合将为所有其项创建一个哈希表。所有项都将有哈希键，这些键将使用特定的哈希函数计算得出。
作者创建的图片
因此，当我们从集合中查找特定项时，哈希函数可以帮助使用哈希函数将项转换为键，然后使用键直接在 O(1)时间内找到该项。
查找和删除性能
这就是为什么在集合中查找一个项目比在列表中查找要快得多。同样，要删除一个项目，主要动作是定位该项目。因此，在集合中删除一个项目的性能也比列表要快得多。
创建性能
也因为结构的原因，构建哈希表比分配一块连续内存要昂贵。因此，创建列表的性能略快。
2.2 调整大小
当一个Python 列表增长时，需要分配一个新的内存块，并且一些内部指针需要更新，但通常这不是一个昂贵的操作。
当一个Python 集合增长时，所有现有的项目都需要重新哈希。这意味着“字典”需要被重建。
追加性能
这就是为什么在列表中追加或插入项目比在集合中要快一点。因为重新哈希通常需要更多时间，尤其是在有大量项目的情况下。
摘要
由作者在 Canva 中创建
在这篇文章中，我们比较了 Python 列表和集合在不同场景下的性能。我们已经看到，在某些场景中，Python 列表甚至可以比 Python 集合更快。然而，需要强调的是，当 Python 集合的性能更好时，它通常要快数千倍，而反过来，Python 列表在其他场景中只能稍微快一点。
希望这篇文章能够满足您的一些好奇心，并帮助您在编码时做出决定！
