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

问题描述

可以说我有一张图，并且想看看N [a] 中是否存在 b。



  a，b = range（2）
 N = [set（[ b]），set（[a，b]）] 
  

OR

  N = [[b]，[a，b]] 
  

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


解决方案

在一个集合中速度要快得多，特别是对于大集合。这是因为该集合使用散列函数映射到存储桶。由于Python实现会自动调整哈希表的大小，因此速度可以保持不变（ O（1） ）无论集合的大小如何（假设散列函数足够好）。



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

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])]

OR

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

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

解决方案

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).

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屋！