len() 在集合和列表方面的复杂性
Complexity of len() with regard to sets and lists
关于集合和列表，len() 的复杂度同样为 O(1)。为什么处理集要花更多时间？
~$ python -m timeit "a=[1,2,3,4,5,6,7,8,9,10];len(a)"
10000000 loops, best of 3: 0.168 usec per loop
~$ python -m timeit "a={1,2,3,4,5,6,7,8,9,10};len(a)"
1000000 loops, best of 3: 0.375 usec per loop
它是否与特定的基准相关，例如，构建集合比列表花费更多的时间并且基准也考虑了这一点？
如果创建集合对象比创建列表花费更多时间，根本原因是什么？
是的，你是对的，更多的是因为 python 创建 set 和 list 对象所需的时间不同。作为更公平的基准，您可以使用 timeit 模块并使用 setup 参数传递对象：
from timeit import timeit
print '1st: ' ,timeit(stmt="len(a)", number=1000000,setup="a=set([1,2,3]*1000)")
print '2nd : ',timeit(stmt="len(a)", number=1000000,setup="a=[1,2,3]*1000")
结果：
1st: 0.04927110672
2nd : 0.0530669689178
如果您想知道为什么会这样，让我们进入 python 世界。实际上设置对象使用 hash table 和散列 table 使用散列函数来创建项目的散列值并将它们映射到值，在这个交易中调用函数并计算散列值和一些另一个额外的任务将花费很多时间。虽然创建列表 python 只需创建一系列对象，您可以通过索引访问它们。
您可以从 Cpython source code 查看有关 set_lookkey 函数的更多详细信息。
另请注意，如果两个算法具有相同的复杂度，并不意味着两个算法具有完全相同的 运行 时间或执行速度。1
因为 big O 符号描述了 limiting behavior of a function 并且没有显示确切的复杂性方程。
例如，以下等式 f(x)=100000x+1 和 f(x)=4x+20 的复杂度为 O(1)
这意味着两者都是线性方程，但正如您所见，第一个函数的斜率要大得多，对于相同的输入，它们会给出不同的结果。
删除 len(a) 语句。结果几乎相同。需要对集合进行哈希处理以仅保留不同的项目，因此速度较慢。
相关行是http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup#l640
640 static Py_ssize_t
641 set_len(PyObject *so)
642 {
643 return ((PySetObject *)so)->used;
644 }
和http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup#l431
431 static Py_ssize_t
432 list_length(PyListObject *a)
433 {
434 return Py_SIZE(a);
435 }
两者都只是静态查找。
所以你可能会问有什么区别。您也测量对象的创建。而且创建集合比创建列表更耗时。
首先，你没有测过len()的速度，你测过创建list/set的速度 连同速度len().
使用timeit的--setup参数：
$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "len(a)"
10000000 loops, best of 3: 0.0369 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "len(a)"
10000000 loops, best of 3: 0.0372 usec per loop
您传递给 --setup 的语句是 运行 在测量 len() 的速度之前。
其次， 你应该注意到 len(a) 是一个非常快速的陈述。测量其速度的过程可能会受到"noise"的影响。考虑 the code executed (and measured) by timeit 等同于以下内容：
for i in itertools.repeat(None, number):
len(a)
因为len(a)和itertools.repeat(...).__next__()都是快速操作，它们的速度可能相似，itertools.repeat(...).__next__()的速度可能会影响计时。
出于这个原因，您最好测量 len(a); len(a); ...; len(a)（重复 100 次左右），以便 for 循环的主体比迭代器花费更多的时间：
$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.2 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.3 usec per loop
（结果还是说len()在列表和集合上的表现一样，但是现在你确定结果是正确的。）
第三， "complexity" 和 "speed" 确实是相关的，但我相信你在制造一些混淆。 len() 对于列表和集合具有 O(1) 的复杂性这一事实并不意味着它必须 运行 在列表和集合上具有相同的速度。
表示，平均而言，无论列表a有多长，len(a)执行的渐近步数相同。并且无论集合b有多长，len(b)执行相同的渐近步数。但是list和set的计算大小的算法可能不同，导致性能不同（timeit显示不是这样，不过也有可能）
最后，
If the creation of a set object takes more time compared to creating a list, what would be the underlying reason?
集合，如你所知，不允许有重复的元素。 CPython 中的集合被实现为散列 tables（以确保平均 O(1) 插入和查找）：构造和维护散列 table 要复杂得多而不是向列表中添加元素。
具体来说，在构建集合时，您必须计算散列、构建散列table、查找它以避免插入重复事件等。相比之下，CPython 中的列表被实现为一个简单的指针数组，根据需要 malloc()ed 和 realloc()ed。
将此与 -s 标志一起使用以在 不考虑第一个字符串的情况下 计时：
~$ python -mtimeit -s "a=range(1000);" "len(a)"
10000000 loops, best of 3: 0.0424 usec per loop
↑
~$ python -mtimeit -s "a={i for i in range(1000)};" "len(a)"
10000000 loops, best of 3: 0.0423 usec per loop
↑
现在只考虑 len 函数，结果几乎相同，因为我们没有考虑 set/list.
的创建时间
让我在这里综合出色的答案：O(1) 仅告诉您关于输入大小的 order of growth。
O(1) 仅表示 恒定时间 相对于输入大小 。
一个方法对于任何输入可能总是需要 0.1 秒，而另一个方法对于任何输入可能需要 1000 年，它们都是 O(1)
在这种情况下，虽然文档 存在一定程度的歧义 ，这意味着该方法大约需要 相同的时间来处理大小为 1 因为它需要处理大小列表 1000；类似地，处理大小为 1 的字典所花费的时间与处理大小为 1000.
的字典所花费的时间相同
不保证针对不同的数据类型。
这不足为奇，因为 len() 在调用堆栈下方的某个点的实施可能因数据类型而异。
顺便说一句，静态类型语言消除了这种歧义，其中 ClassA.size() 和 ClassB.size() 是两种不同的方法。
许多人注意到 O(1) 不是关于不同 数据类型 的性能，而是关于不同 输入大小 [=19] 的性能=].
如果你想测试 O(1)-ness，你会寻找更像
的东西
~$python -m timeit --setup "a=list(range(1000000))" "len(a)"
10000000 loops, best of 3: 0.198 usec per loop
~$python -m timeit --setup "a=list(range(1))" "len(a)"
10000000 loops, best of 3: 0.156 usec per loop
大数据或小数据，所花费的时间都差不多。根据其他帖子，这将设置时间与测试时间分开，但并没有减少 len-time 与 loop-time 的噪音。
关于集合和列表，len() 的复杂度同样为 O(1)。为什么处理集要花更多时间？
~$ python -m timeit "a=[1,2,3,4,5,6,7,8,9,10];len(a)"
10000000 loops, best of 3: 0.168 usec per loop
~$ python -m timeit "a={1,2,3,4,5,6,7,8,9,10};len(a)"
1000000 loops, best of 3: 0.375 usec per loop
它是否与特定的基准相关，例如，构建集合比列表花费更多的时间并且基准也考虑了这一点？
如果创建集合对象比创建列表花费更多时间，根本原因是什么？
是的，你是对的，更多的是因为 python 创建 set 和 list 对象所需的时间不同。作为更公平的基准，您可以使用 timeit 模块并使用 setup 参数传递对象：
from timeit import timeit
print '1st: ' ,timeit(stmt="len(a)", number=1000000,setup="a=set([1,2,3]*1000)")
print '2nd : ',timeit(stmt="len(a)", number=1000000,setup="a=[1,2,3]*1000")
结果：
1st: 0.04927110672
2nd : 0.0530669689178
如果您想知道为什么会这样，让我们进入 python 世界。实际上设置对象使用 hash table 和散列 table 使用散列函数来创建项目的散列值并将它们映射到值，在这个交易中调用函数并计算散列值和一些另一个额外的任务将花费很多时间。虽然创建列表 python 只需创建一系列对象，您可以通过索引访问它们。
您可以从 Cpython source code 查看有关 set_lookkey 函数的更多详细信息。
另请注意，如果两个算法具有相同的复杂度，并不意味着两个算法具有完全相同的 运行 时间或执行速度。1
因为 big O 符号描述了 limiting behavior of a function 并且没有显示确切的复杂性方程。
例如，以下等式 f(x)=100000x+1 和 f(x)=4x+20 的复杂度为 O(1)
这意味着两者都是线性方程，但正如您所见，第一个函数的斜率要大得多，对于相同的输入，它们会给出不同的结果。
删除 len(a) 语句。结果几乎相同。需要对集合进行哈希处理以仅保留不同的项目，因此速度较慢。
相关行是http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup#l640
640 static Py_ssize_t
641 set_len(PyObject *so)
642 {
643 return ((PySetObject *)so)->used;
644 }
和http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup#l431
431 static Py_ssize_t
432 list_length(PyListObject *a)
433 {
434 return Py_SIZE(a);
435 }
两者都只是静态查找。
所以你可能会问有什么区别。您也测量对象的创建。而且创建集合比创建列表更耗时。
首先，你没有测过len()的速度，你测过创建list/set的速度 连同速度len().
使用timeit的--setup参数：
$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "len(a)"
10000000 loops, best of 3: 0.0369 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "len(a)"
10000000 loops, best of 3: 0.0372 usec per loop
您传递给 --setup 的语句是 运行 在测量 len() 的速度之前。
其次， 你应该注意到 len(a) 是一个非常快速的陈述。测量其速度的过程可能会受到"noise"的影响。考虑 the code executed (and measured) by timeit 等同于以下内容：
for i in itertools.repeat(None, number):
len(a)
因为len(a)和itertools.repeat(...).__next__()都是快速操作，它们的速度可能相似，itertools.repeat(...).__next__()的速度可能会影响计时。
出于这个原因，您最好测量 len(a); len(a); ...; len(a)（重复 100 次左右），以便 for 循环的主体比迭代器花费更多的时间：
$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.2 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.3 usec per loop
（结果还是说len()在列表和集合上的表现一样，但是现在你确定结果是正确的。）
第三， "complexity" 和 "speed" 确实是相关的，但我相信你在制造一些混淆。 len() 对于列表和集合具有 O(1) 的复杂性这一事实并不意味着它必须 运行 在列表和集合上具有相同的速度。
表示，平均而言，无论列表a有多长，len(a)执行的渐近步数相同。并且无论集合b有多长，len(b)执行相同的渐近步数。但是list和set的计算大小的算法可能不同，导致性能不同（timeit显示不是这样，不过也有可能）
最后，
If the creation of a set object takes more time compared to creating a list, what would be the underlying reason?
集合，如你所知，不允许有重复的元素。 CPython 中的集合被实现为散列 tables（以确保平均 O(1) 插入和查找）：构造和维护散列 table 要复杂得多而不是向列表中添加元素。
具体来说，在构建集合时，您必须计算散列、构建散列table、查找它以避免插入重复事件等。相比之下，CPython 中的列表被实现为一个简单的指针数组，根据需要 malloc()ed 和 realloc()ed。
将此与 -s 标志一起使用以在 不考虑第一个字符串的情况下 计时：
~$ python -mtimeit -s "a=range(1000);" "len(a)"
10000000 loops, best of 3: 0.0424 usec per loop
↑
~$ python -mtimeit -s "a={i for i in range(1000)};" "len(a)"
10000000 loops, best of 3: 0.0423 usec per loop
↑
现在只考虑 len 函数，结果几乎相同，因为我们没有考虑 set/list.
让我在这里综合出色的答案：O(1) 仅告诉您关于输入大小的 order of growth。
O(1) 仅表示 恒定时间 相对于输入大小 。
一个方法对于任何输入可能总是需要 0.1 秒，而另一个方法对于任何输入可能需要 1000 年，它们都是 O(1)
在这种情况下，虽然文档 存在一定程度的歧义 ，这意味着该方法大约需要 相同的时间来处理大小为 1 因为它需要处理大小列表 1000；类似地，处理大小为 1 的字典所花费的时间与处理大小为 1000.
不保证针对不同的数据类型。
这不足为奇，因为 len() 在调用堆栈下方的某个点的实施可能因数据类型而异。
顺便说一句，静态类型语言消除了这种歧义，其中 ClassA.size() 和 ClassB.size() 是两种不同的方法。
许多人注意到 O(1) 不是关于不同 数据类型 的性能，而是关于不同 输入大小 [=19] 的性能=].
如果你想测试 O(1)-ness，你会寻找更像
的东西~$python -m timeit --setup "a=list(range(1000000))" "len(a)"
10000000 loops, best of 3: 0.198 usec per loop
~$python -m timeit --setup "a=list(range(1))" "len(a)"
10000000 loops, best of 3: 0.156 usec per loop
大数据或小数据，所花费的时间都差不多。根据其他帖子，这将设置时间与测试时间分开，但并没有减少 len-time 与 loop-time 的噪音。