【C言語入門の次】 第13回 リニアサーチ

https://youtu.be/9w8om-c57Ow

$\textcolor{pink}{四国めたん: }$教師役ですわ

$\textcolor{lime}{ずんだもん: }$生徒役なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ こんにちは。四国めたんです

$\footnotesize \textcolor{lime}{ずんだもん:}$ ずんだもんなのだ。こんにちはなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回は サーチ もしくは 検索 のアルゴリズムについてお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ところで 検索 をおこなう場合、検索対象のデータは基本的にはソートされていることが前提ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ ただし、文字列から文字、もしくは文字列を 検索 する場合を除きますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ どうしてなのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ 文字列をソートしたら、文字列の意味をなさなくなりますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ たしかに...

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、文字列からの文字、もしくは文字列の 検索 には、標準Cライブラリでstrchrやstrstrという関数が提供されていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 文字列に対しては、それらの関数を使えばOKなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ただ、文字列以外のデータの サーチ については、様々な方法がありますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、それらのアルゴリズムを理解することで、プログラマーとしての技術力アップにつながりますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そういうわけで、今回は リニアサーチ についてお話ししますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ よろしくなのだ

リニアサーチ

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは早速 リニアサーチ の仕組みについてお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ と云っても特に難しい話ではありませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、単にデータの最初から順番に、対象のデータと検索する値を比較していくだけですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 結構、ちからまかせなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、特に工夫もなにもないため、「検索対象のデータがソートされている」などの条件もありませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ データの種類などに制限はないのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ 検索対象のデータの種類は何でもOKですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 整数や浮動小数点数だけではなく、文字などもOKなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ そうですわね

リニアサーチの実装

$\footnotesize \textcolor{pink}{四国めたん:}$ とりあえず実装してみましょう

$\footnotesize \textcolor{lime}{ずんだもん:}$ よろしくなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回は文字列から文字を検索しますわ

#include <stdio.h>
#include <string.h>

int search(const char text[], char c) {
  int pos = -1;
  int idx = 0;

  char target = text[idx];
  while ((target != 0) && (pos < 0)) {
    if (target == c) {
      pos = idx;
    }
    target = text[++idx];
  }
  return pos;
}

int main(int argc, char* argv[]) {
  char text[] = "This is a pen.";
  int pos = search(text, 'a');
  if (pos >= 0) {
    printf("a は\"%s\"の%dの位置です。\n", text, pos + 1);
  } else {
    printf("a は\"%s\"に含まれません。", text);
  }
  return 0;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ search関数は、指定された文字列から文字の位置を検索しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 検索は英数字だけなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、今回は英数字と記号に限定していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 日本語には対応しないのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ できなくはないのですが、少し複雑な事情もあるので、あとでお話ししますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ まっているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、標準Cライブラリを使った例を次に紹介するので、参考にしてくださいね

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ さて、search関数に戻りますが、戻り値は最初にヒットした位置のインデックスとしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 関数内では、whileループで最初の位置から順番に文字との比較をおこなっていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 結構、力わざなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして文字が見つからなければ、-1を返しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ わかったのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、"target"の更新をする際にtext[++idx]と、前置インクリメントによって"idx"を"text"のインデックスに適用する前に+1していることに注意が必要ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ チョットした小わざなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 実行してみましょう

strchrを使ってみましょう

$\footnotesize \textcolor{pink}{四国めたん:}$ ところで文字列から文字を検索する場合には、標準Cライブラリのstrchr関数を使うことが可能ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ たしかにそのような関数があったのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは上記プログラムを標準Cライブラリのstrchr関数を使って書き直してみましょう

#include <stdio.h>
#include <string.h>

int main(int argc, char* argv[]) {
  char text[] = "This is a pen.";
  char* ppos = strchr(text, 'a');
  if (ppos != NULL) {
    int pos = (int)(ppos - text);
    printf("a は\"%s\"の%dの位置です。\n", text, pos + 1);
  } else {
    printf("a は\"%s\"に含まれません。", text);
  }
  return 0;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ strchr関数の戻り値は、ヒットした文字へのポインタですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 文字が見つからなければ、NULLを返しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、文字列のインデックスを得るには、文字列へのポインタを引けばOKですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 引いた値をint型にキャストしているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ キャストしなくても殆ど問題ないのですが、ワーニングが出ますので...

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ とりあえず実行してみましょう

$\footnotesize \textcolor{pink}{四国めたん:}$ ちなみにstrchr関数は、自作の文字検索プログラムよりも高度な最適化が施されている場合が多いですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ 結果としてstrchr関数の方が高速なので、通常はstrchr関数を使うようにしましょう

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

日本語の文字列

$\footnotesize \textcolor{pink}{四国めたん:}$ strchr関数は英数字用の関数なので、日本語には使うことができませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ また、日本語の文字を検索する関数を自作することも可能ですが、簡単ではありませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ その辺りは、そのうちお話ししてもらえる予定なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そうですわね

$\footnotesize \textcolor{pink}{四国めたん:}$ ただ、一応、Visual C++には_mbschrと云う、日本語を扱うための関数が用意されていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ Visual C++だけなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、インクルードするヘッダファイルは"string.h"ではなく"mbstring.h"になりますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ 注意するのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ とりあえず使って実行してみましょう

#include <stdio.h>
#include <mbstring.h>

int main(int argc, char* argv[]) {
  unsigned char text[] = "これはペンです。";
  unsigned char* ppos = _mbschr(text, 'は');
  if (ppos != NULL) {
    int pos = (int)(ppos - text);
    printf("は は\"%s\"の%dの位置です。\n", text, pos + 1);
  } else {
    printf("は は\"%s\"に含まれません。", text);
  }
  return 0;
}

$\footnotesize \textcolor{lime}{ずんだもん:}$ 示された位置は5となっていて、実際の位置3とは異なっているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、これは日本語の文字に使われるバイト数が、英数字とは異なっているために生じていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ この辺りは、それなりに複雑なので、別途、説明する機会を設ける予定ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ よろしくなのだ

まとめ

$\footnotesize \textcolor{pink}{四国めたん:}$ お疲れさまでした

$\footnotesize \textcolor{lime}{ずんだもん:}$ おつかれさまなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 以上で リニアサーチ を終わりますわ