在Python中，set()比list()更快吗？

Question

在Python中，set()比list()更快吗？

3

假设我有一个包含以空格分隔的不重复整数的输入。在这种情况下，使用下面的内容，

setA = set(input().split())

比下面这种方法快吗？如果是（我实际上就是这样经历过的），为什么呢？

listA = list(input().split())

请阅读输入时不要专注于没有到 int 的转换这一事实。

在我正在处理的一个问题中，使用 list() 会导致超时，但是通过使用 set()，我可以使它在时间限制内运行。我想知道这是为什么？

编辑：如果可能相关的话，以下是相关代码。

arr = input().split()

for ele in arr:

    if ele in setA:
        happiness += 1
    elif ele in setB:
        happiness += -1
    else:
        pass

当 arr 是一行用空格分隔的整数时，这次没有唯一性。

- muyustan

2

在 set 中成员检查需要 O(1) 的时间，而在 list 中需要 O(n) 的时间。 - Ch3steR

3

set 是使用 hashtables 实现的。为了检查成员身份，基本上只需要查看该对象是否位于由其哈希确定的位置即可，因此此操作的速度不取决于集合的大小。相反，对于列表来说，需要搜索整个列表，随着列表增长，这将变得更慢。 - Ch3steR

1

简单来说，由于哈希表的存在，Set更加优化以选择特定元素。 - Paritosh Yadav

1

很高兴能帮助到你 ;) - Ch3steR

这回答了你的问题吗？什么使得集合比列表更快？ - TheMaskedTitan

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paritosh Yadav · Accepted Answer

Python的集合类表示数学中的集合概念，即一个元素的集合，没有重复项，也没有固有顺序。与列表相比，使用集合的主要优势在于它具有高度优化的方法来检查特定元素是否包含在集合中。这基于一种名为哈希表的数据结构。

但是，由于算法基础，存在两个重要限制。第一个限制是集合不维护元素的任何特定顺序。第二个限制是只能将不可变类型的实例添加到Python集合中。因此，像整数、浮点数和字符字符串这样的对象可以成为集合的元素。可以维护一个元组集合，但不能维护列表或集合的集合，因为列表和集合是可变的。