seanh - 2 months ago 22
Python Question

# Equal Average Partition DP using Python 2 VS Python 3

I was using memorization to try to solve the Equal Average Partition Problem, somehow the solution that I came up with take a long time to solve the problem in Python 2.x but relatively fast in Python 3.x
I'm wondering whether anyone encounter something similar, and what are the reasons behind? Thanks

``````def avgset(A):
if len(A) <= 1: return []
A.sort()
A = 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]
A = list(A)
for 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 = []
for itm in res1:
tmp = [A[idx]]+itm
if tmp not in res3:
res3.append(tmp)
for itm in res2:
if itm not in res3:
res3.append(itm)
dic[(idx, curSum, curSize)] = res3
return dic[(idx, curSum, curSize)]

A = [ 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))
``````

`something in dic.keys()` will be O(n) in Python 2 (membership in list) and O(1) in in Python 3 (membership in set). This accounts for observed difference in performance.
Consider using `something in dic`, which is O(1) in both Python 2.x and 3.x and is basically equivalent (unless you modify dict on the fly and want to freeze state of dict keys before modifying it)