Python的len（）内置时间复杂度O（1）背后的秘密是什么[关闭]

Question

由于Python是用C实现的，我很困惑开发人员如何设法使Python内置的len函数在常量时间O（1）上的任何序列上运行，而C的字符串函数strlen以线性时间O（n）运行。

Python内置的len函数的时间复杂性背后的秘密是什么？如果我们用C编写程序，如果我们想要快速的C程序涉及序列长度，那么最好是复制Python的len代码吗？

Answer 1

我猜你错过了一个概念，即数据结构如何在恒定时间内返回其大小，即O（1）。

粗略地说，想想这样的程序：

void init(){
     // code to initialize (or allocate memory) the container 
     size = 0;
}
void add(Something something){
     container.add(something);
     size++;
}
void remove(Something something){
   //Code to search 'something'
   if(found) { 
    container.remove(something); 
    size--;
   }
}
int len(){
    return size;
}

现在，只要你调用方法len()，它就可以返回积分值而无需遍历container。

为什么strlen或任何C相关数据结构不能以这种方式工作是因为有一个像size这样的计数器的空间开销。但这并不意味着你无法定义一个。提示：使用struct并保持大小。

Answer 2

python中的任何字符串/列表都是一个对象。像许多对象一样，它有一个__len__方法，它存储列表的长度。当我们调用len时，__len__会在内部调用，并返回存储的值，这是一个O（1）操作。