Find and Fix a Hidden Quadratic with Doubling Experiments

Goal

Using doubling experiments that measure while doubling the input, you will separate the growth rates of five functions, fix the most common hidden quadratic (deduplication) while preserving order, prove the improvement with the distribution of repeated measurements, and extrapolate the time at the target size.

Why it matters

Even a quadratic function is fast on small input, so the tests pass and it becomes slow only in production. A number measured once cannot be told apart from a single piece of noise, and a judgment based only on the shape of the code misses a one-line in. So you measure repeatedly while changing the size, state the growth rate as a ratio of minimums, and state the improvement through the median and whether the distributions overlap. The grader looks at the time itself only within a wide band, and checks exactly whether the medians and ratios you wrote came from your own samples and whether the function you improved gives the same answer as the original.

Materials

They are under /opt/fixtures/svccs/measure/. Only read them.

suspects.py   함수 다섯 개(dedupe · newest_first · pack · flag_known · window_pairs)
              SUSPECTS[이름] → 함수, make_input(이름, n, seed=0) → 크기 n 의 입력(고정 시드)
params.json   sizes(함수마다 잴 네 크기, 두 배씩) · repeat_min(최소 반복 수 5)
              compare_sizes(7단계 크기) · target_n · budget_s(8단계 외삽 목표와 예산, 초)

How to import: after sys.path.insert(0, "/opt/fixtures/svccs/measure"), run import suspects.

Steps

1. In /root/svccs/measure/clock.json, record the properties of the two clocks, perf_counter and time. Each is {"monotonic", "adjustable", "resolution", "implementation"}, and the values are exactly what time.get_clock_info(이름) returns (with the clock name as the argument). Then record the clock you will use to measure intervals in "choice", as "perf_counter" or "time".
2. In /root/svccs/measure/bench.py, create time_it(fn, make_input, n, repeat=7). For each repetition, build the input fresh with data = make_input(n), and after that measure with time.perf_counter() the time of one call to fn(data). It returns {"n", "repeat", "samples"(초 목록, 길이 repeat), "median"(statistics.median), "min"} (samples is the list of seconds with length repeat, and median is statistics.median).
3. For each function listed in params.json under sizes, measure its four sizes in order with time_it at least 5 times, and write them to /root/svccs/measure/doubling.json as {"functions": {이름: [{"n", "samples", "median", "min"}, …]}} (keyed by the function name). The input is suspects.make_input(이름, n).
4. In /root/svccs/measure/ratios.json, write {"ratios", "ratio", "exponent"} for each function. ratios is the three ratios obtained by dividing the mins of adjacent sizes (starting from the smaller n, to three decimal places), ratio is the median of those three ratios before rounding (to three decimal places), and exponent is log2(ratio) (to two decimal places).
5. In /root/svccs/measure/classes.json, classify the five functions as "linear" or "quadratic" (for example, {"dedupe": "…", …}).
6. In /root/svccs/measure/fixed.py, create dedupe_fast(items). It must return the same values in the same order as suspects.dedupe, but in linear time. It must not modify the list it receives, and it must also accept hashable values that are not strings.
7. For each size in compare_sizes, measure suspects.dedupe (before) and fixed.dedupe_fast (after) at least 5 times each with the same input generator (make_input("dedupe", n)), and write them to /root/svccs/measure/compare.json as {"rows": [{"n", "before": {"samples", "median"}, "after": {"samples", "median"}, "speedup", "separated"}]}. speedup is the before median divided by the after median (to two decimal places), and separated is whether the largest sample of after is smaller than the smallest sample of before (true/false).
8. Write the extrapolation in /root/svccs/measure/forecast.json. Use the row with the largest n from step 7. exponent_before is the dedupe exponent from step 4, before_s = before 중앙값 × (target_n ÷ n) ** exponent_before (the before median times the scaling factor raised to the exponent, to three decimal places), after_s = after 중앙값 × (target_n ÷ n) (the after median times the scaling factor, to five decimal places), fits_before·fits_after are whether each is at most budget_s, and write target_n·budget_s as they are.

