本以为自己不会再写水文了，突然发现只能勉强写水文维持生活。那就继续写水文吧！有一天，技术组的一个小哥提出了这样一个问题，为什么在某些情况下，Python中简单的乘法/除法比按位运算要慢。首先，本着实事求是的精神，我们先验证一下：In[33]:%timeit1073741825*27.47ns±0.0843nsperloop(mean±std.dev.of7runs,100000000loopseach)In[34]:%timeit1073741825<<17.43ns±0.0451nsperloop(mean±std.dev.of7runs,100000000loopseach)In[35]:%timeit1073741823<<17.48ns±0.0621nsperloop(mean±std.dev.of7runs,100000000loopseach)In[37]:%timeit1827337nsperloop*27.46ns(mean±std.dev.of7runs,100000000loopseach)我们发现了几个很有趣的现象：当取值x<=2^30时，乘法比直接位运算快；当取值x>2^32时，乘法明显慢于位运算的现象很有意思，那么造成这种现象的根本原因是什么呢？其实跟Python的底层实现有关。简述1.PyLongObject的实现在Python2.x时期，整数在Python中分为两种类型，一种是long，一种是int。两者已在Python3中合并。目前，两者在Python3中合并，只剩下一个long。首先我们看一下long这种数据结构的底层实现：struct_longobject{PyObject_VAR_HEADdigitob_digit[1];};这里不用关心PyObject_VAR_HEAD的含义，我们只需要关心ob_digit即可。这里ob_digit使用了C99中的“灵活数组”来存储任意长度的整数。这里我们可以看看官方代码中的文档：长整型表示。一个数的绝对值等于SUM(fori=0throughabs(ob_size)-1)ob_digit[i]*2**(SHIFT*i)负数用ob_size<0表示；零由ob_size==0表示。在标准化数字中，ob_digit[abs(ob_size)-1]（最高有效数字）永远不会为零。此外，在所有情况下，对于所有有效的i，0<=ob_digit[i]<=MASK。分配函数负责分配额外的内存，以便ob_digit[0]...ob_digit[abs(ob_size)-1]实际上可用。注意：操作PyVarObject子类型的通用代码必须注意int滥用ob_size的符号位。简而言之，Python将一个十进制数转换成2^(SHIFT)基数进行存储。这里可能不太容易理解。让我举一个例子。在我的电脑上，SHIFT是30。假设有一个整数1152921506754330628，那么把它转换成2^30就是：4*(2^30)^0+2*(2^30)^1+1*(2^30)^2。那么此时ob_digit是一个包含三个元素的数组，它的值为[4,2,1]。OK，了解了这样的基础知识，我们再回头看看Python中的乘法运算。2.Python中的乘法运算Python中的乘法运算分为两部分。对于大数的乘法，Python采用Karatsuba算法1，具体实现如下：));PyLongObject*ah=NULL;PyLongObject*al=NULL;PyLongObject*bh=NULL;PyLongObject*bl=NULL;PyLongObject*ret=NULL;PyLongObject*t1,*t2,*t3;Py_ssize_tshift;/*thenumberofdigitswesplitoff*/Py_ssize_ti;/*(ah*X+al)(bh*X+bl)=ah*bh*X*X+(ah*bl+al*bh)*X+al*bl*Letk=(ah+al)*(bh+bl)=ah*bl+al*bh+ah*bh+al*bl*那么原来的产品是*ah*bh*X*X+(k-ah*bh-al*bl)*X+al*bl*BypickingXtobeapowerof2"*X"只是移位，它*被减少到3个乘以数字的一半。*//*我们要根据较大的数字进行拆分；fiddlessothatb*最大。*/if(asize>bsize){t1=a;a=b;b=t1;i=asize;asize=bsize;bsize=i;}/*Usegradeschoolmathwheneithernumberistoosmall.*/i=a==b?KARATSUBA_SQUARE_CUTOFF:KARATSUBA_CUTOFF;if(asize<=i){if(asize==0）返回（PyLongObject*）PyLong_FromLong（0）；否则返回x_mul(a,b);}/*Ifaissmallcomparedtob,splittingonbgivesadegenerate*casewithah==0,andKaratsubamaybe(evenmuch)efficient*than"gradeschool"then.However,wecanstillwinwin,byviewing*basastringof"bigdigits",每个widtha->ob_size.That*leadstoasequenceofbalancedcallstok_mul.*/if(2*asize<=bsize)returnk_lopsided_mul(a,b);/*Splita&bintohi&lopieces.*/shift=bsize>>1;if(kmul_split(a,shift,&ah,&al)<0)gotofail;断言(Py_SIZE(ah)>0);/*thesplitisn'tdegenerate*/if(a==b){bh=ah;bl=al;Py_INCREF(bh);Py_INCREF(bl);}elseif(kmul_split(b,shift,&bh,&bl)<0)gotofail;/*计划：*1.Allocateresultspace(asize+bsizedigits:that'salways*enough).*2.Computeah*bh,andcopyintoresultat2*shift.*3.Computeal*bl,andcopyintoresultat0.请注意，这*不能与#2.*4.从结果中减去*bl重叠，从shift开始。这可能*下溢（借用高位），但我们不在乎：*我们正在有效地进行无符号算术mod*BASE**(sizea+sizeb)，并且只要*最终*结果适合，*借用和进位可以忽略高位。*5.从结果中减去h*bh，从shift开始。*6.计算(ah+al)*(bh+bl)，并从*atshift开始添加到其他结果中。*//*1.分配结果空间。*/ret=_PyLong_New(asize+bsize);if(ret==NULL)gotofail;#ifdefPy_DEBUG/*Fillwithtrash，tocatchreferencetouninitializeddigits.*/memset(ret->ob_digit,0xDF,Py_SIZE(ret)*sizeof(digit));#endif/*2.t1<-ah*bh,andcopyintohighdigitsofresult.*/if((t1=k_mul(ah,bh))==NULL)gotofail;assert(Py_SIZE(t1)>=0);assert(2*shift+Py_SIZE(t1)<=Py_SIZE(ret));memcpy(ret->ob_digit+2*shift,t1->ob_digit,Py_SIZE(t1)*sizeof(digit));/*零-outthedigitshigherthantheah*bhcopy.*/i=Py_SIZE(ret)-2*shift-Py_SIZE(t1);if(i)memset(ret->ob_digit+2*shift+Py_SIZE(t1),0,i*sizeof(digit));/*3.t2<-al*bl,andcopyintothelowdigits.*/if((t2=k_mul(al,bl))==NULL){Py_DECREF(t1);gotofail;}assert(Py_SIZE(t2)>=0);assert(Py_SIZE(t2)<=2*shift);/*不与高位重叠*/memcpy(ret->ob_digit,t2->ob_digit,Py_SIZE(t2)*sizeof(digit));/*Zerooutremainingdigits.*/i=2*shift-Py_SIZE(t2);/*numberofuninitializeddigits*/if(i)memset(ret->ob_digit+Py_SIZE(t2),0,i*sizeof(digit));/*4&5.Subtractah*bh(t1)andal*bl(t2).Wedoal*blfirst*becauseit'sfresherincache.*/i=Py_SIZE(ret)-shift;/*#digitsaftershift*/(void)v_isub(ret->ob_digit+shift,i,t2->ob_digit,Py_SIZE(t2));Py_DECREF(t2);(void)v_isub(ret->ob_digit+shift,i,t1->ob_digit,Py_SIZE(t1));Py_DECREF(t1);/*6.t3<-(ah+al)(bh+bl),andaddintoresult.*/if((t1=x_add(ah,al))==NULL)gotofail;Py_DECREF(ah);Py_DECREF(al);ah=al=NULL;if(a==b){t2=t1;Py_INCREF(t2);}elseif((t2=x_add(bh,bl))==NULL){Py_DECREF(t1);gotofail;}Py_DECREF(bh);Py_DECREF(bl);bh=bl=NULL;t3=k_mul(t1,t2);Py_DECREF(t1);Py_DECREF(t2);if(t3==NULL)gotofail;assert(Py_SIZE(t3)>=0);/*Addt3.It'snotobviouswhywecan'trunoutofroomhere.*Seethe(*)commentafterthisfunction.*/(void)v_iadd(ret->ob_digit+shift,i,t3->ob_digit,Py_SIZE(t3));Py_DECREF(t3);returnlong_normalize(ret);fail:Py_XDECREF(ret);Py_XDECREF(ah);Py_XDECREF(al);Py_XDECREF(bh);Py_XDECREF(bl);returnNULL;}这是错误Karatsuba算法1的实现将单独说明。感兴趣的朋友可以参考文末参考资料了解具体细节。一般情况下，普通乘法的时间复杂度为n^2（n为位数），而K算法的时间复杂度为3n^(log3)≈3n^1.585。看起来K算法的性能比普通的乘法要好，那为什么Python不用K算法呢？这很简单。K算法的优势其实就是当n足够大的时候，会形成比普通乘法的优势。同时考虑到内存访问等因素，当n不够大时，使用K算法的性能实际上会比直接乘法差。那么我们来看看乘法在Python中的实现：staticPyObject*long_mul(PyLongObject*a,PyLongObject*b){PyLongObject*z;CHECK_BINOP(a,b);/*fastpathforsingle-digitmultiplication*/if(Py_ABS(Py_SIZE(a))<=1&&Py_ABS(Py_SIZE(b))<=1){stwodigitsv=(stwodigits)(MEDIUM_VALUE(a))*MEDIUM_VALUE(b);returnPyLong_FromLongLong((longlong)v);}z=k_mul(a,b);/*取反ifexactlyoneoftheinputsisnegative.*/if(((Py_SIZE(a)^Py_SIZE(b))<0)&&z){_PyLong_Negate(&z);if(z==NULL)returnNULL;}return(PyObject*)z;}in这里我们看到，当两个数小于2^30-1时，Python会直接使用普通的乘法返回，否则会使用K算法进行计算。这时候我们再来看位运算的实现。示例：staticPyObject*long_rshift(PyObject*a,PyObject*b){Py_ssize_twordshift;digitremshift;CHECK_BINOP(a,b);if(Py_SIZE(b)<0){PyErr_SetString(PyExc_ValueError,"negativeshiftcount");returnNULL;}if(Py_SIZE(a)==0){returnPyLong_FromLong(0);}if(divmod_shift(b,&wordshift,&remshift)<0)returnNULL;returnlong_rshift1((PyLongObject*)a,wordshift,remshift);}staticPyObject*long_rshift1(龙Object*a,Py_ssize_twordshift,digitremshift){PyLongObject*z=NULL;Py_ssize_tnewsize,hishift,i,j;digitlomask,himask;if(Py_SIZE(a)<0){/*Rightshiftingnegativenumbersisharder*/PyLongObject*a1,*a2;a1=(PyLongObject*)long_invert(a);if(a1==NULL)returnNULL;a2=(PyLongObject*)long_rshift1(a1,wordshift,remshift);Py_DECREF(a1);if(a2==NULL)returnNULL;z=(PyLongObject*)long_invert(a2);Py_DECREF(a2);}else{newsize=Py_SIZE(a)-wordshift;if(newsize<=0)returnPyLong_FromLong(0);hishift=PyLong_SHIFT-remshift;lomask=((digit)1<
