プログラムの動的解析 - software engineering.pdfVIP

プログラミング技法 第6回演習 資料は http://www-hiraki.is.s.u-tokyo.ac.jp/lectures/prog_giho/ プログラム高速化のまとめ 1 今日の課題 • 行列積のプログラム、またはバブルソートではな いソートのプログラムを出来るだけ高速化せよ – 高速化前のプログラムに（コンパイラの最適化オプ ション以外の）高速化を施し、実行時間差を表にまと める。 – 注意：高速化しやすいように最初のプログラムに駄 目プログラムを使わないように 2 レポート課題のまとめ 課題１：スタックの総和を求める 課題２：行列積を求める 課題３：バブルソートより速いソートを実現 課題４：行列積またはソートの高速化 提出方法：学籍番号、氏名を付けて proggiho-report@hiraki.is.s.u-tokyo.ac.jp まで送付 締め切りは全てのレポートについて学期末まで。 3 課題１ • 十分に大きい配列（例えば1000万要素）を取り スタックとして使う。つまり、操作する場所をスタ ックポインタとしてもつ。 • まず、配列にランダムまたは連続数で順次書き 込む（プッシュ操作）。 • 次に配列を一番最近書き込んだものから順次 読み出し総和を得る。 • 配列サイズを16から2倍づつ大きくしたときの要 素あたりの実行時間変化をリストまたはグラフと して求めよ。 4 課題２ • 十分に大きい2個の行列の行列積を求め、別の 行列として作成するプログラムを作成する。 • 行列サイズを順次大きくし、演算あたりの実行 時間変化をリストまたはグラフとして求めよ。 5 課題3 • アルゴリズムを変えて、バブルソートより速くす る。 2 • バブルソートは計算回数がO(n )の遅いアルゴリ ズム • 良く知られている速いアルゴリズムは – Quick Sort – Merge Sort – Radix Sort などいろいろある。 • 本やWebページで探して、実装して速度比較 6 課題４ • 行列積のプログラム、またはバブルソートではな いソートのプログラムを出来るだけ高速化せよ – 高速化前のプログラムに（コンパイラの最適化オプ ション以外の）高速化を施し、実行時間差を表にまと める。 – 注意：高速化しやすいように最初のプログラムに駄 目プログラムを使わないように