Notes

• The measurement happens while the Pod shares the CPU with other work. If you see "the measurement does not support the classification" in step 5, measure again from step 3.
• The grader imports bench.py·fixed.py. Put executable code under if __name__ == "__main__": or in a separate script.
• Common mistakes: including input building in the time, measuring only once, writing the mean in the place of the median, and losing the order by replacing deduplication with set().
• The outputs disappear when the session ends. Keep them elsewhere if you need them.

Choose the clock for measuring intervals

Use time.get_clock_info to write the monotonic, adjustable, resolution, and implementation of the two clocks, perf_counter and time, to /root/svccs/measure/clock.json, and write the clock to use for interval measurement in choice.

Just copy over the four attributes of the object that time.get_clock_info('perf_counter') returns. A clock whose adjustable is true can also go backward when NTP or an administrator sets the clock back, so the difference between two readings can be negative.

A measuring tool that repeats

Create time_it(fn, make_input, n, repeat=7) in /root/svccs/measure/bench.py. The grader passes in a slow make_input and a short fn to check whether the input is rebuilt on every repetition and whether the input-building time is excluded from the time.

Read the clock after make_input finishes, just before calling fn. The median is statistics.median and the minimum is min. If you reuse the same input several times, a function that modifies its input does different work from the second time on.

Measure while doubling the input

Measure the five functions in sizes of params.json at four sizes each with time_it, at least 5 times, and write them to /root/svccs/measure/doubling.json as functions → name → [{n, samples, median, min}].

Build the input with suspects.make_input(name, n). When you pass it as a lambda, if you do not bind the loop variable name as a default argument, every lambda sees the last name. A quadratic function at the largest size can take close to 1 second per call.

Read the exponent from the ratios

From doubling.json, for each function write the three ratios obtained by dividing the mins of adjacent sizes, their median, and the log2 exponent to /root/svccs/measure/ratios.json. The grader recomputes from your samples with the same rule and compares.

Since t(2n)/t(n) ≈ 2^k, k = log2(ratio). math.log is the natural logarithm, so use math.log2. The reason to use min when looking at growth rates is in the timeit documentation: the large values are usually interference from other processes.

Separate linear from quadratic

Classify the five functions as linear or quadratic and write them to /root/svccs/measure/classes.json. The grader compares against the designed answer, and also checks whether your measurements support that classification within a wide band.

A ratio near 2 is linear and near 4 is quadratic. Do not judge by the shape of the code: even a double loop is linear if the inner loop runs a constant number of times, and a one-line in, insert(0, x), or repeated concatenation hides a quadratic.

Fix the deduplication while preserving order

Create dedupe_fast(items) in /root/svccs/measure/fixed.py. The grader checks, on variant inputs, whether it gives the same values in the same order as the original, whether the number of == calls is proportional to the input, and whether the time does not grow quadratically at 200,000 items.

If you ask "have I seen this already?" of a hash-based structure instead of a list, it becomes linear. A set is an unordered collection, so the result order changes. A dict preserves insertion order (part of the language specification since 3.7).

Prove the improvement with a distribution

For each size in compare_sizes, measure dedupe and dedupe_fast at least 5 times each with the same input generator, and write the before and after samples, the medians, speedup, and separated to /root/svccs/measure/compare.json.

A pair of means gets pulled by a single outlier sample. That the two distributions do not overlap (the slowest value of after < the fastest value of before) is the easiest evidence that it is not noise.

Extrapolate to the target size and compare with the budget

Using the dedupe exponent from step 4 and the median at the largest n from step 7, extrapolate the before and after times at target_n, write them to /root/svccs/measure/forecast.json, and compare them with budget_s.

t(target) ≈ t(n) × (target ÷ n)^k. For the after case, you confirmed in step 6 that it is linear (k = 1). Extrapolation rests on the assumption that the same growth rate continues, so read the result as "roughly how many orders of magnitude."