seanh seanh - 10 months ago 89
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 = 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:
for itm in res2:
if itm not in res3:
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))

Answer Source

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.

On dictionary view objects:

Keys views are set-like since their entries are unique and hashable. If all values are hashable, so that (key, value) pairs are unique and hashable, then the items view is also set-like. (Values views are not treated as set-like since the entries are generally not unique.) For set-like views, all of the operations defined for the abstract base class are available (for example, ==, <, or ^).

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)