GNU関連
GNUデバッガ
GNUデバッガ（単にgdbとも）は、GNUソフトウェア・システムで動く標準のデバッガである。 これは、多くのUnix系システムで動作可能な移植性の高いデバッガであり、Ada、C言語、C++、FORTRAN、FreeBASICといったプログラミング言語に対応している。
DBは、プログラムの実行の変更や追跡といった充実した機能を提供する。プログラム内部の 変数 の値を修正したり、監視したりすることや、プログラムの通常の動作とは別に 関数 を呼び出すことができる。
GNU
GNU（グヌー）とはオペレーティングシステムであり、かつコンピュータソフトウェアの広範囲に渡るコレクションである。GNUは完全にフリーソフトウェアから構成されている。GNUは"GNU's Not Unix!"（「GNUはUNIXではない」）の再帰的頭字語である。この名称が選ばれたのは、GNUはUnix系の設計ではあるがUNIXとは違いフリーソフトウェアでありUNIXに由来するソースコードを全く使っていないことを示すためである。
完全にフリーなUNIXライクなOSを開発するために、1984年にスタートしたソフトウェア開発プロジェクト。米国のプログラマー、リチャード・ストールマン氏が創立した「FSF（Free Software Foundation）」という団体が推進している。フリーとは単なる無料という意味ではなく、利用者に対してコードの改変を認めたり、（改変をしたものを含めて）ソースコードの配布を認める（そして義務づける）というもの。代表的なソフトウェアに、Cコンパイラー「gcc」、エディター「GNU Emacs」などがある。
gcc
gcc(GNU Compiler Collection)とは、GNUプロジェクトが開発・公開しているコンパイラのことである。様々なプログラミング言語のコンパイラを集めたパッケージとなっている。多くのUNIX系OSで標準的に利用され、オープンソースのOSではOS自体のコンパイルに用いられることも多い。
様々な言語に対応しており、標準ではC言語やC++、Objective-C、Fortran、Java、Ada、Goのコンパイラが同梱されている。「gcc」はgcc内のCコンパイラの名称および実行ファイル名でもあり、C++コンパイラのことは「g++」、Javaコンパイラは「GCJ」(GNU Compiler for Java)と呼ばれる。
gccは字句解析などを行うフロントエンド、コードの最適化を行うオプティマイザ、CPU固有のコードを生成するバックエンドに分かれており、フロントエンドやバックエンドを開発・追加することで新しい言語やプロセッサに対応させることができる。
c言語のソースコードが実行可能になるまでの流れ
プリプロセス
概要
コンパイル処理において、プリプロセッサ (preprocessor) とは、コンパイラがソースコードをコンパイルする前に、一旦ソースコードに前処理を施すためのプログラムである。プリプロセッサによって実行される命令は「プリプロセッサ指令」（プリプロセッサディレクティブ）などと呼ばれ、処理自体は「プリプロセス」(preprocess) と呼ばれる。
プリプロセッサは、その名の通り、コンパイラによるソースコードの字句解析や、構文解析、バイナリコード生成などよりも前に実行される。プリプロセッサでは、主に次のような処理が行われる。
ソースコード中にヘッダやソースファイルを取り込む ソースコード中に書かれたマクロを置き換える コンパイル対象となるソースとそうでない部分を指定する 処理系ごとの動作を指定する
ヘッダ取り込み
標準ライブラリの機能を使うとき、プログラムの先頭で「#include
プログラムの規模が大きくなると、その一部の機能をある程度の単位でまとめるのがプログラミングの定石である。Cでは、機能を提供する側がその仕様（関数のプロトタイプ宣言やマクロによる定数定義など）をヘッダとしてまとめ、機能を使う側がそれを取り込んで（インクルードして）使用する。
標準ライブラリで提供されているヘッダを使用する場合は「#include
コンパイル
概要
C言語で書かれたソースプログラムは、計算機は直接には解釈・実行できないので計算機が実行できる形式（機械語、または実行可能形式とかバイナリプログラムと呼ばれる）に変換したものを作成する作業を行う。この変換を行ってくれるソフトウェアをコンパイラと呼び、コマンドとしてUNIX標準ではccが用意されている。コンパイルされた結果、アセンブリ言語で書かれたプログラムとなる。
アセンブリ言語とは、0と1で構成される機械語を、人間に理解できるように英数字で表現した言語のこと。原則として機械語の１つの命令に付き、１つの文字列（ニーモニック）が割り当てられているため、それらを利用することでプログラミングする。C言語などの高級言語に対して低級言語と呼ばれ、ソースコードは記述しにくいが、サイズが小さく、実行ファイルの実行速度も速い。
リンク
概要
(複数の)オブジェクトプログラムは、リンケージエディタ(linkage editor)に よって連結編集され、1つの実行可能なプログラムにまとめられる。 最終的に出来上がったプログラムのことを、実行形式(executable)という。 連結編集のことはリンク(link)ともいい、リンケージエディタのことを リンカ(linker)ということもある。
参考
プリプロセッサでプログラムの質を向上させよう (1/4)：目指せ！ Cプログラマ（16） - ＠IT
ハローワールド徹底解説 - Qiita
ハッシュ法の実装
ハッシュ法
ハッシュ法は、検索アルゴリズムの一つで、各要素の値に応じて格納場所を管理するハッシュテーブルを用いて、データの検索を高速化する。ハッシュテーブルはキーを持つデータの集合に対して、動的な挿入、検索、削除を効率的に行うことができるデータ構造の1つである。
ハッシュテーブル
ハッシュテーブルはm個の要素を格納できる配列Tと、データのキーから配列の添字を決定する関数から構成されている。つまり、各データを挿入すべき位置をそのデータのキーを入力とした関数で求める。
衝突
ハッシュ法で不特定多数のデータを扱う場合、異なるデータでも同じハッシュ値が生成される可能性がある。これをハッシュ値の「衝突 (collision) 」呼ぶ。
use strict; use warnings; use utf8; use Time::HiRes qw(gettimeofday tv_interval); binmode(STDOUT, ":utf8"); use Data::Dumper; &hash_algorithm; sub hash_algorithm { my $t0 = [gettimeofday]; print "命令の数を表す数値nを入力してください。\n"; my $input_n = <STDIN>; print "n件の命令を入力してください。\n"; my %input_orders_hash; my @result_arr; while (my $input_n_order = <STDIN>) { last if $input_n_order eq "end\n"; chomp($input_n_order); my @tmp = split(/ /, $input_n_order); if ($tmp[0] eq 'insert') { $input_orders_hash{"$tmp[1]"} = $tmp[1]; } if ($tmp[0] eq 'find') { if ($input_orders_hash{"$tmp[1]"}) { push (@result_arr, 'yes'); } else { push (@result_arr, 'no'); } } } $\="\n"; foreach my $result_value (@result_arr) { print $result_value; } my $timer = tv_interval($t0)."\n"; print "$timer ms\n"; }
上記のコードは、ハッシュを使っているけれどハッシュテーブルを再現できていないよね。スクリプト言語でも再現できるのだろうか。
再帰と分割統治
再帰関数
再帰関数とは、関数の中で自分自身を呼び出すような関数で、アルゴリズムを実装するためのプログラミングテクニックの1つである。例えば、整数nの階乗を計算する関数は再帰関数として定義することができる。
factional(n)
if n == 1
return 1
return n * factional(n - 1)
nの階乗は、n! = n x (n -1) x (n - 2)... x 1 = n x (n - 1)!であり、nが1より大きい場合は、より小さい部分問題である「(n - 1)の階乗」を含んでいる。そのため、パラメタnを減らして同じ機能を持つ関数、つまり自分自身を適用し、元の問題の計算に利用することができる。nが1のときは、1を返すというように、再帰関数はそれが必ずどこかで終了するように実装する必要がある。
二分探索の実装
二分探索
二分探索やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つである。コンピュータで扱うデータは、多くの場合ある項目によって整列され管理されており、そのような場合はより効率的なアルゴリズムを適用することができる。二分探索は、データの大小関係を利用した高速な探索アルゴリズムである。
ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
use strict; use warnings; use utf8; binmode(STDOUT, ":utf8"); &main; sub main { print "整数の数を表す数値nを入力してください。\n"; my $input_n = <STDIN>; print "n個の整数を入力してください。\n"; my $input_n_nums = <STDIN>; chomp($input_n_nums); my @n_nums_arr = split(/ /, $input_n_nums); print "整数の数を表す数値qを入力してください。\n"; my $input_q = <STDIN>; print "q個の整数を入力してください。\n"; my $input_q_nums = <STDIN>; chomp($input_q_nums); my @q_nums_arr = split(/ /, $input_q_nums); my $result_cnt = &binary_search_algorithm($input_n, \@n_nums_arr, $input_q, \@q_nums_arr); print $result_cnt; } sub binary_search_algorithm { my ($input_n, $n_nums_arr, $input_q, $q_nums_arr) = @_; $\="\n"; my $first_num = $n_nums_arr->[0]; my $last_num = $n_nums_arr->[$input_n - 1]; my $i = 0; my $j = 0; foreach my $q_num (@{$q_nums_arr}) { while ($first_num <= $last_num) { my $mid_tmp = ($first_num + $last_num) / 2; my $mid = sprintf("%d", $mid_tmp); if ($q_num < $mid) { $last_num = $mid; } else { $first_num = $mid + 1; } if ($mid == $q_num) { $i++; last; } } if ($j == $input_q - 1) { last; } $j++; $first_num = $n_nums_arr->[0]; $last_num = $n_nums_arr->[$input_n - 1]; } return $i; }
【Perl】for/foreach/whileの使い分け
まずはforeachで書けないか考える
まず最初にforeachを使って書けないかを考える。foreachはループを最も簡単に書けるので、foreachで十分なのであれば、foreachを使う。foreachは繰り返しをするための条件を指定することができない。
my @animals = ('Cat', 'Dog', 'Mouse'); foreach my $animal (@animals) { print "$animal\n"; }
要素番号が必要なときは通常のfor文
次に要素番号が必要な場合があるとする。そのときは通常のfor文を使う。次のサンプルプログラムは、要素番号と配列の要素を出力するものになっている。「@animals」をスカラコンテキストで評価すると、配列の長さが取得できることに注意する。
my @animals = ('Cat', 'Dog', 'Mouse'); for (my $i = 0; $i < @animals; $i++) { my $animal = $animals[$i]; print "$i : $animal\n"; }
要素番号を増やしていかないような繰り返しはwhile文
while文は、for文と異なり「ループする条件」の部分しか持たない。
1. ファイルから行を読み込む
ファイルから行を読み込む場合はwhile文を使用する。
while (my $line = <>) { print $line; }
2. 配列をpopする
配列をpop関数を使って取り出してなくなったら終わりというような処理はwhile文で書く。
my @animals = ('Cat', 'Dog', 'Mouse'); while (my $animal = pop @animals) { print "$animal\n"; }
結論
要素番号が必要ならforを使用する。要素番号は不要だが、ループするにあたって、指定した条件に一致しない場合ループさせたくないようなときはwhileを使用する。前述した内容一致しない場合はforeachを使用する。
参考:for/while文を使った繰り返し処理 - Perlゼミ(サンプルコードPerl入門)
番兵法を用いた線形探索の実装
概要
線形探索は、配列の先頭から各要素が目的の値と等しいかどうかを順番に調べる。等しいものが見つかった時点でその位置を返し探索を終了する。末尾まで調べて目的の値が存在しなかった場合はそのことを示す特別な値を返す。アルゴリズムの効率は悪いが、線形探索はデータの並び方に関係なく適用することができる。
番兵法
番兵とは、配列などの要素として設置される特別な値で、ループ制御を簡略化する目的などで使用されるプログラミングテクニックである。番兵法による線形探索では、探索対象の配列の末尾に目的の値を番兵として設置する。番兵を設置すると、逐次探索に比べると条件判断が1つ減るため、探索効率が向上する。
配列の最後に探索データを設定。 配列の先頭から順番に、探索データと比較する。 値が同じなら探索終了。違うなら次の要素と比較する。 見つかった要素が配列の一番後ろだった場合、探索データは見つからなかったものとする。
use strict; use warnings; use utf8; binmode(STDOUT, ":utf8"); &main; sub main { print "整数の数を表す数値nを入力してください。\n"; my $input_n = <STDIN>; print "n個の整数を入力してください。\n"; my $input_n_nums = <STDIN>; chomp($input_n_nums); my @n_nums_arr = split(/ /, $input_n_nums); print "整数の数を表す数値qを入力してください。\n"; my $input_q = <STDIN>; print "q個の整数を入力してください。\n"; my $input_q_nums = <STDIN>; chomp($input_q_nums); my @q_nums_arr = split(/ /, $input_q_nums); my $result_cnt = &linear_search_algorithm($input_n, \@n_nums_arr, $input_q, \@q_nums_arr); my $result_cnt_Banpei = &linear_search_algorithm($input_n, \@n_nums_arr, $input_q, \@q_nums_arr); print $result_cnt; print $result_cnt_Banpei; } # 番兵法を用いた線形探索 sub linear_search_algorithm_Banpei { my ($input_n, $n_nums_arr, $input_q, $q_nums_arr) = @_; $\="\n"; my $cnt = 0; foreach my $n_num (@{$n_nums_arr}) { push (@{$q_nums_arr}, $n_num); my $i = 0; while ($n_num != $q_nums_arr->[$i]) { $i++; } if ($i == $input_q) { pop @{$q_nums_arr}; next; } $cnt++; pop @{$q_nums_arr}; } return $cnt; } # 逐次探索 sub linear_search_algorithm { my ($input_n, $n_nums_arr, $input_q, $q_nums_arr) = @_; $\="\n"; my $cnt = 0; foreach my $n_num (@{$n_nums_arr}) { foreach my $q_num (@{$q_nums_arr}) { if ($n_num != $q_num) { next; } $cnt++; } } return $cnt; }
