我对Python中list和set的理解主要是list允许重复，list允许有序信息，list有位置信息。我发现，当我试图搜索一个元素是否在列表中，如果我先将列表转换为集合，运行时间要快得多。例如，我编写了一个代码，试图找到列表中最长的连续序列。以0 ~ 10000为例，最长的连续为10001。当使用list时:
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)
以上代码的运行时间为"Duration: 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)
使用集合的上述代码的运行时间现在是&;Duration: 0:00:00.005138&;，比通过列表搜索要短得多。谁能帮我解释一下原因吗?谢谢你！
这个问题问得好。
数组的问题是，除了逐个比较每个元素之外，没有更聪明的方法来搜索数组a。
- 有时你会很幸运地在
a的第一个元素上得到匹配。 - 有时候你会很不幸，直到
a的最后一个元素才找到匹配，或者根本没有。 - 平均来说，你每次都要搜索数组中一半的元素。
这被称为具有"时间复杂度"。O(len(a))，俗称O(n)。这意味着算法(在数组中搜索值)所花费的时间与输入的大小(要搜索的数组中元素的数量)成线性比例。这就是为什么它被称为"线性搜索"。哦，你的数组变大了2倍?你的搜索速度变慢了2倍。1000 x更大?1000 x慢。
数组很好，但如果元素计数过高，它们就无法💩进行搜索。
集合是聪明的。在Python中，它们的实现就好像是一个只有键而没有值的Dictionary。像字典一样，它们由一个叫做哈希表的数据结构支持。
哈希表使用值的哈希值作为快速获取"摘要"的方法。一个物体的。这个"summary"然后用于缩小搜索范围，因此它只需要线性搜索所有元素的一个非常小的子集。在哈希表中进行搜索，时间复杂度为O(1)。注意没有"n"或者是len(the_set)。这是因为在哈希表中搜索所花费的时间不会随着哈希表大小的增长而增长。所以我们说它具有常数时间复杂度
通过类比，你只在寻找牛奶时搜索乳制品岛。你知道牛奶的哈希值(比如，它是isle)是&;dairy&;而不是"熟食"，所以你不必浪费任何时间寻找牛奶
一个自然的后续问题是"为什么我们不总是使用集合?"好吧，这是一种权衡。- 正如你所提到的，集合不能包含重复的，所以如果你想存储两个东西，这是不可能的。
- 在Python 3.7之前，它们也是无序的，所以如果你关心元素的顺序也不行。集合通常有一个更大的cpu/内存开销，当使用包含少量元素的许多集合时，这些开销会增加。
- 这也是有可能的这是因为奇特的CPU特性(如CPU缓存和分支)预测)，线性搜索通过小数组实际上可以比在集合中基于哈希的查找更快。
我建议你进一步阅读数据结构和算法。这些东西与语言无关。既然您知道set和dict在幕后使用哈希表，那么您可以查找涵盖任何语言哈希表的资源，这应该会有所帮助。也有一些以python为中心的资源，如https://www.interviewcake.com/concept/python/hash-map