20260526_3

20260519_3

---

プログラムの実行性能

• 計算量はプログラムの実行に要する計算資源の量
• CPU側ではクロックの向上
• メモリは遅い
  • キャッシュを利用する
  • パイプライン
    • スーパースカラ
      • 複数のパイプラインを用意して、実行依存度の少ない命令を並列実行する
      • コンパイラの最適化と協議
  • 分岐予測
    • 当分結果の変わらないようなところは省く
  • マルチコア
  • →メインメモリの遅さを隠蔽する

どうしてまだ遅い？

• データキャッシュミス

  • キャッシュに収まりきらない大きなデータを扱っている
  • 局所性の不足(様々なデータが散らばっている)

• パイプラインハザード

  • 予測したのと違うやつが実行される

• 小さな関数を多数呼び出す

  • スタックやレジスタの退避が重くなる

• コンピュータにとって関数呼び出しのコストは低くない

  • キャッシュミスの可能性
  • スタックの操作(コールスタックの構成/レジスタの退避)

• プログラムの最適化

  • 実行時間を変えずに何らかの基準でプログラムの動作をマシにする
    • 実行時間？
    • 電力？
    • 処理の回数？

例としては定数の畳み込みやループ展開など

再帰呼び出しの除去

• 再帰の良さ
  • 複雑なアルゴリズムをシンプルにできる
  • コードが短くなる
• 計算機には負担

• 再帰呼び出しの除去
• 末尾呼び出し(関数の最後が再帰呼び出しであるケース)
  • 引数の変化や戻り値の蓄積を行うとループに読み替えられる

int fact(int n){
	if(n==0){
		return 1;
	}else{
		return n*fact(n-1);
	}
}

を

int fact(int n){
	int val=1;
	while(n != 0){
		val *=n;
		n -=1
	}
}

このようになる
これは簡単に除去できるためコンパイラ側で処理をしてくれる

逆に、データが配列になっていて、末尾にアクセスできる場合には末尾再帰にできる

whileで再帰を除去することも可能

goto文←使えなくなないがやめとけ

• 末尾再帰でない場合
• 10進数を16進数に変換する
  • 10進数を16で割ったあまりが一番下の桁になる
  • 商をもう一度割ることでもう一桁出てくる
  • しかし、一番最初の桁が最後に出てきてしまう

void tohex(int x){
	if(x>=16){
		tohex(x/16);
	}
	printf("%c",hex[x%16]);//終端条件
}

実効順を入れ替えたい(配列に桁の内容を持っておけばよさそう)

ここではスタックを利用する
スタックに桁の内容を格納し、取り出したときに数を読み出せる

whileを二回やる

演算子の優先順位

*c++はc++したあとにポインタをとる
(*c)++は*cを1増す
→後置演算子のほうが単項演算子よりも強い