TT Lab
はじめる
学ぶ 学習パス コース

良いサービスを作る CS — 教科書の概念を計測で学び直す

倍化実験で隠れた二次を見つけて直す

TT Labで続きを見る

目標

入力を2倍ずつ増やして測る倍増実験で、関数5つの増加率を分け、もっとも一般的な隠れた二次(重複除去)を順序を保ちながら直したあと、改善を反復測定の分布で証明し、目標サイズでの時間を外挿します。

なぜ重要なのか

小さな入力では二次の関数も速いので、テストは通るのに、本番でだけ遅くなります。1回測った数字はノイズ1つと区別できず、コードの形だけを見た判断は、1行のinを見逃します。そのため、サイズを変えながら繰り返し測り、増加率は最小値どうしの比率で、改善は中央値と分布の重なりで語ります。採点ツールは、時間そのものは広い帯でしか見ず、書いた中央値・比率が自分のサンプルから出たものかどうかと、改善した関数が元の関数と同じ答えを出すかどうかを、正確に確認します。

用意するもの

/opt/fixtures/svccs/measure/の下にあります。読み取り専用で使ってください。

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단계 외삽 목표와 예산, 초)

このコードブロックの韓国語の説明は、順に、suspects.pyには関数が5つあり、SUSPECTSは名前から関数への対応でmake_inputは固定シードでサイズnの入力を作ること、params.jsonには、sizes(関数ごとに測る2倍ずつの4つのサイズ)・repeat_min(最小の反復回数は5)・compare_sizes(ステップ7のサイズ)・target_nとbudget_s(ステップ8の外挿の目標とバジェット、単位は秒)が入っていること、を述べています。

読み込み方: sys.path.insert(0, "/opt/fixtures/svccs/measure")のあとにimport suspectsを実行します。

ステップ

  1. /root/svccs/measure/clock.jsonに、perf_counterとtimeの2つの時計の性質を書きます。それぞれ{"monotonic", "adjustable", "resolution", "implementation"}で、値はtime.get_clock_info(이름)の結果そのままです(プレースホルダーは時計の名前です)。そして、区間を測る時計を"choice"に、"perf_counter"または"time"として書きます。
  2. /root/svccs/measure/bench.pyにtime_it(fn, make_input, n, repeat=7)を作成します。反復ごとにdata = make_input(n)で入力を新しく作り、そのあとにtime.perf_counter()を使ってfn(data)1回分の時間を測ります。{"n", "repeat", "samples"(초 목록, 길이 repeat), "median"(statistics.median), "min"}を返します(韓国語で「秒のリスト」と「長さ」を意味する語です)。
  3. params.jsonのsizesにある関数ごとに、その4つのサイズを順番にtime_itで5回以上測り、/root/svccs/measure/doubling.jsonに{"functions": {이름: [{"n", "samples", "median", "min"}, …]}}の形式で書きます。入力はsuspects.make_input(이름, n)で作ります(プレースホルダーは関数の名前です)。
  4. /root/svccs/measure/ratios.jsonに、関数ごとに{"ratios", "ratio", "exponent"}を書きます。ratiosは、隣り合う2つのサイズのminどうしを割った比率3つ(小さいnから、小数第3位)、ratioはその3つの比率(丸める前)の中央値(小数第3位)、exponentはlog2(ratio)(小数第2位)です。
  5. /root/svccs/measure/classes.jsonに、5つの関数を"linear"または"quadratic"に分類して書きます(例: {"dedupe": "…", …})。
  6. /root/svccs/measure/fixed.pyにdedupe_fast(items)を作成します。suspects.dedupeと同じ値を同じ順序で返し、かつ線形である必要があります。受け取ったリストを変更せず、文字列以外のハッシュ可能な値も受け付ける必要があります。
  7. compare_sizesのサイズごとに、suspects.dedupe(before)とfixed.dedupe_fast(after)を、同じ入力ジェネレーター(make_input("dedupe", n))でそれぞれ5回以上測り、/root/svccs/measure/compare.jsonに{"rows": [{"n", "before": {"samples", "median"}, "after": {"samples", "median"}, "speedup", "separated"}]}の形式で書きます。speedupはbeforeの中央値÷afterの中央値(小数第2位)、separatedはafterの最大のサンプルがbeforeの最小のサンプルより小さいかどうか(true/false)です。
  8. /root/svccs/measure/forecast.jsonに外挿を書きます。ステップ7の最大のnの行を使い、exponent_beforeはステップ4のdedupeの指数、before_s = before 중앙값 × (target_n ÷ n) ** exponent_before(小数第3位)、after_s = after 중앙값 × (target_n ÷ n)(小数第5位)とします(コード内の韓国語は、どちらも「中央値」を意味する語です)。fits_before・fits_afterはそれぞれbudget_s以下かどうか、そしてtarget_n・budget_sはそのまま書きます。

