哪个更快，为什么?设置还是列表? [英] Which is faster and why? Set or List?

问题描述

假设我有一个图表，想看看 b in N[a].哪个实施速度更快?为什么?

Lets say that I have a graph and want to see if b in N[a]. Which is the faster implementation and why?

a, b = range(2)
N = [set([b]), set([a,b])]

或

N= [[b],[a,b]]

这显然过于简单化了，但想象一下图变得非常密集.

This is obviously oversimplified, but imagine that the graph becomes really dense.

推荐答案

集合中的成员测试速度要快得多，尤其是对于大型集合.这是因为该集合使用 哈希函数 来映射到存储桶.由于 Python 实现会自动调整哈希表的大小，因此速度可以保持不变 (O(1)) 无论集合的大小(假设哈希函数足够好).

Membership testing in a set is vastly faster, especially for large sets. That is because the set uses a hash function to map to a bucket. Since Python implementations automatically resize that hash table, the speed can be constant (O(1)) no matter the size of the set (assuming the hash function is sufficiently good).

相反，要评估一个对象是否是列表的成员，Python 必须比较每个成员是否相等，即测试是 O(n).

In contrast, to evaluate whether an object is a member of a list, Python has to compare every single member for equality, i.e. the test is O(n).

这篇关于哪个更快，为什么?设置还是列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！