Equal Average Partition DP using Python 2 VS Python 3
<p>I was using memorization to try to solve the <a href="https://www.interviewbit.com/problems/equal-average-partition/" rel="nofollow">Equal Average Partition Problem</a>, somehow the solution that I came up with take a long time to solve the problem in <a href="https://repl.it/DJdT" rel="nofollow">Python 2.x</a> but relatively fast in <a href="https://repl.it/DJci" rel="nofollow">Python 3.x</a> 
I'm wondering whether anyone encounter something similar, and what are the reasons behind? Thanks </p>

<pre><code>def avgset(A):
    if len(A) &lt;= 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 &gt; 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))
</code></pre>

<p><code>something in dic.keys()</code> 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.</p>

<p>On <a href="https://docs.python.org/3/library/stdtypes.html#dictionary-view-objects" rel="nofollow">dictionary view objects</a>:</p>

<blockquote>
  <p>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, ==, &lt;, or ^).</p>
</blockquote>

<p>Consider using <code>something in dic</code>, 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)</p>

python dynamic-programming