2025年11月8日
今週の活動
- 前回までにレビュー労力測定手法を考えたが、レビュー対象となる全てのコミットの労力が等しいと仮定していた
- しかし、実際は労力（コスト）に対するバグ混入確率（リターン）が最大となるようなコミットを優先的にレビューするはずであり、先ほどの実装は不適切
- そこで、コストとリターンの両方を考慮したレビュー労力測定手法を検討
- コミットのレビューをナップサック問題に変換
- アイテム: レビュー待ちの各コミット\(i\)
- アイテムの数\(N\): レビュー待ちの全てのコミット数
- アイテムの重さ\(W_i\): コミット\(i\)のレビューに必要な労力
- アイテムの価値\(V_i\): コミット\(i\)のレビューによるバグ発見期待値（メソッドの陽性確率）
- ナップサックの容量\(C_{total}\): レビューに使える総労力
- 解くべき問題: レビュー労力の合計が \(C_{total}\) を超えないように、レビューするコミットの組み合わせを選び、そのバグ発見期待値の合計 \(V_{total}\) を最大化
- 労力の計算に用いる指標
- 変更コード行数（コードチャーン）
- 変更ファイル数
- Entropy
- 正規化前: \(H(P) = -\sum_{k=1}^{n} p_k \log_2 p_k\)
- \(n\): 変更されたファイル数
- \(p_k\): ファイル\(k\)が変更全体に占める割合
- \(p_k = \frac{\text{file}_k \text{の変更行数}}{\text{全変更行数}}\)
- \(\sum_{k=1}^{n} p_k = 1\)
- 正規化後: \(\text{Entropy} = \frac{H(P)}{\log_2 n}\)
- 0から1の範囲に正規化
- ファイル数が異なる変更同士を比較可能にする
- 具体例
- ファイルA, B, Cを変更した場合（A: 30行, B: 20行, C: 10行）:
- \(\begin{align} p_A &= \frac{30}{60} = 0.5 \\ p_B &= \frac{20}{60} = 0.333 \\ p_C &= \frac{10}{60} = 0.167 \end{align}\)
- \(\begin{align} H(P) &= -(0.5 \log_2 0.5 + 0.333 \log_2 0.333 + 0.167 \log_2 0.167) \\ &= -(0.5 \times (-1) + 0.333 \times (-1.585) + 0.167 \times (-2.585)) \\ &= -(-0.5 - 0.528 - 0.432) \\ &= 1.46 \end{align}\)
- \(\text{Entropy} = \frac{1.46}{\log_2 3} = \frac{1.46}{1.585} \approx 0.92\)
得られた成果
- ナップサック問題の整理と解法の検討
- ナップサック問題: 整数計画問題のうち、0-1整数計画問題に分類されるもの
- 貪欲法
- 近似解を求める
- 計算時間が容量に依存しない
- ソートが必要な場合の計算量は\(O(N\log{N})\)
- 動的計画法
- 最適解を求める
- 容量が大きいほどと計算時間が増加
- 計算量は\(O(NW)\)
- レビューの場合は「容量 = レビューに使える総労力」になるため、解の算出に時間がかかりすぎる可能性が高い
来週の計画
- 貪欲法と動的計画法の2通りを試し、より良い方を見つける
- 選んだアルゴリズムを用いて労力考慮型のレビュー労力測定手法を実装