title: Is there an efficient Python implementation for Somers'D for ungrouped variables?
body: <p>I'm looking for an efficient python implementation of Somers'D, for which I need to compute the number of concordant, discordant and tied pairs between two random variables X and Y. Two pairs (X_i, Y_i), (X_j, Y_j) are concordant if the ranks of both elements agree; that is, <code>x_i &gt; x_j</code> and  <code>y_i &gt; y_j</code> or <code>x_i &lt; x_j</code> and  <code>y_i &lt; y_j</code>. Two pairs are called discordant if the ranks of both elements do not agree: <code>x_i &gt; x_j</code> and  <code>y_i &lt; y_j</code> or <code>x_i &lt; x_j</code> and  <code>y_i &gt; y_j</code>. Two pairs are said to be tied in X (Y) when <code>x_i = x_j</code> <code>y_i = y_j</code>. </p>
  
  <p>Somers'D is then computed as <code>D = (N_C - N_D) / (N_tot - N_Ty).</code>
  (See: <a href="https://en.wikipedia.org/wiki/Somers%27_D" rel="noreferrer">https://en.wikipedia.org/wiki/Somers%27_D</a>.)</p>
  
  <p>I wrote a naive implementation using nested for-loops. Here, S contains my predictions and Y the realized outcomes.</p>
  
  <pre><code>def concordance_computer(Y, S): 
      N_C = 0
      N_D = 0
      N_T_y = 0
      N_T_x = 0
  
      for i in range(0, len(S)):
          for j in range(i+1, len(Y)):
              Y1 = Y[i]
              X1 = S[i]
              Y2 = Y[j]
              X2 = S[j]
  
              if Y1 &gt; Y2 and X1 &gt; X2:
                  N_C += 1
              elif Y1 &lt; Y2 and X1 &lt; X2:
                  N_C += 1
              elif Y1 &gt; Y2 and X1 &lt; X2:
                  N_D += 1
              elif Y1 &lt; Y2 and X1 &gt; X2:
                  N_D += 1
              elif Y1 == Y2:
                  N_T_y += 1
              elif X1 == X2:
                  N_T_x += 1
  
      N_tot = len(S)*(len(S)-1) / 2                        
      SomersD = (N_C - N_D) / (N_tot - N_T_y)      
  
      return SomersD
  </code></pre>
  
  <p>Obviously, this is gonna be very slow when (Y,S) have a lot of rows. I stumbled upon the use of bisect while searching the net for solutions:</p>
  
  <pre><code>merge['Y'] = Y
  merge['S'] = S
  zeros2 = merge.loc[merge['Y'] == 0]
  ones2 = merge.loc[merge['Y'] == 1]
  
  from bisect import bisect_left, bisect_right
  def bin_conc(zeros2, ones2):
      zeros2_list = sorted([zeros2.iloc[j, 1] for j in range(len(zeros2))])
      zeros2_length = len(zeros2_list)
  
      conc = disc = ties = 0
      for i in range(len(ones2)):
          cur_conc = bisect_left(zeros2_list, ones2.iloc[i, 1])
          cur_ties = bisect_right(zeros2_list, ones2.iloc[i, 1]) - cur_conc
          conc += cur_conc
          ties += cur_ties
          disc += zeros2_length - cur_ties - cur_conc
  
      pairs_tested = zeros2_length * len(ones2.index)
  
      return conc, disc, ties, pairs_tested
  </code></pre>
  
  <p>This is very efficient, but only works for binary variables Y. Now my question is: how can I implement the <code>concordance_computer</code> in an efficient way for ungrouped Y?</p>