情報構造論のガイダンス

プログラム作成でのポイント

この授業で恒例の、プログラムを作る場合に何に気をつけてプログラムを作成するかを聞いてみた。今年は、以下に示す3要素をうまく答えてくれたかな。

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

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

プログラム例

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

// ((case-1))
// 単純サーチ　O(N)
#define SIZE 1024
int a[ SIZE ] ; // 配列
int size ;      // 実際のデータ数(Nとする)
int key ;       // 探すデータ
for( int i = 0 ; i < size ; i++ )
   if ( a[i] == key )
      break ;

しかし、もっと早く探したいのであれば、2分探索法を用いるだろう。

// ((case-2))
// 2分探索法　O(log N)
int L=0 , R=size ; // プログラムは複雑になった 
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[ key ] に保存
// 処理速度はクソ速いけど、メモリは大量消費

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

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

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

動作時間の予測

ここで、プログラムの実行時間を細かく分析してみる。例えば、前節のcase-1単純サーチをフローチャートで表せば、以下のように表せるだろう。フローチャートの各部の実行回数は、途中で見つかる場合があるので、最小の場合・最大の場合を考え平均をとってみる。また、その１つ１つの処理は、コンピュータで機械語で動くわけだから、処理時間を要する。この時間を とする。

この検索処理全体の時間 を考えると、平均時間とすれば、以下のように表せるだろう。

ここで例題

この単純サーチのプログラムを動かしてみたら、N=1000で、5μ秒かかったとする。では、N=10000であれば、何秒かかるだろうか？

感のいい学生であれば、直感的に 50μ秒 と答えるだろうが、では、T_β,T_α は何秒だったのだろうか？ 上記のT(N)=T_α+N ✕ T_β に当てはめると、N=1000,T(N)=5μ秒の条件では、連立方程式は解けない。

ここで一番のポイントは、データ処理では N が小さな値の場合はあまり考えない。N が巨大な値であれば、T_αは、1000T_βに比べれば微々たる値という点である。よって

で考えれば良い。これであれば、T(1000)=5μ秒=T_β×1000 よって、T_β=5n秒となる。この結果、T(10000)=T_β×10000=50μ秒 となる。

前回のハッシュ法では、数値(電話番号)をキーとする検索であった。 このためハッシュ関数は、数値の不規則性の部分を取り出すだけでよかった。 それでは、文字をキーとしてデータを探す場合はどのようにすればよいか？

文字列をキーとするハッシュ

文字の場合は、文字コードを用いてハッシュ値を作れば良い。

int hash_func( char* s ) {
   int sum = 0 ;
   for( int i = 0 ; s[i] != '¥0' ; i++ )
      sum += s[i] ;
   return sum % HASE_SIZE ;
}

しかし、この方法では、文字の並び順が違うだけ(“ABC”,”CBA”,”BBB”)に対して、 同じハッシュ値となってしまう。 英文字の場合は文字数も限られ、文字コード的には末尾4bitが変化するだけであり、 上位ビットは文字数に左右されることになる。 この場合、同じような文字数であれば、末尾4bitの不規則性も平均化されて、 近いハッシュ値になることが懸念される。

そこで、文字コード的に変化のある部分が、数値的に全体に影響を及ぼし、 最終的な値が広く分布するように以下のような計算とする場合が多い。

// 積算部のみ
sum = ( sum * (小さめの素数) + s[i] ) % (大きめの素数) ;

このような考え方は、疑似乱数を生成する方式と近い部分が多い。

共有のあるデータの取扱い問題

struct List* join( struct List* p , struct List* q )
{  struct List* ans = p ;
   for( ; q != NULL ; q = q->next )
      if ( !find( ans , q->data ) )
         ans = cons( q->data , ans ) ;
   return ans ;
}
void list_del( struct List* p )
{                            // ダメなプログラムの例
   while( p != NULL ) {      // for( ; p != NULL ; p = p->next )
      struct List* d = p ;   //    free( p ) ;
      p = p->next ;
      free( d ) ;
   }    
}
void main() {
   // リストの生成
   struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
   struct List* b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ;
   struct List* c = join( a , b ) ;　// c = { 4, 1, 2, 3 }
                                     //          ~~~~~~~ ここは a
   // a,b,cを使った処理

   // 処理が終わったのでa,b,cを捨てる
   list_del( c ) ;
   list_del( b ) ;
   list_del( a ) ; // list_del(c)ですでに消えている
}                  // このためメモリー参照エラー発生

参照カウンタ法

上記の問題の簡単な解決方法は、参照カウンタ法である。

参照カウンタ法は、データを指すポインタ数を一緒に保存し、

• データ生成時は、refc = 1
• 共有が発生する度に、refc++

データを消す場合は、

• refc–
• refc が 0 の時は、本当に消す

struct List {
   int          refc ; // 参照カウンタ
   int          data ; // データ
   struct List* next ; // 次のポインタ
} ;

void list_del( strcut List* p ) {  // 再帰で全廃棄
   if ( p->refc <= 0 ) {           // 参照カウンタを減らし
      list_del( p->next ) ;        // 0ならば本当に消す
      free( p ) ;
   }
}

ただし、参照カウンタ法は、循環リストではカウンタが0にならないので、取扱いが苦手。

2分木なども終わって、検索処理のさらなる高速化として、 ハッシュ法を説明する。

オープンアドレス法

電話番号が記録されているのかどうかを探す処理を考えると、 最も単純な方法は、電話番号を配列の添字にする方法となる。

int array[ 1000000 ] ; // 局番2桁+4桁
void entry( int tel ) {
   array[ tel ] = tel ;
}
int search( int tel ) {
   if ( array[ tel ] == 0 ) // O(1) のアルゴリズム
      return 0 ;
   else
      return 1 ;
}

しかしこの方法では、0778621111 といった番号も考えると、 巨大なメモリを必要として、非現実的となる。 この際の解決法がハッシュ法で、データ件数が少なければ、 例えば電話番号の末尾2桁がおなじデータの発生する確率は低い。 もし、電話番号末尾2桁が同じでも、その番号の次の場所に保存するなどすればよい。

#define SIZE 100     // ハッシュ表のサイズ
int hash[ SIZE ] ;   // ハッシュ表
int hash_func( int phone ) {   // hash_func:ハッシュ関数
   return phone % SIZE ;
}
void entry( int phone ) {
int idx = hash_func( phone ) ; // idx:ハッシュ値
   while( hash[ idx ] != 0 )   // データ件数100で無限ループだけど...
      idx = (idx + 1) % SIZE ;
   hash[ idx ] = phone ;
}
int search( int phone ) {
   int idx = hash_func( phone ) ;
   while( hash[ idx ] != 0 ) {
      if ( hash[ idx ] == phone )
         return 1 ;
      idx = (idx + 1) % SIZE ;
   }
   return 0 ;
}

チェイン法

オープンアドレス法では、次の空き場所を探して保存するが、 表サイズよりもデータ件数を多く保存することはできない。

表が埋まって、同じハッシュ値のデータがでてきたら、同じハッシュ値どうしを リスト構造で保存する方法はチェイン法と呼ばれる。

struct List *hash[ SIZE ] ; // ポインタはNULLで全て初期化
void entry( int phone ) {
   int idx = hash_func( phone ) ;
   hash[ idx ] = cons( phone , hash[ idx ] ) ;
}
int search( int phone ) {
   int idx = hash_func( phone ) ;
   struct List* p ;
   for( p = hash[ idx ] ;
        p != NULL ;
        p = p->next )
   {
      if ( p->data == phone )
         return 1 ;
   }
   return 0 ;
}