i using memorization try solve equal average partition problem, somehow solution came take long time solve problem in python 2.x relatively fast in python 3.x i'm wondering whether encounter similar, , reasons behind?
def avgset(a): if len(a) <= 1: return [] a.sort() = tuple(a) idx = 0 cursum = 0 cursize = 0 dic = {} length = len(a) avg = sum(a)/float(length) minary = sorted(recursive(a, idx, cursum, cursize, avg, dic), key=lambda x:len(x))[0] = list(a) itm in minary: a.remove(itm) return [minary, a] def recursive(a, idx, cursum, cursize, avg, dic): if idx > len(a)-1: return none if (idx, cursum, cursize) in dic.keys(): return dic[(idx, cursum, cursize)] if (cursum+a[idx])/ float(cursize+1) == avg: return [[a[idx]]] res1 = recursive(a, idx+1, cursum+a[idx], cursize+1, avg, dic) or [] res2 = recursive(a, idx+1, cursum, cursize, avg, dic) or [] res3 = [] itm in res1: tmp = [a[idx]]+itm if tmp not in res3: res3.append(tmp) itm in res2: if itm not in res3: res3.append(itm) dic[(idx, cursum, cursize)] = res3 return dic[(idx, cursum, cursize)] = [ 28, 10, 2, 44, 33, 31, 39, 46, 1, 24, 32, 31, 28, 9, 13, 40, 46, 1, 16, 18, 39, 13, 48, 5 ] print (avgset(a))
there 1 difference between python 2 , 3 using. in line
if (idx, cursum, cursize) in dic.keys(): return dic[(idx, cursum, cursize)] method keys() in python2 returns list of dict keys , in python3 returns iterator through keys (it iterkeys() method in python2.) note method keys() not needed since operator in <dict> return result want. code
if (idx, cursum, cursize) in dic: return dic[(idx, cursum, cursize)] works same speed in 2 , 3.
it seems operator in <iterator> optimized in python3, if possible evaluate faster iterate through elements, in dict or set.
Comments
Post a Comment