Speeding Up a Step That Does Not Dominate

Swapping a list for a set removes a few thousand comparisons, while the loop over every pair beside it still makes close to a million.

Making a step faster only speeds up a solution when that step dominates its cost, so every step must be costed before any is changed. The mistake is fixing the first line that looks slow, and it feels right because that line is wasteful. A depot numbers its parcels 1 to n, parcel i weighing (37 × i) mod 101 + 1 kilograms. Ten parcels on a hold list are removed first, and then, for every remaining parcel, the depot wants how many remaining parcels are heavier. The original tests the hold list as a Python list, which scans it, the hidden cost the Analysing Complexity topic in Data Structures warns about, and compares every parcel with every other.

Three versions on 1,000 parcels: the original, the hold list made a set, and the comparison of every pair replaced by a sorted copy searched with bisect_right, which finds by halving where a weight would go among the sorted weights.

The original, the wrong fix and the right fix

parcels_original.pypy

HOLD = [3, 14, 15, 92, 65, 35, 89, 79, 32, 38]


def weight_of(number: int) -> int:
    return (37 * number) % 101 + 1


def heavier_counts(numbers: list[int], weights: list[int], hold: list[int]) -> list[int]:
    kept = [weight for number, weight in zip(numbers, weights) if number not in hold]
    return [sum(1 for j, other in enumerate(kept) if j != i and mine < other) for i, mine in enumerate(kept)]


if __name__ == "__main__":
    numbers = list(range(1, 1001))
    counts = heavier_counts(numbers, [weight_of(number) for number in numbers], HOLD)
    print("parcels kept:", len(counts))
    print("heavier than the first kept parcel:", counts[0])
    print("heavier pairs in all:", sum(counts))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

parcels kept: 990
heavier than the first kept parcel: 616
heavier pairs in all: 485189

parcels_wrong_fix.pypy

HOLD = [3, 14, 15, 92, 65, 35, 89, 79, 32, 38]


def weight_of(number: int) -> int:
    return (37 * number) % 101 + 1


def heavier_counts(numbers: list[int], weights: list[int], hold: list[int]) -> list[int]:
    held = set(hold)
    kept = [weight for number, weight in zip(numbers, weights) if number not in held]
    return [sum(1 for j, other in enumerate(kept) if j != i and mine < other) for i, mine in enumerate(kept)]


if __name__ == "__main__":
    numbers = list(range(1, 1001))
    counts = heavier_counts(numbers, [weight_of(number) for number in numbers], HOLD)
    print("parcels kept:", len(counts))
    print("heavier than the first kept parcel:", counts[0])
    print("heavier pairs in all:", sum(counts))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

parcels kept: 990
heavier than the first kept parcel: 616
heavier pairs in all: 485189

parcels_right_fix.pypy

from bisect import bisect_right

HOLD = [3, 14, 15, 92, 65, 35, 89, 79, 32, 38]


def weight_of(number: int) -> int:
    return (37 * number) % 101 + 1


def heavier_counts(numbers: list[int], weights: list[int], hold: list[int]) -> list[int]:
    kept = [weight for number, weight in zip(numbers, weights) if number not in hold]
    ordered = sorted(kept)
    return [len(ordered) - bisect_right(ordered, mine) for mine in kept]


if __name__ == "__main__":
    numbers = list(range(1, 1001))
    counts = heavier_counts(numbers, [weight_of(number) for number in numbers], HOLD)
    print("parcels kept:", len(counts))
    print("heavier than the first kept parcel:", counts[0])
    print("heavier pairs in all:", sum(counts))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

parcels kept: 990
heavier than the first kept parcel: 616
heavier pairs in all: 485189

All three give the same answers. A separate run counted their comparisons, wrapping each number in a subclass of int whose == and < add to a counter, since a time would change from run to run.

Comparisons made by each version, from the counted run
Version	Parcels	Hold-list comparisons	Ranking comparisons	Total
Original	1,000	9,955	979,110	989,065
Original	2,000	19,955	3,958,110	3,978,065
Original	4,000	39,955	15,916,110	15,956,065
Hold list as a set	1,000	10	979,110	979,120
Hold list as a set	2,000	10	3,958,110	3,958,120
Hold list as a set	4,000	10	15,916,110	15,916,120
Sorted copy	1,000	9,955	18,426	28,381
Sorted copy	2,000	19,955	40,671	60,626
Sorted copy	4,000	39,955	87,609	127,564

The set removes almost every hold-list comparison and the total barely moves: about 1% at 1,000 parcels and less as the parcels grow, because the ranking compares m(m − 1) pairs for m kept parcels. The sorted copy leaves the list scan alone and cuts the total by a factor of 35 at 1,000 parcels and 125 at 4,000, since sorting and searching cost about m log m. The check that prevents the mistake is step 1 of the procedure: cost every step first, then change the one that dominates. With the ranking fixed, the list scan is now a third of what is left, and making the hold list a set is worth doing next.

Complexity Analysis
Performance

← → move through sections and cards