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>There is only one difference between python 2 and 3 that you are using. In line</p>

<pre><code>if (idx, curSum, curSize) in dic.keys(): return dic[(idx, curSum, curSize)]
</code></pre>

<p>method <code>keys()</code> in python2 returns list of dict keys and in python3 returns iterator through keys (it was iterkeys() method in python2.) Note that method <code>keys()</code> is not needed since operator <code>in &lt;dict&gt;</code> will return result you want. So code </p>

<pre><code>if (idx, curSum, curSize) in dic: return dic[(idx, curSum, curSize)]
</code></pre>

<p>works with same speed in 2 and 3.</p>

<p>It seems that operator <code>in &lt;iterator&gt;</code> is optimized in python3, if it is possible to evaluate it faster than to iterate through elements, like in <code>dict</code> or <code>set</code>.</p>

python dynamic-programming