第6章: 最適化、テスト、検証
6.1 ソフトウェアテストの理論
Edsger Dijkstraのテスト哲学
1969年、Edsger Dijkstraは「テストはバグの存在を示すことはできるが、バグの不在を示すことはできない」という有名な洞察を述べた（"Notes on Structured Programming", 1969）。
この原理は、ソフトウェアテストの本質的な限界を示している:
テスト ≠ 証明
テスト = 反例の探索
しかし、テストには実用的な価値がある。十分な数のテストケースを実行することで、プログラムの信頼性を高めることができる。
Glenford J. Myersのテスト論
1979年、Glenford J. Myersは"The Art of Software Testing"において、テストの体系的アプローチを確立した。
Myersの定義:
テストとは、エラーを発見する目的でプログラムを実行するプロセスである
Myersは以下のテストカテゴリを定義した:
- ホワイトボックステスト: コードの内部構造を知った上でのテスト
- ブラックボックステスト: 入出力仕様のみに基づくテスト
- 境界値分析: 境界条件でのテスト
- 同値分割: 入力を等価クラスに分割
テスト駆動開発（TDD）
Kent Beckは2003年の"Test-Driven Development: By Example"において、テスト駆動開発（TDD）を体系化した。
TDDのサイクル:
Red → Green → Refactor
1. Red: 失敗するテストを書く
2. Green: テストを通す最小限のコードを書く
3. Refactor: コードを改善する
push_swapでは、各操作のテストを先に書き、次に実装を行うことで品質を保証できる。
6.2 プログラム検証の理論
Floyd-Hoare論理
1969年、C.A.R. Hoareは"An Axiomatic Basis for Computer Programming"において、プログラムの正しさを数学的に証明する方法を提案した。
Hoareトリプル:
$$\{P\} S \{Q\}$$
意味: 「Pが真の状態でSを実行すると、Qが真になる」
push_swapの操作に適用:
{stack_a.size >= 2}
sa
{stack_a[0] と stack_a[1] が交換されている}
{stack_a.size >= 1}
pb
{stack_b.size が1増加し、stack_a.size が1減少}
{stack_a.size >= 1}
ra
{旧stack_a[0] が stack_a の末尾に移動}
ループ不変条件
Dijkstraはループの正しさを証明するためにループ不変条件（loop invariant）を導入した。
push_swapのソートアルゴリズムにおける不変条件の例:
/* Turkishソートのループ不変条件 */
void turkish_sort(t_data *data)
{
/* 事前条件: data->a は未ソート */
while (data->size_a > 3)
pb(data);
sort_three(data);
/* 不変条件: data->a の3要素はソート済み */
while (data->size_b > 0)
{
/* ループ不変条件:
* - data->a は循環的にソート済み
* - data->b の各要素は data->a の適切な位置に挿入可能
*/
push_cheapest_to_a(data);
}
/* 事後条件: data->a は完全にソート済み、data->b は空 */
final_rotation(data);
}
6.3 最適化の理論
Donald Knuthの警告
1974年、Donald Knuthは"Structured Programming with go to Statements"において有名な警告を発した:
> "Premature optimization is the root of all evil (or at least most of it) in programming." > > （早すぎる最適化は諸悪の根源である）
しかし、Knuthの完全な引用は以下である:
> "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."
つまり、97%のケースでは最適化を気にせず、本当に重要な3%に集中すべきだという教えである。
最適化の階層
Michael Abrashは"Graphics Programming Black Book"（1997年）において、最適化の階層を示した:
- アルゴリズムの最適化: $O(n^2)$から$O(n \log n)$への改善など
- データ構造の最適化: 適切なデータ構造の選択
- コードの最適化: 定数倍の改善
- 低レベル最適化: キャッシュ、分岐予測など
push_swapでは、アルゴリズムの選択（チャンクソート vs 基数ソート）が最も重要な最適化である。
操作の最適化
操作列の後処理による最適化:
1. 逆操作の削除
隣接する逆操作は無意味なので削除:
ra + rra → (削除)
pa + pb → (削除)
2. 同期操作への変換
個別操作を同期操作に変換:
ra + rb → rr
rra + rrb → rrr
sa + sb → ss
3. 冗長操作の検出
n回の回転は、スタックサイズによっては逆回転の方が効率的:
stack_size = 5 の場合:
ra×3 (3操作) vs rra×2 (2操作) → rra×2 を選択
最適化の実装
/* 操作列の最適化 */
void optimize_operations(char ***ops, int *count)
{
int changed;
do {
changed = 0;
/* 逆操作の削除 */
changed |= remove_inverse_operations(ops, count);
/* 同期操作への変換 */
changed |= combine_to_simultaneous(ops, count);
/* 冗長操作の削除 */
changed |= remove_redundant_operations(ops, count);
} while (changed); /* 変更がなくなるまで繰り返す */
}
/* 逆操作の削除 */
int remove_inverse_operations(char ***ops, int *count)
{
static char *inverse_pairs[][2] = {
{"ra", "rra"}, {"rra", "ra"},
{"rb", "rrb"}, {"rrb", "rb"},
{"pa", "pb"}, {"pb", "pa"},
{NULL, NULL}
};
int i;
int j;
int changed;
changed = 0;
i = 0;
while (i < *count - 1)
{
j = 0;
while (inverse_pairs[j][0])
{
if (strcmp((*ops)[i], inverse_pairs[j][0]) == 0 &&
strcmp((*ops)[i + 1], inverse_pairs[j][1]) == 0)
{
remove_at(ops, count, i, 2);
changed = 1;
break;
}
j++;
}
if (!changed)
i++;
changed = 0;
}
return (changed);
}
/* 同期操作への変換 */
int combine_to_simultaneous(char ***ops, int *count)
{
static char *combine_pairs[][3] = {
{"ra", "rb", "rr"},
{"rb", "ra", "rr"},
{"rra", "rrb", "rrr"},
{"rrb", "rra", "rrr"},
{"sa", "sb", "ss"},
{"sb", "sa", "ss"},
{NULL, NULL, NULL}
};
int i;
int j;
int changed;
changed = 0;
i = 0;
while (i < *count - 1)
{
j = 0;
while (combine_pairs[j][0])
{
if (strcmp((*ops)[i], combine_pairs[j][0]) == 0 &&
strcmp((*ops)[i + 1], combine_pairs[j][1]) == 0)
{
free((*ops)[i]);
(*ops)[i] = strdup(combine_pairs[j][2]);
remove_at(ops, count, i + 1, 1);
changed = 1;
break;
}
j++;
}
i++;
}
return (changed);
}
6.4 テスト戦略
Mike Cohnのテストピラミッド
Mike Cohnは"Succeeding with Agile"（2009年）において、テストピラミッドの概念を提唱した:
/\
/ \ E2E テスト (少数)
/----\
/ \ 統合テスト (中程度)
/--------\
/ \ ユニットテスト (多数)
/____________\
push_swapにおけるテストピラミッド:
ユニットテスト
/* 操作のユニットテスト */
void test_sa(void)
{
int arr[] = {2, 1, 3};
t_data *data;
data = create_test_data(arr, 3);
/* 事前条件の確認 */
assert(data->a->value == 2);
assert(data->a->next->value == 1);
/* 操作実行 */
sa_silent(data);
/* 事後条件の確認 */
assert(data->a->value == 1);
assert(data->a->next->value == 2);
assert(data->a->next->next->value == 3);
free_data(data);
printf("test_sa: PASSED\n");
}
void test_pb(void)
{
int arr[] = {1, 2, 3};
t_data *data;
data = create_test_data(arr, 3);
/* 操作実行 */
pb_silent(data);
/* 事後条件の確認 */
assert(data->size_a == 2);
assert(data->size_b == 1);
assert(data->b->value == 1);
assert(data->a->value == 2);
free_data(data);
printf("test_pb: PASSED\n");
}
void test_ra(void)
{
int arr[] = {1, 2, 3};
t_data *data;
data = create_test_data(arr, 3);
/* 操作実行 */
ra_silent(data);
/* 事後条件の確認 */
assert(data->a->value == 2);
assert(data->a->next->value == 3);
assert(data->a->next->next->value == 1);
free_data(data);
printf("test_ra: PASSED\n");
}
境界値テスト
/* 境界値テスト */
void test_edge_cases(void)
{
printf("\n=== Edge Case Tests ===\n");
/* 空スタックでのsaは何もしない */
test_sa_empty();
/* 1要素のスタックでのsaは何もしない */
test_sa_single();
/* 空スタックでのpbはエラーにならない */
test_pb_empty_source();
/* INT_MAXとINT_MINの処理 */
test_extreme_values();
/* 既にソート済みの入力 */
test_already_sorted();
/* 逆順の入力 */
test_reverse_sorted();
printf("\nAll edge case tests passed!\n");
}
void test_extreme_values(void)
{
int arr[] = {INT_MIN, 0, INT_MAX};
t_data *data;
int ops;
data = create_test_data(arr, 3);
ops = execute_sort_and_count(data);
assert(is_sorted(data->a));
assert(data->size_b == 0);
free_data(data);
printf("test_extreme_values: PASSED (%d ops)\n", ops);
}
網羅的テスト（3要素）
3要素の全6パターンをテスト:
/* 3要素の全パターンテスト */
void test_all_three_permutations(void)
{
int permutations[6][3] = {
{1, 2, 3}, /* ソート済み */
{1, 3, 2},
{2, 1, 3},
{2, 3, 1},
{3, 1, 2},
{3, 2, 1} /* 逆順 */
};
int expected_ops[] = {0, 2, 1, 2, 2, 2};
int i;
t_data *data;
int ops;
printf("\n=== Three Element Permutation Tests ===\n");
i = 0;
while (i < 6)
{
data = create_test_data(permutations[i], 3);
ops = execute_sort_and_count(data);
printf("Pattern [%d, %d, %d]: ",
permutations[i][0], permutations[i][1], permutations[i][2]);
assert(is_sorted(data->a));
assert(data->size_b == 0);
if (ops <= expected_ops[i])
printf("PASSED (%d ops, expected <= %d)\n", ops, expected_ops[i]);
else
printf("FAILED (%d ops, expected <= %d)\n", ops, expected_ops[i]);
free_data(data);
i++;
}
}
ストレステスト
/* 大量データでのストレステスト */
void stress_test(int size, int iterations)
{
int i;
int ops;
int max_ops;
int total_ops;
int *arr;
int target;
printf("\n=== Stress Test: %d elements, %d iterations ===\n",
size, iterations);
max_ops = 0;
total_ops = 0;
target = (size <= 100) ? 700 : 5500;
i = 0;
while (i < iterations)
{
arr = generate_random_unique_array(size);
ops = test_and_verify(arr, size);
if (ops < 0)
{
printf("Iteration %d: FAILED (not sorted or B not empty)\n", i);
free(arr);
return;
}
total_ops += ops;
if (ops > max_ops)
max_ops = ops;
free(arr);
i++;
if ((i + 1) % 100 == 0)
printf("Progress: %d/%d completed\n", i + 1, iterations);
}
printf("\nResults:\n");
printf(" Average: %.1f operations\n", (double)total_ops / iterations);
printf(" Maximum: %d operations\n", max_ops);
printf(" Target: %d operations\n", target);
if (max_ops <= target)
printf(" Status: PASSED\n");
else
printf(" Status: FAILED (exceeded target by %d)\n", max_ops - target);
}
6.5 Checkerプログラムの理論と実装
インタプリタ設計
Checkerプログラムは、push_swap命令のインタプリタである。
インタプリタの基本構造（Abelson & Sussman, "Structure and Interpretation of Computer Programs", 1985）:
Read → Evaluate → Print → Loop (REPL)
Checkerの場合:
Read（命令を読む） → Execute（実行） → Continue → Final Check
Checkerの実装
/* checker.c */
int main(int argc, char **argv)
{
t_data *data;
char *line;
int gnl_result;
/* 引数なしなら終了 */
if (argc < 2)
return (0);
/* データ初期化 */
data = parse_and_init(argc, argv);
if (!data)
error_exit("Error\n");
/* 命令の読み取りと実行 */
while (1)
{
gnl_result = get_next_line(STDIN_FILENO, &line);
if (gnl_result <= 0)
break;
if (!execute_instruction(data, line))
{
free(line);
free_data(data);
error_exit("Error\n");
}
free(line);
}
/* 結果判定 */
if (is_sorted(data->a) && data->size_b == 0)
write(STDOUT_FILENO, "OK\n", 3);
else
write(STDOUT_FILENO, "KO\n", 3);
free_data(data);
return (0);
}
/* 命令の実行 */
int execute_instruction(t_data *data, char *inst)
{
/* 末尾の改行を除去 */
size_t len = strlen(inst);
if (len > 0 && inst[len - 1] == '\n')
inst[len - 1] = '\0';
/* 命令のディスパッチ */
if (strcmp(inst, "sa") == 0)
return (sa_silent(data), 1);
if (strcmp(inst, "sb") == 0)
return (sb_silent(data), 1);
if (strcmp(inst, "ss") == 0)
return (ss_silent(data), 1);
if (strcmp(inst, "pa") == 0)
return (pa_silent(data), 1);
if (strcmp(inst, "pb") == 0)
return (pb_silent(data), 1);
if (strcmp(inst, "ra") == 0)
return (ra_silent(data), 1);
if (strcmp(inst, "rb") == 0)
return (rb_silent(data), 1);
if (strcmp(inst, "rr") == 0)
return (rr_silent(data), 1);
if (strcmp(inst, "rra") == 0)
return (rra_silent(data), 1);
if (strcmp(inst, "rrb") == 0)
return (rrb_silent(data), 1);
if (strcmp(inst, "rrr") == 0)
return (rrr_silent(data), 1);
/* 不正な命令 */
return (0);
}
push_swapとcheckerの統合テスト
# 基本テスト
ARG="4 67 3 87 23"; ./push_swap $ARG | ./checker $ARG
# ランダムテスト（100要素）
ARG=$(ruby -e "puts (1..100).to_a.shuffle.join(' ')"); \
./push_swap $ARG | ./checker $ARG
# 操作数カウント
ARG=$(ruby -e "puts (1..100).to_a.shuffle.join(' ')"); \
./push_swap $ARG | wc -l
6.6 プロファイリングとデバッグ
時間計測
#include <sys/time.h>
typedef struct s_timer {
struct timeval start;
struct timeval end;
} t_timer;
void timer_start(t_timer *t)
{
gettimeofday(&t->start, NULL);
}
double timer_stop(t_timer *t)
{
gettimeofday(&t->end, NULL);
return (t->end.tv_sec - t->start.tv_sec) * 1000.0 +
(t->end.tv_usec - t->start.tv_usec) / 1000.0;
}
/* プロファイリング */
void profile_sort(int size, int iterations)
{
t_timer timer;
double total_ms;
int i;
total_ms = 0;
printf("Profiling %d elements, %d iterations...\n", size, iterations);
i = 0;
while (i < iterations)
{
int *arr = generate_random_unique_array(size);
t_data *data = create_test_data(arr, size);
timer_start(&timer);
execute_sort(data);
total_ms += timer_stop(&timer);
free_data(data);
free(arr);
i++;
}
printf("Total time: %.2f ms\n", total_ms);
printf("Average time: %.2f ms per sort\n", total_ms / iterations);
}
メモリリーク検出
Valgrindを使用したメモリチェック:
# 基本チェック
valgrind --leak-check=full ./push_swap 3 2 1
# 詳細チェック
valgrind --leak-check=full --show-leak-kinds=all \
--track-origins=yes ./push_swap $(shuf -i 1-100 -n 100 | tr '\n' ' ')
ビジュアライザー
/* テキストベースのビジュアライザー */
void visualize_stacks(t_data *data)
{
t_stack *a;
t_stack *b;
int max_height;
int i;
max_height = data->size_a > data->size_b ? data->size_a : data->size_b;
printf("\n");
printf("Stack A | Stack B\n");
printf("-----------+-----------\n");
a = data->a;
b = data->b;
i = 0;
while (i < max_height)
{
if (a)
{
printf("%10d |", a->value);
a = a->next;
}
else
printf(" |");
if (b)
{
printf(" %d\n", b->value);
b = b->next;
}
else
printf("\n");
i++;
}
printf("-----------+-----------\n");
printf("Size: %d | Size: %d\n\n", data->size_a, data->size_b);
}
6.7 評価基準と最終チェック
42の評価基準
3要素: 最大2-3操作
5要素: 最大12操作
100要素:
- 5点: 700操作以下
- 4点: 900操作以下
- 3点: 1100操作以下
- 2点: 1300操作以下
- 1点: 1500操作以下
500要素:
- 5点: 5500操作以下
- 4点: 7000操作以下
- 3点: 8500操作以下
- 2点: 10000操作以下
- 1点: 11500操作以下
最終チェックリスト
基本機能:
[ ] push_swap がコンパイルできる
[ ] checker がコンパイルできる（ボーナス）
[ ] Makefile が all, clean, fclean, re を提供
エラー処理:
[ ] 数値以外の引数 → "Error\n"
[ ] INT範囲外 → "Error\n"
[ ] 重複 → "Error\n"
[ ] 引数なし → 何も出力せず終了
メモリ管理:
[ ] valgrind でメモリリークなし
[ ] すべてのmallocにNULLチェック
コード品質:
[ ] Norminette に準拠
[ ] 関数が25行以内
[ ] グローバル変数なし
6.8 まとめ
本章では、ソフトウェア品質保証の理論と実践を学んだ:
- テスト理論: Dijkstraのテスト哲学、Myersのテスト分類、TDD
- 検証理論: Floyd-Hoare論理、ループ不変条件
- 最適化理論: Knuthの警告、最適化の階層、操作の最適化
- テスト実装: ユニットテスト、境界値テスト、ストレステスト
- Checker実装: インタプリタ設計、命令ディスパッチ
- プロファイリング: 時間計測、メモリチェック
- Dijkstra, E. W. (1969). "Notes on Structured Programming", EWD249
- Hoare, C. A. R. (1969). "An Axiomatic Basis for Computer Programming", Communications of the ACM, 12(10)
- Myers, G. J. (1979). "The Art of Software Testing", John Wiley & Sons
- Knuth, D. E. (1974). "Structured Programming with go to Statements", Computing Surveys, 6(4)
- Beck, K. (2003). "Test-Driven Development: By Example", Addison-Wesley
- Cohn, M. (2009). "Succeeding with Agile", Addison-Wesley
- Abelson, H., & Sussman, G. J. (1985). "Structure and Interpretation of Computer Programs", MIT Press
- Abrash, M. (1997). "Graphics Programming Black Book", Coriolis Group
これでpush_swapプロジェクトのガイドは完了である。本ガイドで学んだ理論的背景とアルゴリズムの知識を活用し、効率的で正しいソートプログラムを実装してほしい。
---