Mean Reciprocal Rank for Retrieval
Problem Statement
Report the Mean Reciprocal Rank (MRR) of a batch of retrieval queries: the average of 1/rank where rank is the 1-based position of the first correct hit in each query's ranked result list.
Background
For a query whose correct item first appears at rank r (1-indexed), the reciprocal rank is 1/r; if the correct item never appears, the reciprocal rank is 0. MRR averages this over all queries:
MRR=Q1​∑q=1Q​rankq​1​
MRR rewards putting the right answer near the top, unlike Recall@K which only checks membership.
Your Task
Implement:
def mean_reciprocal_rank(rankings, relevant):
- rankings[q]: the ranked list of retrieved item ids for query q (best first).
- relevant[q]: the single correct item id for query q.
Return the MRR as a float rounded to 4 decimals.
Input Format
- rankings: list of lists of ids.
- relevant: list of ids, one per query.
Output Format
- A float rounded to 4 decimals.
Sample
print(mean_reciprocal_rank([[3, 1, 2], [0, 5, 4]], [1, 4]))
Output:
0.4167
Example:
print(mean_reciprocal_rank([[3, 1, 2], [0, 5, 4]], [1, 4]))
0.4167
Query 0: correct id 1 is at rank 2 -> 0.5. Query 1: correct id 4 is at rank 3 -> 0.3333. Mean = (0.5+0.3333)/2 = 0.4167.
Constraints:
len(rankings) == len(relevant),1 <= Q <= 5000.- Rank is 1-based; a missing correct item contributes 0.
- Round to 4 decimals.
1. Background Knowledge
Mean Reciprocal Rank (MRR) is a standard evaluation metric for information retrieval systems. It measures how well a ranking algorithm places the correct answer near the top of its results. For a single query, if the correct item appears at 1-based position r, the reciprocal rank is r1​. If the correct item is absent from the ranked list, the reciprocal rank is 0.
The key intuition is that MRR heavily rewards top placements. A correct answer at rank 1 contributes 1.0, at rank 2 contributes 0.5, at rank 3 contributes ≈0.333, and so on. This makes MRR more sensitive to ranking quality than metrics like Recall@K, which only checks whether the correct item appears anywhere in the top K results.
MRR is computed by averaging the reciprocal ranks over all queries:
MRR=Q1​q=1∑Q​rankq​1​where Q is the total number of queries and rankq​ is the 1-based position of the first correct hit for query q.
2. Algorithm Approach
This is a straightforward linear scan problem. For each query:
- Iterate through the ranked list from position 1 onward.
- Check if the current item matches the relevant (correct) item for that query.
- If a match is found, record the reciprocal of the 1-based index.
- If no match is found after scanning the entire list, the contribution is 0.
After processing all queries, sum the reciprocal ranks and divide by the total number of queries.
The pattern is essentially: for each query, find the first occurrence of the target in a list, compute 1/position, and accumulate.
3. Step-by-Step Strategy
- Initialize a running sum variable (e.g., total_rr = 0.0) and note the number of queries Q=len(rankings).
- Loop over each query index q from 0 to Q−1:
- Retrieve rankings[q] (the ranked list) and relevant[q] (the correct item id).
- Scan the ranked list with a 1-based counter (or use 0-based index and add 1).
- For each position, check if the item equals the relevant id.
- If found: add position1​ to total_rr and break out of the inner loop (only the first hit counts).
- If the list is exhausted without a match: add 0 (i.e., do nothing).
- Compute MRR as total_rr / Q.
- Round the result to 4 decimal places using round(value, 4).
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.