Efficient, large-scale competition scoring in Python
<p>Consider a large dataframe of scores <code>S</code> containing entries like the following. Each row represents a contest between a subset of the participants <code>A</code>, <code>B</code>, <code>C</code> and <code>D</code>. </p>

<pre><code> A     B    C   D
0.1  0.3  0.8    1
  1  0.2  NaN  NaN
0.7  NaN    2  0.5
NaN   4   0.6  0.8
</code></pre>

<p>The way to read the matrix above is: looking at the first row, the participant <code>A</code> scored <code>0.1</code> in that round, <code>B</code> scored <code>0.3</code>, and so forth.</p>

<p>I need to build a triangular matrix <code>C</code> where <code>C[X,Y]</code> stores how much better participant <code>X</code> was than participant <code>Y</code>. More specifically, <code>C[X,Y]</code> would hold the <strong>mean</strong> % difference in score between <code>X</code> and <code>Y</code>. </p>

<p>From the example above:</p>

<pre><code>C[A,B] = 100 * ((0.1 - 0.3)/0.3 + (1 - 0.2)/0.2) = 33%
</code></pre>

<p>My matrix <code>S</code> is huge, so I am hoping to take advantage of JIT (Numba?) or built-in methods in <code>numpy</code> or <code>pandas</code>. I certainly want to avoid having a nested loop, since  <code>S</code> has millions of rows.</p>

<p>Does an efficient algorithm for the above have a name?</p>

<p>Let's look at a NumPy based solution and thus let's assume that the input data is in an array named <code>a</code>. Now, the number of pairwise combinations for 4 such variables would be <code>4*3/2 = 6</code>. We can generate the IDs corresponding to such combinations with <a href="http://docs.scipy.org/doc/numpy/reference/generated/numpy.triu_indices.html#numpy.triu_indices" rel="nofollow"><code>np.triu_indices()</code></a>. Then, we index into the columns of <code>a</code> with those indices. We perform the subtractions and divisions and simply add the columns ignoring the NaN affected results with <a href="http://docs.scipy.org/doc/numpy/reference/generated/numpy.nansum.html" rel="nofollow"><code>np.nansum()</code></a> for the desired output.</p>

<p>Thus, we would have an implementation like so -</p>

<pre><code>R,C = np.triu_indices(a.shape[1],1)
out = 100*np.nansum((a[:,R] - a[:,C])/a[:,C],0)
</code></pre>

<p>Sample run -</p>

<pre><code>In [121]: a
Out[121]: 
array([[ 0.1,  0.3,  0.8,  1. ],
       [ 1. ,  0.2,  nan,  nan],
       [ 0.7,  nan,  2. ,  0.5],
       [ nan,  4. ,  0.6,  0.8]])

In [122]: out
Out[122]: 
array([ 333.33333333, -152.5       ,  -50.        ,  504.16666667,
        330.        ,  255.        ])

In [123]: 100 * ((0.1 - 0.3)/0.3 + (1 - 0.2)/0.2) # Sample's first o/p elem
Out[123]: 333.33333333333337
</code></pre>

<p>If you need the output as <code>(4,4)</code> array, we can use <a href="http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.distance.squareform.html" rel="nofollow"><code>Scipy's squareform</code></a> -</p>

<pre><code>In [124]: from scipy.spatial.distance import squareform

In [125]: out2D = squareform(out)
</code></pre>

<p>Let's convert to a pandas dataframe for a good visual feedback -</p>

<pre><code>In [126]: pd.DataFrame(out2D,index=list('ABCD'),columns=list('ABCD'))
Out[126]: 
            A           B           C    D
A    0.000000  333.333333 -152.500000  -50
B  333.333333    0.000000  504.166667  330
C -152.500000  504.166667    0.000000  255
D  -50.000000  330.000000  255.000000    0
</code></pre>

<p>Let's compute <code>[B,C]</code> manually and check back -</p>

<pre><code>In [127]: 100 * ((0.3 - 0.8)/0.8 + (4 - 0.6)/0.6)
Out[127]: 504.1666666666667
</code></pre>

python pandas numpy matrix numba