Efficient, large-scale competition scoring in Python

Question

Consider a large dataframe of scores S containing entries like the following. Each row represents a contest between a subset of the participants A, B, C and D.

 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

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

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

From the example above:

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

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

Does an efficient algorithm for the above have a name?

Answer 1

Let's look at a NumPy based solution and thus let's assume that the input data is in an array named a. Now, the number of pairwise combinations for 4 such variables would be 4*3/2 = 6. We can generate the IDs corresponding to such combinations with np.triu_indices(). Then, we index into the columns of a with those indices. We perform the subtractions and divisions and simply add the columns ignoring the NaN affected results with np.nansum() for the desired output.

Thus, we would have an implementation like so -

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

Sample run -

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

If you need the output as (4,4) array, we can use Scipy's squareform -

In [124]: from scipy.spatial.distance import squareform

In [125]: out2D = squareform(out)

Let's convert to a pandas dataframe for a good visual feedback -

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

Let's compute [B,C] manually and check back -

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