Chains versus loops: top-k, and a function that must not allocate

Select the best-scoring items and count positive scores. The two functions use the same input, but only the counting function has an allocation check.

pub struct Item { pub id: u32, pub score: i64 }

pub fn top_k_by_score(items: &[Item], k: usize) -> Vec<u32>
pub fn count_matching(items: &[Item]) -> usize

Select the top k items

Return the ids of the k highest-scoring items. Order by score descending, then by id ascending when scores tie. Preserve repeated items and ids; this is a selection of entries, not a set of unique ids.

Return an empty vector when k == 0 or the input is empty. If k exceeds the input length, return every id in the required order. This also applies to very large k: base storage on min(k, items.len()), not the requested count alone. Scores can use the full i64 range, so avoid reversing their order by negating them.

ids    = [1,  2,  3,  4]
scores = [10, 30, 20, 30], k = 2  -> [2, 4]

ids    = [3, 1, 2]
scores = [7, 7, 7], k = 2        -> [1, 2]

For this exercise, keep a bounded BinaryHeap while scanning rather than sorting the whole input. A push-then-pop approach retains at most m items after each step, with a temporary extra item during insertion, where m = min(k, items.len()). Sort the retained items to produce the final order. The value tests check results, not whether you used this structure.

Make the worst retained item easy to remove

BinaryHeap puts its largest element at the top. Build a key where larger means better: (score, Reverse(id)). The first coordinate prefers higher scores; the second prefers smaller ids. Wrap that entire key in Reverse so the heap exposes the worst retained item for removal.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((30_i64, Reverse(4_u32))));
    heap.push(Reverse((30_i64, Reverse(2_u32))));
    heap.push(Reverse((10_i64, Reverse(1_u32))));
    assert_eq!(heap.pop(), Some(Reverse((10, Reverse(1)))));
    assert_eq!(heap.pop(), Some(Reverse((30, Reverse(4)))));
    assert_eq!(heap.pop(), Some(Reverse((30, Reverse(2)))));
}

For n input items and m > 0, scanning this way takes O(n log(m + 1)) time. Sorting the retained items takes O(m log(m + 1)) time, with O(m) auxiliary storage overall. Writing log(m + 1) includes the linear scan when m == 1. When m == 0, return immediately.

Count without collecting

count_matching returns the number of items with score > 0. Zero and negative scores do not count. This function must make no heap allocations during the measured call. Filtering references and calling count() can compute the answer directly without building an intermediate collection:

fn main() {
    let scores = [-3, 0, 4, 9];
    let count = scores.iter().filter(|&&score| score > 0).count();
    assert_eq!(count, 2);
}

The starter instead collects matching references into a vector and asks for its length. A vector may allocate and grow as matches arrive; no matches may require no allocation. Its exact allocation count is not part of Rust's API contract and can also be affected by optimization.

The harness snapshots a global allocator counter around count_matching and rejects an increase. Input parsing and top_k_by_score happen outside that interval. This checks observed allocation calls for the tested build and inputs, not every possible execution of the source. Do not rely on an optimizer to remove an unnecessary collection; use a counting operation. Clippy's opt-in needless_collect lint can help identify this pattern, but a successful default lint check does not establish allocation behavior.

Compare implementations by measuring them

Iterators and loops can compile to similar machine code. Neither form is always faster. Inlining, bounds-check elimination, vectorization, allocation and input shape all matter. For example, zip stops at the shorter input; an indexed loop that assumes equal lengths has a different contract unless you establish that length relationship first.

An iterator's size_hint can help a collector reserve storage, but losing an exact length does not by itself prove a slowdown. Nor does knowing the length prove that an iterator chain is free of overhead. Compare implementations that perform the same work on representative data and inspect variation across repeated optimized runs. Record the compiler, build flags, machine and input sizes when reporting timings.

black_box can help prevent a benchmark from being simplified using known inputs or an unused result. Wrap inputs before the work and consume its result afterward:

use std::hint::black_box;

fn positive_count(scores: &[i64]) -> usize {
    scores.iter().filter(|&&score| score > 0).count()
}

fn main() {
    let scores = [-3, 0, 4, 9];
    let result = black_box(positive_count(black_box(&scores)));
    assert_eq!(result, 2);
}

This demonstrates placement, not a complete benchmark. black_box is a best-effort optimization hint. Expressions inside its argument can still be simplified: black_box(5 * 10) does not require a runtime multiplication.

Submissions must compile, pass the value and allocation checks, and pass Clippy with warnings treated as errors. The starter also sorts tied ids in the wrong direction, so fixing only its counting function is not enough.