定本 Cプログラマのためのアルゴリズムとデータ構造 2-2-2つづき

文献購読

2分探索法の肝をメモ

ポイント

  • 最初にデータをソートすることが必要
  • 着目範囲の上限と下限を常に設定する
  • 上限と下限から真ん中を算出し、目的のキーと真ん中を比較する
  • キーと真ん中との大小をみることで、真ん中を上下に移動させる。
  • 真ん中を移動するときは、真ん中自身と上下限の真ん中に移動する
  • キーが見つかるか、真ん中を移動できなくなるまで繰り返す
  • 最後の最後にlow = highになったあと、low > highとかになったら終わり

速さ

1000個のキーを検索するときに10回程度しか探索しない。
線形だと平均で500回、最悪1000回。

定本 Cプログラマのためのアルゴリズムとデータ構造 2-2-1のつづき

文献購読

おっと、わすれてた。2-4は途中で力尽きて放棄してたんだ。

線形探索法の計算量

ループの中は各回に1回づつ実行される処理なので、ループ内はO(1)。
そしてwhileループの平均実行回数はO(n/2)となる。
これは、ちょっと回すと結局O(n)になってしまう。
あとと、この後の2分探索は最大実行回数を算出するので単位をあわせると、
whileループ全体の計算量は以下のようになるよ。

O(1)*O(n/2) = O(1)*O(n) = O(n)

で、線形探索全体としてはO(max(1, n, 1, 1))とかで結局O(n)という計算量になる。

これって激遅いよね。

定本 Cプログラマのためのアルゴリズムとデータ構造 2-2-2

文献購読

ということで、今日はバイナリサーチこと、2分探索法をやる。
binary search。いい響き。

2分探索法って

前回の線形探索法との違いは、ほとんど以下の関数に集約される。
前回のsearch()を以下に置き換えればok。

int binary_search(int key){
  int low, high, middle;
  int n = TABLE_SIZE;
  low = 0;
  high = n - 1;
  /*lowがhighより小さければ真ん中を割り出せる*/
  while(low <= high){
    middle = (low + high) / 2;
    if(key == table[middle].key){
      /*真ん中がkeyの場合*/
      return (table[middle].data);
    }
    else if(key < table[middle].key){
      /*割り出した真ん中よりkeyが小さいなら、highをmiddle-1へ*/
      high = middle - 1;
    }
    else{
      /*割り出した真ん中がkeyより大きいなら、lowをmiddle+1へ*/
      high = middle + 1;
    }
  }
  /*だめなら-1を返す*/
  return -1;
}

実際の速さは？

まだパフォーマンスを図る方法が出てこないのでどうしようもないけど、
体感速度的には微妙に早い気がする。

計算量は?

計算量は線形探索より劇的に少なくない。
探索範囲が判定ごとに半分に減るのでループが繰り返される回数は、log nになる。
よって、計算終了までのループ実行回数はO(log n)
ループの内部も、各回に最高1回だけ実行される。
だから、ループ内部の計算量はO(1)。

よってwhileループの計算量はO(1) * O(log n) = O(log n)となる。

ループの前後もそれぞれ1回しか実行されないから、
2分探索法の計算量はO(1)+O(log n)+O(1) = O(max(1, log n, 1))=O(log n)となる

線形探索との比較

線形探索法の計算量がO(n)だから、2分探索法は線形探索法に比べて大変に早いといえる。

勉強はいいかげんにやろう

日記

なんか、前回の日記からずいぶんと間があいてしまったなー。
時間が空いた理由は、きっちりやろうとしすぎていたからかな。
ともかく手が伸びなかったのだから心の奥底で気が重かったんだと思う。

改善策は、ここのところ考えていたので導けた。

いままでは「説明読み」→写経→「コード書き」→写経、という感じで、
まず説明ありき、さらに、写経が疲れる、という感じだった。
アルゴリズムの勉強と気持ちよいが結びついてなかったみたい。

なので、今後は「コードを先に入力」して、「説明は書かないこともある」くらいで良いかなと思っている。

ともかく、楽しく、サクサクと勉強したいと思う。

さてやるぞ。

定本 Cプログラマのためのアルゴリズムとデータ構造 2-3

文献購読

定本 Cプログラマのためのアルゴリズムとデータ構造の第2章の読書メモです。

線形計画法による探索の計算量

計算量について考える。使う例は、n個のデータを格納したリストから、ある特定のキーを持つデータを探索するもの。

単純な探索プログラムのデータ数n

表に登録されているデータ数が増えるほど探索にかかる時間が増える。
→表のデータ数をnにするのが自然。（へえ

線形探索法で探索を行うプログラム

リニアサーチ。
配列を端から順にスキャンしながらキーの比較をする。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TABLE_SIZE 100

struct{
  int key;
  int data;
} table[TABLE_SIZE];

/* フィボナッチ数列で構造体を初期化 */
int init_table(int max){
  int i, x, x1, x2;
  x1 = 1;
  x2 = 1;

  if(max >= 0){
    table[0].key = 1;
    table[0].data = x1;

    if(max >= 1){
      table[1].key = 2;
      table[1].data = x2;

      if(max >= 2){
        for(i=2; i<max; i++){
          x = x1 + x2;
          table[i].key = i+1;
          table[i].data = x;
          x1 = x2;
          x2 = x;
          printf("Fibonacci %d : %d\n", i+1, x);
        }
      }
    }
    return 0;
  }
  else{ return -1; }
}


int search(int key){
  int i;
  i = 0;
  while(i < TABLE_SIZE){
    if(table[i].key == key){
      return table[i].data;
    }
    i++;
  }
  return -1;
}

int main(void){
  int init, rnd, ans;

  init = init_table(TABLE_SIZE);
  if(init < 0){
    return -1;
  }

  /* 1から100までの乱数 */
  srand(time(NULL));
  rnd = rand() % TABLE_SIZE + 1;
  printf("randum number : %d\n", rnd);

  ans = -1;
  ans = search(rnd);
  if(ans == -1){ return -1; }
  printf("table.key : %d => %d\n", rnd, ans);

  return 0;
}

リニアサーチは単純。
関数searchの繰り返し実行部分は、以下のreturn以外。

  while(i < TABLE_SIZE){
    if(table[i].key == key){
      return table[i].data;
    }
    i++;
  }

リニアサーチの最良と最悪

  • 最良
    • 1回の探索で探索終了。
  • 最悪
    • ABLE_SIZEの探索をしても答えが見つからない。

つまりwhileループは最小1、最大でn回実行される。

例ではテーブルに昇順で登録しているキーやデータを
ランダムにした場合は、平均でn/2回の探索が繰り返される。

計算量

  • reruenする行や、引用部の前後の行
    • O(1)
  • ループ部分
    • O(n/2)

C言語を使っての発見

C言語

発見というか、忘れているだけかも。

  • #defineの行末は「;」なし
  • 関数名と同じ変数は作れない
  • int型で表現できる範囲が、意外と狭い。
  • randはsrandで初期化する
  • 引数を受け付けない関数の宣言は、関数名(void)にする。
  • 構造体はハッシュだなー