ROC AUC from Scores

AUC is the number every classification result is quoted with, and a researcher is expected to know what it measures, not only how to call it. Computing it from scratch is a good exercise because the definition suggests a double loop over every pair of examples, and the right answer is a sort.

Implement roc_auc(scores, labels).

• scores: a list of \( n \) real-valued scores. A higher score means the model thinks a positive is more likely. Scores need not be probabilities and may repeat.
• labels: a list of \( n \) labels, each 0 or 1.

The area under the ROC curve is the probability that a randomly chosen positive has a higher score than a randomly chosen negative, with a tie counting one half:

\[ \text{AUC} = \frac{1}{n_+ n_-} \sum_{i:\,y_i = 1} \;\sum_{j:\,y_j = 0} \Big( [s_i > s_j] + \tfrac{1}{2}[s_i = s_j] \Big) \]

where \( n_+ \) and \( n_- \) are the numbers of positives and negatives.

Return the AUC as a plain Python float rounded to 4 decimals (round(float(x), 4)). If there are no positives or no negatives, the AUC is undefined: return None.

Examples

roc_auc([0.1, 0.4, 0.35, 0.8], [0, 0, 1, 1])
# 0.75

There are \( 2 \times 2 = 4 \) positive-negative pairs. The positive at 0.8 beats both negatives. The positive at 0.35 beats the negative at 0.1 and loses to the one at 0.4. That is 3 wins out of 4.

roc_auc([0.5, 0.5, 0.2, 0.8], [1, 0, 0, 1])
# 0.875

The positive at 0.5 ties the negative at 0.5, which counts one half, and beats the negative at 0.2. The positive at 0.8 beats both. That is \( 3.5 / 4 \).

Constraints

• \( 1 \le n \le 200{,}000 \).
• One hidden test has \( n = 200{,}000 \) with about half positives and many tied scores. A loop over every pair is about \( 10^{10} \) steps and cannot finish. Aim for \( O(n \log n) \).