运行 "in" 使用 Python 搜索 "list" 和 "set" 的时间差
Run time difference for "in" searching through "list" and "set" using Python
我对list和set的理解Python主要是list允许重复，list允许有序信息，list有位置信息。我发现当我尝试搜索某个元素是否在列表中时，如果我先将列表转换为集合，运行时间会快得多。例如，我写了一段代码试图找到列表中最长的连续序列。以从0到10000的列表为例，最长连续为10001。使用列表时：
start_time = datetime.now()
nums = list(range(10000))
longest = 0
for number in nums:
if number - 1 not in nums:
length = 0
##Search if number + 1 also in the list##
while number + length in nums:
length += 1
longest = max(length, longest)
end_time = datetime.now()
timecost = 'Duration: {}'.format(end_time - start_time)
print(timecost)
上面代码的运行时间是“持续时间：0:00:01.481939”
仅添加一行以将列表转换为下面第三行中的设置：
start_time = datetime.now()
nums = list(range(10000))
nums = set(nums)
longest = 0
for number in nums:
if number - 1 not in nums:
length = 0
##Search if number + 1 also in the set(was a list)##
while number + length in nums:
length += 1
longest = max(length, longest)
end_time = datetime.now()
timecost = 'Duration: {}'.format(end_time - start_time)
print(timecost)
上述代码使用集合的 运行 时间现在是“持续时间：0:00:00.005138”，比搜索列表的时间短很多。谁能帮我理解其中的原因？谢谢！
这是一个很好的问题。
数组的问题在于，除了逐一比较每个元素之外，没有更智能的方法来搜索某个数组 a。
- 有时您会很幸运并在
a 的第一个元素上找到匹配项。
- 有时您会很不走运，直到
a 的最后一个元素才找到匹配项，或者可能 none 根本找不到匹配项。
- 平均而言，您每次必须搜索 they 数组的一半元素。
据说这具有 O(len(a)) 的“时间复杂度”，或者通俗地说，O(n)。这意味着算法（在数组中搜索一个值）所花费的时间与输入的大小（要搜索的数组中的元素数）成线性关系。这就是为什么它被称为“线性搜索”。哦，你的数组变大了 2 倍？好吧，您的搜索速度变慢了 2 倍。大 1000 倍？慢 1000 倍。
数组很棒，但它们用于搜索元素数量是否过高。
集合很聪明。在 Python 中，它们的实现就像是带有键但没有值的字典。像字典一样，它们由称为 hash table.
的数据结构支持
散列table 使用值的散列作为快速获取对象“摘要”的方法。这个“摘要”然后用于缩小搜索范围，因此它只需要线性搜索所有元素的一个非常小的子集。在哈希 table 中搜索时间复杂度 O(1)。请注意，其中没有“n”或 len(the_set)。这是因为在散列 table 中搜索所花费的时间不会随着散列 table 大小的增长而增长。所以据说它具有常数时间复杂度。
打个比方，当你在寻找牛奶时，你只会搜索奶制品岛。你知道牛奶（比如 isle）的哈希值是“dairy”而不是“deli”，所以你不必浪费任何时间搜索牛奶
一个自然的 follow-up 问题是“那我们为什么不总是使用集合呢？”。好吧，有一个 trade-off.
- 正如您所提到的，集合不能包含重复项，因此如果您想存储两个内容，可以是 non-starter。
- 在 Python 3.7 之前，它们也是无序的，所以如果你关心
元素的顺序，他们也不会这样做。 * 套装通常有一个
更大的 cpu/memory 开销，当使用许多包含少量元素的集合时，开销会增加。
- 还有可能
因为奇特的 CPU 特性（比如 CPU 缓存和分支
预测），通过小数组进行线性搜索实际上可以
比 hash-based look-up 更快。
我建议您进一步阅读数据结构和算法。这玩意相当language-independent。现在您知道 set 和 dict 在幕后使用哈希 Table，您可以查找涵盖任何语言的哈希 table 的资源，这应该会有所帮助.还有一些 Python-centric 资源，比如 https://www.interviewcake.com/concept/python/hash-map
我对list和set的理解Python主要是list允许重复，list允许有序信息，list有位置信息。我发现当我尝试搜索某个元素是否在列表中时，如果我先将列表转换为集合，运行时间会快得多。例如，我写了一段代码试图找到列表中最长的连续序列。以从0到10000的列表为例，最长连续为10001。使用列表时：
start_time = datetime.now()
nums = list(range(10000))
longest = 0
for number in nums:
if number - 1 not in nums:
length = 0
##Search if number + 1 also in the list##
while number + length in nums:
length += 1
longest = max(length, longest)
end_time = datetime.now()
timecost = 'Duration: {}'.format(end_time - start_time)
print(timecost)
上面代码的运行时间是“持续时间：0:00:01.481939” 仅添加一行以将列表转换为下面第三行中的设置：
start_time = datetime.now()
nums = list(range(10000))
nums = set(nums)
longest = 0
for number in nums:
if number - 1 not in nums:
length = 0
##Search if number + 1 also in the set(was a list)##
while number + length in nums:
length += 1
longest = max(length, longest)
end_time = datetime.now()
timecost = 'Duration: {}'.format(end_time - start_time)
print(timecost)
上述代码使用集合的 运行 时间现在是“持续时间：0:00:00.005138”，比搜索列表的时间短很多。谁能帮我理解其中的原因？谢谢！
这是一个很好的问题。
数组的问题在于，除了逐一比较每个元素之外，没有更智能的方法来搜索某个数组 a。
- 有时您会很幸运并在
a的第一个元素上找到匹配项。 - 有时您会很不走运，直到
a的最后一个元素才找到匹配项，或者可能 none 根本找不到匹配项。 - 平均而言，您每次必须搜索 they 数组的一半元素。
据说这具有 O(len(a)) 的“时间复杂度”，或者通俗地说，O(n)。这意味着算法（在数组中搜索一个值）所花费的时间与输入的大小（要搜索的数组中的元素数）成线性关系。这就是为什么它被称为“线性搜索”。哦，你的数组变大了 2 倍？好吧，您的搜索速度变慢了 2 倍。大 1000 倍？慢 1000 倍。
数组很棒，但它们用于搜索元素数量是否过高。
集合很聪明。在 Python 中，它们的实现就像是带有键但没有值的字典。像字典一样，它们由称为 hash table.
的数据结构支持散列table 使用值的散列作为快速获取对象“摘要”的方法。这个“摘要”然后用于缩小搜索范围，因此它只需要线性搜索所有元素的一个非常小的子集。在哈希 table 中搜索时间复杂度 O(1)。请注意，其中没有“n”或 len(the_set)。这是因为在散列 table 中搜索所花费的时间不会随着散列 table 大小的增长而增长。所以据说它具有常数时间复杂度。
打个比方，当你在寻找牛奶时，你只会搜索奶制品岛。你知道牛奶（比如 isle）的哈希值是“dairy”而不是“deli”，所以你不必浪费任何时间搜索牛奶
一个自然的 follow-up 问题是“那我们为什么不总是使用集合呢？”。好吧，有一个 trade-off.
- 正如您所提到的，集合不能包含重复项，因此如果您想存储两个内容，可以是 non-starter。
- 在 Python 3.7 之前，它们也是无序的，所以如果你关心 元素的顺序，他们也不会这样做。 * 套装通常有一个 更大的 cpu/memory 开销，当使用许多包含少量元素的集合时，开销会增加。
- 还有可能 因为奇特的 CPU 特性（比如 CPU 缓存和分支 预测），通过小数组进行线性搜索实际上可以 比 hash-based look-up 更快。
我建议您进一步阅读数据结构和算法。这玩意相当language-independent。现在您知道 set 和 dict 在幕后使用哈希 Table，您可以查找涵盖任何语言的哈希 table 的资源，这应该会有所帮助.还有一些 Python-centric 资源，比如 https://www.interviewcake.com/concept/python/hash-map