algorithm - 提高模块效率

Question

我在这个方法中运行了大约 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    

这是将数字转换为 base3 的方法:-

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做一个软件，这2个函数是其中的一部分。请指教为什么这2个方法这么慢，以及如何提高这些方法的效率。

Answer 1

第一个函数可以简化为:

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)

下一步；你只是在生成一个 base-3 数字序列。直接生成这些:

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

这会产生 base3 值，用 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)