[CPyUG] python中len()是如何实现的？
gauss
请len()这个函数是如何实现的，不知道效率高不高？
或者说， 怎么查看python中类似len()这种函数的源码？
Best Regards,
张晓润
Sun Yat-sen University
Xunzhen Quan
--
邮件来自: `CPyUG`华蟒用户组(中文Python技术邮件列表)
规则: http://code.google.com/p/cpyug/wiki/PythonCn
发言: pyth...@googlegroups.com
退订: python-cn+...@googlegroups.com (向此发空信即退!)
详情: http://code.google.com/p/cpyug/wiki/CpyUg
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Leo Jay
>
> Hi 各位大牛,
> 请len()这个函数是如何实现的，不知道效率高不高？
> 或者说， 怎么查看python中类似len()这种函数的源码？
len是用对象的__len__方法来取长度的。所以你不能很笼统的说len的效率高不高。这得看具体对象的__len__是怎么实现的。
你当然也可以为自己的类实现一个__len__方法，然后速度巨慢。比方说下面的例子：
import timeit
import time
class A(object):
def __len__(self):
time.sleep(1)
return 0
print timeit.timeit(lambda : len(A()), number=5)
不过，如果具体说到某个类，我们还是可以去分析的。
比方说，我们想知道list的len方法，效率高不高。
从黑盒的方式，我们可以生成一个有很多元素的list，然后看看len要多长时间：
import timeit
import time
print timeit.timeit('len(a)', 'a = range(10000000)', number=1000000)
在我电脑上的结果是0.0686秒。
对1000万元素的list，取len做100万遍，只要0.0686秒。那这个len无疑是个常数时间的操作。
从白盒的方式，我们就要去看源代码了。我以2.7.2版本的代码为例。
既然len是builtin函数，那我们显然应该在 Python/bltinmodule.c 文件里去找。
在 builtin_methods 的定义里，你可以看到：
{"len", builtin_len, METH_O, len_doc},
说明len的实现是用一个叫builtin_len的函数：
static PyObject *
builtin_len(PyObject *self, PyObject *v)
{
Py_ssize_t res;
res = PyObject_Size(v);
if (res < 0 && PyErr_Occurred())
return NULL;
return PyInt_FromSsize_t(res);
}
这里可以看出，结果在PyObject_Size里。在 Objects/abstract.c 里：
Py_ssize_t
PyObject_Size(PyObject *o)
{
PySequenceMethods *m;
if (o == NULL) {
null_error();
return -1;
}
m = o->ob_type->tp_as_sequence;
if (m && m->sq_length)
return m->sq_length(o);
return PyMapping_Size(o);
}
这里可以发现，在对象类型的tp_as_sequence下面的sq_length里。
那我们去Objects/listobject.c里找到list的类型定义，在这里可以看到，
sq_length由一个叫list_length的方法实现：
static Py_ssize_t
list_length(PyListObject *a)
{
return Py_SIZE(a);
}
在Include/object.h里找到Py_SIZE的定义：
#define Py_SIZE(ob) (((PyVarObject*)(ob))->ob_size)
总结下来一句话，size是放在list对象的一个叫ob_size的成员里，list的len操作，
就是直接读这个数值而已。这是一个常数时间操作。
> Best Regards,
> 张晓润
> Sun Yat-sen University
>
>
--
Best Regards,
Leo Jay
lee Alexander
--
邮件来自: `CPyUG`华蟒用户组(中文Python技术邮件列表)
规则: http://code.google.com/p/cpyug/wiki/PythonCn
发言: pyth...@googlegroups.com
退订: python-cn+...@googlegroups.com (向此发空信即退!)
详情: http://code.google.com/p/cpyug/wiki/CpyUg
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
free.wang
--
邮件来自: `CPyUG`华蟒用户组(中文Python技术邮件列表)
规则: http://code.google.com/p/cpyug/wiki/PythonCn
发言: pyth...@googlegroups.com
退订: python-cn+...@googlegroups.com (向此发空信即退!)
详情: http://code.google.com/p/cpyug/wiki/CpyUg
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
真正的杰出，不是妙用规则的错层，而是极致的偏执于信念.
The Crankiness of Belief achieves Great , not the Trick of Regulation.
fengjian/风间星魂
> 邮件来自: `CPyUG`华蟒用户组(中文Python技术邮件列表)
> 规则: http://code.google.com/p/cpyug/wiki/PythonCn
> 发言: pyth...@googlegroups.com
> 退订: python-cn+...@googlegroups.com (向此发空信即退!)
> 详情: http://code.google.com/p/cpyug/wiki/CpyUg
> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
fengjian/风间星魂
fengjia...@gmail.com
blog: fengjian.sinaapp.com
求武汉地区任意unix方向工作。
2年iOS经验 objc/c/c++/python/lua
Zoom.Quiet
> --
> 邮件来自: `CPyUG`华蟒用户组(中文Python技术邮件列表)
> 规则: http://code.google.com/p/cpyug/wiki/PythonCn
> 发言: pyth...@googlegroups.com
> 退订: python-cn+...@googlegroups.com (向此发空信即退!)
> 详情: http://code.google.com/p/cpyug/wiki/CpyUg
> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
--
人生苦短, Pythonic! 冗余不做,日子甭过!备份不做,十恶不赦!
俺: http://about.me/zoom.quiet
文字协议: http://creativecommons.org/licenses/by-sa/2.5/cn/
gauss
感谢推荐，已购买此书