Precision@k and NDCG@k

Background

Ranking metrics judge an ordered list of results, not a single prediction. Precision@k is the fraction of the top-$k$ results that are relevant. NDCG@k (Normalised Discounted Cumulative Gain) additionally rewards placing more relevant items higher, discounting gains logarithmically by rank and normalising against the ideal ordering. They are the workhorse metrics of search and recommendation evaluation.

Problem statement

Implement precision_at_k(relevances, k) and ndcg_at_k(relevances, k), where relevances lists the relevance scores in the model's ranked order (higher = more relevant; relevance $> 0$ means "relevant"):

$$\text{P@}k = \frac{1}{k}\sum_{i=1}^{k}\mathbb{1}(\text{rel}_i > 0)$$ $$\text{DCG@}k = \sum_{i=1}^{k}\frac{\text{rel}_i}{\log_2(i+1)}, \qquad \text{NDCG@}k = \frac{\text{DCG@}k}{\text{IDCG@}k}$$

where $\text{IDCG@}k$ is the DCG of the relevances sorted in descending order.

Input

• relevances — list[float]: relevance scores in ranked order.
• k — int: the cutoff rank.

Output

• precision_at_k returns a float in $[0, 1]$.
• ndcg_at_k returns a float in $[0, 1]$ ($1$ = ideal ordering).

Examples

Example 1

Input:  relevances = [3, 2, 3, 0, 1, 2], k = 3
Output: precision_at_k = 1.0, ndcg_at_k = 0.9778

Explanation: all of the top 3 are relevant (P@3 = 1.0). DCG@3 = $3/\log_2 2 + 2/\log_2 3 + 3/\log_2 4$; dividing by the ideal DCG (relevances sorted descending) gives NDCG@3 = 0.9778.

Constraints

• Rank positions start at 1; the discount for position $i$ is $\log_2(i+1)$.
• Precision@k counts relevance $> 0$ as relevant and always divides by $k$.
• NDCG normalises by IDCG@k (ideal ordering); return $0$ if IDCG@k is $0$.
• Tests compare with atol=1e-4.

Notes

• The log discount encodes "higher ranks matter more": moving a relevant item from rank 1 to rank 10 sharply reduces its contribution.
• NDCG lies in $[0, 1]$ and is comparable across queries thanks to the per-query ideal-DCG normalisation, unlike raw DCG.