アルゴリズムについて
プログラミングにおいてアルゴリズムとは、問題を解決するために必要な一連の処理手順のことです。
問題解決の単なる手法なので、アルゴリズムはプログラミング言語に依存しません。もちろん、このブログで紹介しているTclでもアルゴリズムを記述することができます。
基本情報技術者試験では、特定のプログラミング言語に依存しない擬似言語というものを使用してアルゴリズムの問題を表記しているそうです。
例えば、変数aと変数bを比較するアルゴリズムを文章で書くと以下のようになります。
※変数aと変数bには異なる整数値を入力すること。
# 変数aと変数bを比較する。
変数aに数値を代入する。例.20
変数bに数値を代入する。例.30
# 変数aと変数bを比較する。
a > b の場合
a は b より大きいです。と表示して終了する。
a < b の場合
a は b より小さいです。と表示して終了する。
これを擬似言語で書くと以下の図のようになります。
データ構造について
プログラミングにおいてデータ構造とは、データの集まりを効果的に扱うようにした一定の形式のことです。
代表的なデータ構造として以下のようなものがあります。
基本的なデータ構造
リスト、配列(Array)
複数の要素(値)を列状に並べた構造をしています。各要素は0または1から始まるインデックス番号で管理されており、インデックス番号をキーにして値を参照します。
[リストのイメージ図]
連想配列、ハッシュ、マップ、辞書
要素の名前と値がセットになったデータを束ねた構造をしています。要素名には文字を使うことがでます。値を参照するには要素名をキーにして値を参照します。
内部的にはハッシュ関数を使って要素名から生成したハッシュ値で値を管理しています。
[連想配列のイメージ]
「リストと配列の区別は？」、「ハッシュとマップの区別は？」など考えるかもしれませんが、これらの区別はプログラミング言語によって違います。
構造的に同じものを言語によってリストと言ったり、配列と言ったり、要素の書き換え可否、大きさの拡張可否などの機能の違いで区別されていることがあります。
用途・機能によるデータ構造
スタック
スタックはデータ列の最後に挿入した要素を最初に取り出す構造をしています。このような構造のことを、LIFO (Last In, First Out) と呼ばれています。
積み重ねた本やお皿をイメージすると分かり易いと思います。
[スタックのイメージ]
スタックは、テキストエディタの「元に戻す(undo)」や、ブラウザの「戻る(back)」ボタンなどで利用されています。
stackは日本語で「積み重ねる」という意味があります。
キュー、リングバッファ
キューはデータ列の最初に挿入した要素から順番に取り出すデータ構造をしています。このような構造のことを、FIFO(First In, First Out)と呼ばれています。
キューのイメージは、銀行のATMやお店のレジで人が並んでいる様子をイメージするとわかりやすいと思います。
[キューのイメージ]
queueは日本語で「待ち行列」という意味があります。
リングバッファはデータ列の先頭と末尾を繋げたリング状のデータ構造をしています。回転ずしや空港の荷物受け取りをイメージすると分かり易いと思います。
[リングバッファのイメージ]
キューやリングバッファは、バックアップや集計などのバッチ処理を順番に実行するような用途で使われています。
厳密にいうと、プログラミング言語でキューやリングバッファを実装する場合、テータ列が移動するのではなくATMや皿を取る人がデータ列を移動するようなイメージで実装されています。
[参考]
Tclでキューや、リングバッファを実装した例を紹介しています。
ツリー
ツリーは木構造とも呼ばれており階層的なデータ構造をしています。
[ツリーのイメージ]
木構造はディレクトリ、ドメイン名、制御構造、XMLといった階層構造のあるデータを操作する用途で使われています。
これらのデータ構造に格納されたデータを効率的に操作するにはアルゴリズムを使います。
アルゴルズムの必要性
プログラミングをするにはプログラミング言語の文法を覚えるだけではなく、アルゴリズムの学習が不可欠です。
プログラミングをこれから始めようとする方は、〇〇言語入門の書箱、入門サイト、チュートリアルのページなど参照しながら学習を進めていくと思います。
これらの入門書はプログラミング言語の文法と使い方の説明が中心になっており、プログラミングの基本的な手法は他の言語でマスターしているものとして説明があまりされていません。
実はプログラミング言語の文法を覚えただけではプログラミングができません。
例えば、入門書で文法を覚えてサンプルコードをキーボードでカタカタと記述しながら学習が終了したとします。(この時点ではプログラミングをマスターした気になっています。)
今度はサンプルではなく、自分がやりたい事をプログラミングしてみます。
そうすると「どのような手続きを記述していけばいいのか？」と悩んだ事はないですか？
私も初めてプログラミングをやり始めた時に、変数aと変数bの値を入れ替えるような超簡単な事ですら考え込んでしまいました。
みなさんは車輪の再発明というのを聞いた事がありますか？
ほとんどのプログラミング言語には値の比較・検索・並べ替えなどの便利な関数や機能が備わっています。
従って、「アルゴリズムを学習することは、車輪を再発明するようなものだ！」と言う人がいます。
だからと言ってアルゴリズムを全く学習しないてもよいとは思いません。
便利な関数も、それらを組み立てるには基本的なプログラミングの手法をマスターしておかないと組み立てる事ができません。
その基本的なプログラミングの手法をマスターするためには定番と言われるアルゴリズムを学習することが重要です。
コメント