优化Python代码有感

最近信息安全的老师布置了作业。要求实现DES算法。。写了1天，优化了1天。。。小有些心得。。

首先感慨一下DES算法。。真是对人对机器都不友好的算法。。竟然还有诡异的S-BOX操作。。。

第二感慨一下Python对2进制不那么方便的支持。。连bin函数都没有。。虽然3.0有了。。可惜2.5没有。。只能自己实现，一大损失效率的地方啊。

好，接下来说说优化过程。

      首先是单线程改多线程。。原来是将明文分成64bit一块的序列，每块单独加密。改成每一个64bit的块开一个线程操作。

      单线程加密解密一个1000长度的字符串所需时间大致和多线程加密10000长度的相等。效率提升明显。

      其次是优化异或过程。原来的异或是整体将字符串转成整数然后再异或，发现效率很低。第一次修改为将2个字符串的每一位单独取出转成整形以后异或，效率提升不明显。后来上课时候突然想到，异或操作其实完全可以抛弃整数。1位的2个字符串的异或操作只有4种，写一个字典，用想要异或的2个字符串作为key，结果作为value。简单实现了一下。

def Xor(s1, s2):
    """
    字符串xor
    
    s1 -- 第一个字符串
    s2 -- 第二个字符串
    """
    data={}
    data['0','1']=data['1','0']='1'
    data['0','0']=data['1','1']='0'
    s=[data[s1[x],s2[x]] for x in range(0,s1.__len__())]
    return ''.join(s)

 

      第三就是优化10进制转2进制。因为python没有提供 bin 函数。于是自己实现了一个。

dec2bin = lambda n:''.join([hex2bin(x) for x in hex(n)[2:].rstrip('L')]

 

但是在用profile做测试的时候发现的。程序运行中大量的用到了这个函数。很占cpu时间。经过观察发现主要是2个地方使用很多，第一就是异或操作的时候，因为python提供的异或只能在整数之间进行，第二就是在S_BOX运算的时候。

      异或操作已经优化了。不需要10进制转2进制了。。剩下就是S_BOX运算了。经过观察发现，S_BOX里面最大的数也不过 15,于是想到可以穷举所有S_BOX里面的数字的值对应的二进制。更改代码如下。

def easyDec2Bin(s):
    """
    简单的10进制转2进制,用于简化s_box操作
    
    s -- 10进制数
    """
    data={0:'0000',1:'0001',2:'0010',3:'0011',4:'0100',
		      5:'0101',6:'0110',7:'0111',8:'1000',9:'1001',
		      10:'1010',11:'1011',12:'1100',13:'1101',14:'1110',
		      15:'1111'}
    return data[s]

 

  第四步优化也是通过profile发现的。。发现程序运行过程中，大量的时间消耗在一个lambda函数上。

    b= ''.join(map(lambda x:data[x],s))

   这个函数的作用是生成一个字符串。。尝试着把这个lambda函数改成列表操作。

    b= ''.join([data[x] for x in s]

      效率提升明显。。。原来一直以为map操作比较快。看来并非如此。难怪Guido大叔要推广列表操作了。。

      最后一步优化就是用了psyco模块，将程序变成JIT的。。效率提升很大。。。

最终优化的结果就是，加密解密1个40k的文件，原本需要将近50秒的时间，现在10秒不到就完成了。。。。

效果提升明显。不过总觉得还有提升的空间。。尝试把多线程改成Stackless版本的试试看。。。。希望能有更大的提高 。。。。