seanh - 1 year ago 98

Python Question

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))

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.

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 collections.abc.Set 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)