我对Python中%
运算符的时间和空间复杂度很感兴趣。此外,Python是否对% 2
使用位运算?
编辑: 我询问的是Python 2.7的实现,以防它与Python 3略有不同。
Python使用Knuth的《计算机编程艺术》中的经典算法D。运行时间(通常)与两个数字长度的乘积成正比。空间与两个数字长度的和成正比。
实际的除法在Objects/longobject.c
中进行,参见x_divrem()。关于Python长整数的内部表示的背景信息,请参见Include/longintrepr.h
。
% 2
不使用位运算。检查一个数字是否为偶数/奇数的标准惯用法是& 1
。
Python 2和3使用相同的算法。
Python 2.7的文档(http://docs.python.org/2.7/library/functions.html?highlight=divmod#divmod)提供了一些关于这方面的基础信息。
我还看了一下源代码;虽然不是专家级人物,但我可以告诉你,在Objects\abstract.c文件中,"divmod()"被定义为二进制函数。
在第1246行定义了一个用于求余数的函数:
PyObject *
PyNumber_Remainder(PyObject *v, PyObject *w)
{
return binary_op(v, w, NB_SLOT(nb_remainder), "%");
}
binary_op函数定义在第994行,主要包装了在第922行定义的函数“binary_op1”。从那里开始,大部分代码运行到一个名为“NB_BINOP”的函数,该函数在下面的代码中定义在第895行:
#define NB_BINOP(nb_methods, slot) \
(*(binaryfunc*)(& ((char*)nb_methods)[slot]))