algorithm - 提高模块效率

我用这种方法运行循环大约100万次，但是可能由于O（n^2）而花费了很多时间，所以有没有办法改进这两个模块：-

def genIndexList(length,ID):
   indexInfoList = []
   id = list(str(ID))
   for i in range(length):
       i3 = (str(decimalToBase3(i)))
       while len(i3) != 12:
           i3 = '0' + i3
       p = (int(str(ID)[0]) + int(i3[0]) + int(i3[2]) + int(i3[4]) + int(i3[6]) +     int(i3[8]) + int(i3[10]))%3
       indexInfoList.append(str(ID)+i3+str(p))
   return indexInfoList

下面是将数字转换为基数3的方法：-

def decimalToBase3(num):
   i = 0
   if num != 0 and num != 1 and num != 2:
       number = ""
       while num != 0 :
           remainder = num % 3
           num = num / 3
           number = str(remainder) + number
       return int(number)
   else:
       return num

我用python做了一个软件，这两个函数是其中的一部分，请说明为什么这两个方法速度这么慢，以及如何提高这些方法的效率。

最佳答案

第一个功能可以简化为：

def genIndexList(length, ID):
   indexInfoList = []
   id0 = str(ID)[0]
   for i in xrange(length):
       i3 = format(decimalToBase3(i), '012d')
       p = sum(map(int, id0 + i3[::2])) % 3
       indexInfoList.append('{}{}{}'.format(ID, i3, p))
   return indexInfoList

您可能希望将其改为生成器：

def genIndexList(length, ID):
   id0 = str(ID)[0]
   for i in xrange(length):
       i3 = format(decimalToBase3(i), '012d')
       p = sum(map(int, id0 + i3[::2])) % 3
       yield '{}{}{}'.format(ID, i3, p)

第二个功能可以是：

def decimalToBase3(num):
   if 0 <= num < 3: return num
   result = ""
   while num:
       num, digit = divmod(num, 3)
       result = str(digit) + result
   return int(result)

下一步；您只需生成一个基数为3的数字序列直接生成这些：

from itertools import product, imap
def base3sequence(l=12, digits='012'):
    return imap(''.join, product(digits, repeat=l))

这将生成基3值，0填充到12位：

>>> gen = base3sequence()
>>> for i in range(10):
...     print next(gen)
...
000000000000
000000000001
000000000002
000000000010
000000000011
000000000012
000000000020
000000000021
000000000022
000000000100

genIndexList()变成：

from itertools import islice
def genIndexList(length, ID):
   id0 = str(ID)[0]
   for i3 in islice(base3sequence(), length):
       p = sum(map(int, id0 + i3[::2])) % 3
       yield '{}{}{}'.format(ID, i3, p)

关于algorithm - 提高模块效率，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16810125/