Layer Reuse Ratio Across an Image Set
Problem Statement
Quantify how much a set of images benefits from shared layers by comparing the naive total (sum over all image layers) to the deduplicated total.
Background
The naive size sums every layer of every image (double-counting shared layers). The dedup size counts each digest once. The reuse ratio is 1 - dedup/naive — the fraction of bytes saved by sharing. With a naive total of 0, the ratio is 0.0.
Your Task
def reuse_ratio(images):
- images: list of images, each a list of (digest, size).
- Return the reuse ratio, rounded to 4 decimals.
Input Format
- images (list of lists of (str, int)).
Output Format
- A float rounded to 4 decimals.
Sample
print(reuse_ratio([[("a", 100)], [("a", 100)]]))
Output:
0.5
Example:
print(reuse_ratio([[("a", 100)], [("a", 100)]]))0.5
- Calculate the naive total by summing the sizes of all layers across every image, including duplicates: 100+100=200.
- Determine the dedup total by summing the size of each unique digest only once; since digest "a" appears in both images, it is counted a single time: 100.
- Compute the reuse ratio using the formula 1−naivededup​ to find the fraction of bytes saved by sharing layers: 1−200100​=1−0.5=0.5.
- Round the result to 4 decimal places as required by the problem specification: 0.5→0.5.
- The final output is 0.5
Constraints:
- naive = sum of all layer sizes (with repeats); dedup = sum over unique digests.
- ratio = 1 - dedup/naive; naive==0 -> 0.0.
- Round to 4 decimals.
1. Background Knowledge
In container image registries, images are stored as a stack of layers, each identified by a unique content-addressable digest (a hash). When multiple images share the same layer, the registry stores that layer only once on disk, but the logical size of each image still includes it. This is the foundation of layer reuse: the physical storage footprint is the union of all distinct layers, while the logical footprint is the sum across all images.
The naive total is the sum of the sizes of every layer in every image, counting shared layers multiple times. The deduplicated total is the sum of sizes of each unique digest, counted exactly once. The reuse ratio quantifies the storage savings from sharing: it is the fraction of the naive total that is eliminated by deduplication. Mathematically, if N is the naive total and D is the deduplicated total, the ratio is 1−ND​, with a special case of 0.0 when N=0 to avoid division by zero.
This metric is useful in CI/CD pipelines and registry management to understand how much disk space is saved by multi-stage builds, base image sharing, and other layer-reuse strategies.
2. Algorithm Approach
This is a set-based deduplication problem. The core idea is:
- Compute the naive total by summing all (digest, size) pairs across all images.
- Compute the deduplicated total by collecting all unique digests and summing their sizes once each.
- Apply the ratio formula with the zero-division guard.
The key data structure is a dictionary (or set) keyed by digest, which naturally handles deduplication in O(1) average lookup time.
3. Step-by-Step Strategy
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.