基本的なガイダンス

情報構造論のシラバスを、ここに示す。プログラムを作成する上で、どのような考え方で作れば処理速度が速いのかを議論する。基本的に、4回のテストのたびに、レポート課題を実施する。各テスト毎の評価は、テスト素点と、「テスト素点×60%+レポート評価×40%」の良い方とする。テストに自信のない人は、レポート課題をきちんと提出すること。

• 情報構造論の講義録は、すべてこの BLOG に残します。
• 過去のテスト問題は、こちらにすべて残ってます。

プログラムを評価する3つのポイント

まずは以下を読む前に、質問。

• あなたが”良い”プログラムを作るために何を考えて作りますか？ ※1
  • ここまでの段階で3つの要点を考えメモしてください。

具体的な言葉で要点を考えると、いろいろなものがでてくるだろうが、端的なポイントにまとめると、次の3つに分類できるはずである。

• プログラムの速度
• プログラムのわかり易さ
• メモリの使用量

プログラムを作る場合、この３要素がトレードオフの関係にある。プログラムの速度を優先すると、プログラムが分かり難くなったり、メモリを大量浪費するものだったりする。

メモリの使用量の影響

メモリを大量に使用すると、どういった影響がでるのか？ OSの機能を知らないと、メモリ(主記憶)を使い果たしたら、プログラムが動かないと思うかもしれないけど、最近のOSは仮想メモリ機能があるため、主記憶がメモリが足りなければ待機状態のプロセスのメモリを補助記憶に保存することで、プログラムを動かすことはできる。(仮想記憶)

しかし、プロセスが切り替わる度に、補助記憶への読み書きが発生するため、処理性能は低下する。(スワッピング)

int 型のメモリ使用量は？

int 型は、プログラムで扱う一般的な整数を扱うのに十分なデータ型。

32bit の0/1情報の組み合わせで、2³²通りの情報が表現でき、負の数も扱いたいことから2の補数表現を用いることで、-2³¹～0～2³¹-1 の範囲を扱うことができる。2³¹ = 2×2¹⁰×2¹⁰×2¹⁰ ≒ 2×1000³

32bit = 4byte

ソフトウェアとアルゴリズムとプログラム

用語として、ソフトウェア、アルゴリズム、プログラムという表現があるが、この違いは何か？

• アルゴリズム – 計算手順の考え方。
• プログラム – アルゴリズムを特定のプログラム言語によって記述したもの。
• ソフトウェア – プログラムと、その処理に必要なデータ。
  (日本語を変換するプログラムは、日本語の辞書データが無いと動かない/役に立たない)
• パラダイム – プログラムをどう表現すると分かりやすいか？

トレードオフ関係をプログラムで確認

例えば、配列の中から、目的データを探すプログラムの場合、最も簡単なプログラムは以下の方法であろう。

// ((case-1))
// 単純サーチ O(N)
#define SIZE 1024
int main() {
   int a[ SIZE ] = {
      52 , 14 , 82 , 62 , 15
   } ; // 配列
   int size =  5 ;      // 実際のデータ数(Nとする)
   int key  = 62 ;      // 探すデータ
   for( int i = 0 ; i < size ; i++ ) // 先頭から1つづつ比較、シンプル
      if ( a[i] == key ) {
         printf( "Find %d¥n" , key ) ;
         break ;
      }
   }
}

import java.util.*;

public class Main {
   public static void main(String[] args) throws Exception {
      int a[] = {
         52 , 14 , 82 , 62 , 15
      } ;
      int key = 62 ;
      for( int i = 0 ; i < a.length ; i++ ) {
          if ( a[i] == key ) {
             System.out.println( "Find " + key ) ;
             break ;
          }
      }
   }
}

// import java.util.Arrays;  // こういった正当なJavaのプログラムでは、
// public class Main {       // データ件数が大きくなった時の挙動がわからない
//    public static void main( String[] args ) {
//       Integer a[] = {
//          52 , 14 , 82 , 62 , 15    // Integer型 int 型は何が違うの？
//       } ;
//       if ( Arrays.asList( a ).contains( 62 ) ) {
//          System.out.println("配列内に値が存在しています。");
//       }
//    }
// }

しかし、もっと早く探したいのであれば、2分探索法を用いるだろう。でも、このプログラムは、case-1 のプログラムよりは分かり難い。(速度⇔わかり易さ)

// ((case-2))
// 2分探索法 O(log N)
// 速いけど、プログラムは分かりにくく(複雑に)なった
int main() {
   int a[] = {
      14 , 15 , 52 , 62 , 82  // データはあらかじめ昇順に並べておく
   } ; 
   int L=0 , R= 5 ; 
   while( L != R ) {
      int M = (L + R) / 2 ;
      if ( a[M] == key )
         break ;
      else if ( a[M] < key )
         L = M + 1 ;
      else
         R = M ;
   }
}

import java.util.*;

public class Main {
   public static void main(String[] args) throws Exception {
      int a[] = {
         14 , 15 , 52 , 62 , 82  // データはあらかじめ昇順に並べておく
      } ;
      int key = 62 ;
      int L = 0 ;
      int R = a.length ;
      while( L != R ) {
         int M = (L + R) / 2 ;
         if ( a[M] == key )
            break ;
         else if ( a[M] < key )
            L = M + 1 ;
         else
            R = M ;
      }
   }
}

でももっと速いプログラムとしたければ、大量のメモリを使えば一発でデータを探せる。(速度⇔メモリ使用量)

// ((case-3))
// 添字がデータ O(1)
// 探すデータが電話番号 272925 のような 6 桁ならば、データを以下の様に保存すればいい。
int a[ 1000000 ] ;
a[ 272925 ] = 272925 ;
：
// データを探したければ a[ 電話番号 ] で探せばいい
printf( "%d\n" , a[ 621111 ] ) ;
// 処理速度はクソ速いけど、メモリは大量消費

良いプログラムを作るとは

プログラムを作る時には、メモリが大量に使えるのなら、速いものを使えばいい。だけど実際には、そのシステムには限られた予算があるだろう。

実際には、限られた予算からメモリやCPUが決まり、その会社の人員やら経験やらでプログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。

皆さんも、ゲームを買った時、処理速度が遅くてキャラクターがカクカク動いたら幻滅するでしょ？ゲームがバグですぐに変な動きしたらキレるでしょ！(参考) 発売日の予定どおりに買えなかったらさみしいでしょ!!プログラムがでかすぎてローディングに時間がかかったら、寝ちゃうでしょ!!!