参考

区間を測る時計を選ぶ

time.get_clock_infoでperf_counterとtimeの2つの時計のmonotonic・adjustable・resolution・implementationを/root/svccs/measure/clock.jsonに書き、区間の測定に使う時計をchoiceに書いてください。

time.get_clock_info('perf_counter')が返すオブジェクトの4つの属性を、そのまま書き写せば十分です。adjustableがtrueの時計は、NTPや管理者が時刻を戻したときに、一緒に後ろへ戻ることがあるため、2回読んだ値の差が負になることがあります。

繰り返し測る測定ツール

/root/svccs/measure/bench.pyにtime_it(fn, make_input, n, repeat=7)を作成してください。採点ツールが、遅いmake_inputと短いfnを渡して、入力を反復ごとに新しく作っているかどうかと、入力の作成を時間から除いているかどうかを確認します。

時計は、make_inputが終わったあと、fnを呼び出す直前に読みます。中央値はstatistics.median、最小値はminです。同じ入力を何回も使うと、入力を書き換える関数は、2回目から別の動作をすることになります。

入力を2倍ずつ増やして測る

params.jsonのsizesにある5つの関数を、4つのサイズずつtime_itで5回以上測り、/root/svccs/measure/doubling.jsonにfunctions → 名前 → [{n, samples, median, min}]の形式で書いてください。

入力はsuspects.make_input(名前, n)で作ります。ラムダで渡すとき、ループ変数nameをデフォルト引数に束縛しないと、すべてのラムダが最後の名前を参照します。もっとも大きいサイズの二次の関数は、1回に1秒近くかかることがあります。

比率から指数を読み取る

doubling.jsonから、関数ごとに隣り合うサイズのminどうしを割った比率3つ、その中央値、log2の指数を、/root/svccs/measure/ratios.jsonに書いてください。採点ツールは、あなたのサンプルから同じルールで再計算して突き合わせます。

t(2n)/t(n) ≈ 2^kなので、k = log2(比率)です。math.logは自然対数なので、math.log2を使います。増加率を見るときにminを使う理由は、timeitのドキュメントにあります。大きい値はたいてい、別のプロセスの干渉です。

線形と二次を分ける

5つの関数をlinearまたはquadraticに分類して、/root/svccs/measure/classes.jsonに書いてください。採点ツールは、設計上の正解と突き合わせ、あなたの測定がその分類を広い帯の範囲内で裏づけているかどうかも確認します。

比率が2の近くなら線形、4の近くなら二次です。コードの形で判断しないでください。二重のループでも、内側が定数回なら線形であり、1行のin・insert(0, x)・繰り返しの連結が、二次を隠しています。

順序を保ちながら重複除去を直す

/root/svccs/measure/fixed.pyにdedupe_fast(items)を作成してください。採点ツールは、変形した入力で元の関数と同じ値・同じ順序になるか、==の呼び出し回数が入力に比例するか、20万個で時間が二次で増えないかを確認します。

「すでに見たか」を、listではなくハッシュベースの構造に問い合わせると、線形になります。setは順序のないコレクションなので、結果の順序が変わります。dictは挿入順序を保ちます(3.7から言語仕様)。

改善を分布で証明する

compare_sizesのサイズごとに、dedupeとdedupe_fastを同じ入力ジェネレーターで5回以上測り、/root/svccs/measure/compare.jsonにbefore・afterのサンプルと中央値、speedup、separatedを書いてください。

平均1組は、外れ値のサンプル1つに引きずられます。2つの分布が重ならないこと(afterのもっとも遅い値 < beforeのもっとも速い値)が、「ノイズではない」ことのもっとも簡単な証拠です。

目標サイズに外挿してバジェットと比べる

ステップ4のdedupeの指数と、ステップ7の最大のnの中央値を使って、target_nでの改善前後の時間を外挿し、/root/svccs/measure/forecast.jsonに書いて、budget_sと比べてください。

t(target) ≈ t(n) × (target ÷ n)^kです。改善後は、ステップ6で線形(k = 1)であることを確認しました。外挿は同じ増加率が続くという仮定なので、結果は「おおよそ何桁の数か」として読んでください。