Infomation

　プログラミングに関するちょっとしたまめ知識を集めています。
　知らなくても支障は無いけど知ってるとちょっとした時に得意に慣れるかも知れない小ネタ達です。
　呑み会のネタにでもどうぞ。

目次

一般知識

アルゴリズム

用語・定義

コーディングスタイル

言語依存

まめ知識

一般知識

Q.:ANS_F]][[ソートの所にあるO(n log n)とかって何？

A.O記法と言います。
アルゴリズムの性能評価などでよく使われる記法です。
OはOrderの略で、一回の処理時間などをあらわします。
例えば、データの個数nが2倍3倍になると実行時間が22 = 4倍, 32 = 9倍になるようなプログラムの実行時間はO(n2)であると言います。
これを正確に言うと難しい話になりますが。
「定数c(＞0)、Nが存在し、n ≧ Nならば必ず|f(n)| ≦ c|g(n)|が成り立つ時。
n→∞の時、f(n) = O(g(n))で有る」と言います。

Q.Windowsの改行コードが二文字なのは何故？

A.そもそもテレタイプの転送スピード(10bytes/secだったかな？)に対して、ヘッドの移動速度が遅いおかげで復帰改行が二文字になった様です。
改行文字だけでは改行した時点で次の文字がタイプされるから、復帰コードを入れて調整したんですね。

＃追記
＃調べてみたら、問題のテレタイプはTeletype Model33と言う物らしいです。

Q.配列の番号はなぜ、０から始まるのですか（配列の始めはarr[0]のように）？？　１から始まるほうがわかりやすいと思うのですが。

A.密かにFORTRANなんかでは1から始まってる気もしますけどね。
それにPascalなんかでは任意の添え字範囲を使えたような気もしますね。

物事実は0から数えた方が良いこと多いんです。
これって有名な話なんですよね。
例えば、とあるビルの4階まで駆け上がるとします。
一つの階を上がるのに10秒掛かるとしたら4階まで何秒掛かりますか？
x=4*10=40で40秒？違うでしょ？
実際には「1階から上がる＝1階まで0秒」ですから。
x=(4-1)*10=30で30秒ですよね。
これも地階を0階としていれば目的地は3階になるのでそのままの計算で出せますよね。
x=3*10=30
他にも2000年は21世紀ではなく20世紀でややこしかったり。
等差数列の公式も「初項+公差*(n-1)」だったり。
これらも0基準ならなんて事はなかったんですよね。
この手の問題はプログラミングでも多い物です。
だから何故配列の添え字が0からなのか考えるより慣れた方がお得だと思いますよｗ
まぁ強いて言うなら言語仕様であるとしか言えないですね。
プログラミング言語を構築する学者さんというのは数学者が多いですから、上記のような理由で0にしたがるんだと思います。

Q.バッチ処理って何？

A.スクリプト言語などによる処理の自動化のことです。
シェルスクリプトやバッチファイル、人によってはPerlやRubyで、実行したいコマンドや条件を列挙して何らかの処理を自動化します。
パイプやリダイレクトで延々繋がれたコマンドラインで打ち込みきれないコマンドなども、そう言ったスクリプト処理したりします。
バッチファイルの例を挙げたいと思います。(MS-DOS/Windows限定)
以下のソースをテキストエディタで打ち込み(コピペでもOK)、sample.batと言う名前で保存して下さい。
そして、DOSプロンプト、或いはコマンドプロンプトで保存したディレクトリ(フォルダ)に移動し、sampleと打ち込んでエンターキーを押してみて下さい。

@echo bat script sample,
@echo 拡張子exeのファイルを逆順ソートして1ページずつ表示
@echo off
pause
dir *.exe | sort /r | more

Q.TROってなんですか？

A.TROはTail Recursion Optimizeの略で。
末尾再帰を非再帰に最適化する事を言います。
多くの場合末尾再帰は反復文で置き換えられるので、一般的にはTROは反復文への変換を言います。
さらに言うと、コンパイラの最適化フェーズでの末尾再帰最適化の事を言うことも多いでしょう。
この場合も、多くのコンパイラでは反復文を使った場合とほぼ同等のオブジェクトコードを生成するようです。
再帰関数は場合によっては関数コールのコストが問題になりますので。
出来る場合には反復文に最適化することを考えても良いでしょう。
＃スタックの消費量も減るのでコンピュータと地球にも優しいですねｗ

Q.hogeってなんでそ？

A.hogeとは、特に凝った識別子を付ける必要のない変数や関数に付けられる識別子です。
hogeの他にはpiyo、nyao等が有るようです。
どうも1980年代初頭に同時多発的に発生したようです。
英語圏ではfoo、bar、baz(buz？)が使われるようです。

Q.n進数がよく解らないです。

A.別途ドキュメントを用意しましたが、とりあえずさわりだけ。
n進数とは、基数がnで有る数集合です。
はい、解りませんねｗ
つまり、nの時点で桁上がりする数の集まりです。
詳しく話し出すともっとややこしい話になるのですが。
言い換えれば数の種類がn個である数の集まりとも言えます。
とりあえずはnで桁上がりする事だけ覚えておけば問題ないでしょう。
例を挙げておきます。
3進数の場合。
0、1、2の次は10となります。
普段使い慣れている10進数に変換すると3ですね。
同じく、20、21、22と来たら次は100です。
10進数に変換すると9ですね。
5進数なら。
0、1、2、3、4の次は10、10進数での5に当たりますね。
40、41、42、43、44、100となり、10進数での25ですね。
10進数よりもnの大きな物も見ましょう。
有名所の16進数では9の次からA、B、C、D、E、Fと来て10になります。
FC、FD、FE、FF、100で、10進数の256に当たりますね。

アルゴリズム

Q.アルゴリズムって何？

A.1.アルゴリズム：
日本語では算法と訳される。
数学者アル・フワリズミの名からアルゴリズムと呼ばれる。
プログラミングに関わらず、数学的世界に於いて、何らかの問題に対する解法・手順を表す言葉として使用されている。

＃長月の知る限りでは数学で名前にアルゴリズムが付いた計算手順は二つしか有りませんｗ
＃気になるなら数学系サイトで調べてみて下さい。

Q.安定したソート、不安定なソートって何？

A.ソート後のデータ順序が保証されてるかどうかで分類します。
同じデータがあったとき元の順序通りでソートする物が安定したソート。
関係なく並べるのが不安定なソート。
下の表は安定、不安定で分類したソートアルゴリズムの表です。
アルゴリズム選択の際の参考にどうぞ。

分類名前オーダー
安定バブルソートO(n2)
挿入ソートO(n2)
選択ソートO(n2)
マージソートO(n log n)
分布数えソートO(n)
逆写像ソートO(n)
ラディックスソート(基数ソート)O(mn)　mは桁数
不安定クイックソートO(n log n)
ヒープソートO(n log n)
コームソートO(n log n)

用語・定義

Q.インタプリタって何ですか？

A.本来の語義としては、インタープリタはプログラムの内容をそのつど機械語に翻訳しながら実行していく言語処理系のことです。
ちなみにコンパイラは一気に機械語に翻訳します。（実行はしません）
しかし、その都度翻訳しながら実行するかどうかはインタプリタシステム次第です。
上記の説明は本来の語義としては正しいですが現実を反映していません。
最近のインタプリタは一度コンパイルしてしまう物が多いと思います。
つまり、(最近多い)中間言語インタプリタと呼ばれる物は、
一度ソースコードをコンパイルしてしまって、中間コードをインタプリタに渡します。
或いはオブジェクトコード(実行可能な形式のコード)をメモリ上に展開します。
そして、プログラムカウンタと言う物を実行開始の位置に置くんですね。(つまりメモリ上のプログラムの実行を開始する)

Q.ある言語のソースコードを別の言語のソースコードに変換するプログラムってなんて言うんですか？

A.ある言語のソースファイルを別の言語のソースファイルに変換する物をトランスレーターと言います。
ちなみに、ある言語の動作を理解するために、その言語を使ってそれ自身のインタプリタを作ることをメタサーキュラーと言います。

Q.サブルーチンとかプロシージャとかファンクションとか関数とか手続きとかメソッドとかって結局の所何？

サブルーチン：
その名の通り本来は補助的(サブ)な処理の流れ(ルーチン)を表す。
一般的には関数や手続きに分割された処理のひとかたまりを言う。

＃つまり、「この処理はこういう意味なんですよ」と理解しやすいようにルーチンに名前を与えて、その中では特定の処理に集中している感じです。

プロシージャ(手続き)：
内部で定義された処理を実行する。
多くの場合引数を取り、他から独立したメモリ空間を与えられる。
細かな処理を隠蔽し、プログラムの管理を容易にする為に考え出された。
＃詳しくは構造化を勉強しましょう

関数(ファンクション)：
引数に寄らない返り値を返すプロシージャ。
数学の関数をモデルに作られたため、処理結果を代入文などで受けることが出来る。(事が多い)
＃プロシージャとの利点・欠点の違いは使っていく内に解るでしょう。
＃解るようになれば胸を張って中級者と言えるでしょう・・・と思います(汗)

メソッド：
オブジェクト指向言語(以下OOPL)におけるクラスメンバ関数に対してよく使われる用語。
日本語訳すると方法・筋道、しかしOOPLに於いては振る舞いと言った意味を持つ。

Q.ライブラリって何？DLLって奴のこと？

ライブラリ：
プログラミング言語に於いては特定の処理を何度も書かずに済むように、その処理を担当する関数・手続き・サブルーチン・クラス等をひとまとめにしたもの。
ソースファイルレベルで提供されたりコンパイルド(機械語翻訳済み)で提供されたり様々である。

＃楽をするためには是非使い方を覚えたい物の一つｗ

DLL(ダイナミックリンクライブラリ)：
DynamicLinkLibraryの略で、便利な関数を集めた物。
昔は静的にリンクする物だったライブラリを動的にリンクできるようにした物。
実行可能ファイルにバイナリを含めなくて良いので、ディスクスペースの節約になったり、配布時の苦労が減ったりする。(場合によっては逆の事も・・・)

＃DLLと言うのはWindows用語だったりします。
＃UNIX系OSでの同様の働きをするプログラムはa.outだったりELFだったりします。
＃拡張子で言うと.soだったかな？

Q.エンディアンって何ですか？

A.CPUがデータを読む順番です。
具体的に言いましょう、例えば、4バイトのデータ0x00112233が有ったとき。
00,11,22,33と読むCPUも有れば33,22,11,00と読むCPUも有ります。
前者をビッグエンディアン、後者をリトルエンディアンと言います。
場合によってどちらもできるCPUはバイエンディアンと呼ばれるようです。
と、これだけでは寂しいので名前の由来なんかを・・・
リトルエンディアン、ビッグエンディアンと言うのは、スイフトのガリバー旅行記に出てくる卵を細い方から食べるか、太い方から食べるかの派閥に由来します。
何故これを引用したのかは解りませんが、エンディアンという言葉はガリバー旅行記からです。

コーディングスタイル

Q.一般的なグローバル変数とローカル変数の使い分けは？

A.知りません。
長月は業務でコーディングを行ったことがないので一般的にどうしているかは知りません。
しかし、長月なりの指針であればお答えできます。
以下長月なりの指針

Ｃ言語版：グローバル変数は必要最小限でとどめる。
どうしてもポインタで渡せない、自動変数では困る場合のみ使用する。
使用するときも、出来るだけstaticを付ける。

C++版：グローバル変数は必要最小限でとどめる。
どうしてもポインタやリファレンスで渡せない、自動変数では困る場合のみ使用する。
使用するときも、出来るだけstaticを付けるか名前空間の使用を検討する。
出来るだけクラスメンバにしてしまう、クラスメンバにした場合、出来るだけprivateやprotectedにする。
その変数へのアクセスはメンバ関数によってのみ行われる。

HSP版：HSPは構造化された言語ではないのでローカル変数は存在しません。
しかし、Ver2.5から追加されたモジュール機能によって独立した空間を構築できるようになりました。(厳密には独立ではないですが)
その機能を使って、「グローバル変数しかなく、全ての変数にstaticが付いたＣ言語でソースファイルを分割する。」様な状態が作れるのでそれを利用します。
出来るだけ流れ毎にひとまとめにして、それぞれをモジュールに区切ることで変数のグローバル化を防ぎます。
逆に、モジュール機能を使うと、プログラム全体でグローバルな変数は存在しなくなるのでHSPでは使い分けはしないことになりますね。
密かに構造体やクラスのようなアクセス方法で内部にアクセスできるので。
プログラム全体で一つしかインスタンス化出来ないクラスのような使い方もしますｗ
むしろそう言う使い方がメインですね(汗)

Perl版：Perlも変数はデフォルトでグローバルですね。
では長月はPerlでどのようにグローバルとローカルを使い分けるのでしょうか？
実はサブルーチンローカルの物をローカル化する以外グローバル変数のままで使います。
後は一時変数や、ループカウンタなどの名前を付けるのが面倒な物をローカル化することがあります。
しかし、ループの意味を表す変数名でループカウンタを作ることもあるので、実は結構使い分けを意識していません。

Q.番兵(番人、見張り、センチネル)ってなんですか？

A.簡単に言うとデータの最後にデータの末尾である印を入れておくことです。
が、最後に単純な「あり得ない値」を入れておく訳ではありません。
良く勘違いでＣ文字列の\0様に、単純なあり得ない値を用いた終端子を番人等と言う方も居ますが。
実際にはこれらとは少し違います。
単なるあり得ない値で識別するのではなく、「必ず条件にヒットする値」を使ってループを終了させ、ループの外で番兵に当たったか判定します。
メリットとしては、ループの度に行われる終了判定を省略できます。
では例として要素数が解らない0〜9の値を取るint配列の要素を順番に参照して、
特定の数以下の値を持つ最初の要素を調べるコードを書いてみましょう。
/* 単なるあり得ない値を使う方法 */
int arr[] = {5,6,7,8,100}; /* 有効なデータはarr[3]まで */
while(0 >= arr[i] && arr[i] <= 9){
if(arr[i] <= x) break; /* xには探したい値が入っている */
else i++;
}
/* 番兵君だったら */
int arr[] = {5,6,7,8,-1}; /* 有効なデータはarr[3]まで */
while(1){
if(arr[i] <= x) break; /* xには探したい値が入っている */
else i++;
}
if(0 > arr[i]) puts("番兵君");

ループの回数が膨大な場合には馬鹿に出来ない差になります。
さらに上手く使えばループのコードがすっきりとした物に出来ることもあります。

Q.変数名の前に二つとか後ろに付けるアンダースコアの意味を教えて。

A.前に二つアンダースコアを付けるのは多分C/C++の話だと思うのですが。
C/C++では、コンパイル時に識別子の前にアンダースコアを付ける事があるので、それに引っかからないように二つ付けることがあります。
多くの場合はユーザーの付ける識別子ではなく、処理系定義のライブラリ関数やライブラリ変数になります。
その他、Ｃ言語の事前定義マクロも前後にアンダースコアを二つ付けます。

それに対して、変数名の後ろにアンダースコアは。
構造体やクラスのメンバ変数に付けられることが多いようです。
これは個人の趣味のレベルでしょう。
ちなみに、Effective C++の著者、Scott Meyers氏もこの命名規則がお好きなようです。

言語依存

Q.Ｃ言語のprintf()で使われる%gって何の略ですか？　%d = decimalみたいな感じだろうとは思うのですが・・・(Ｃ言語)

A.え〜%gの語源なんですが・・・
%e=Exponent(指数), %f=floating Point(浮動小数点数)で、EFの次はGで%gと言うことなんだそうです。
実はあんまり意味無かったんですねｗ

Q.そもそもポインタって何？(Ｃ言語)

A.Ｃ言語を前提にお話しします。
ポインタ変数と言うのはただの変数です、具体的には整数値を保持しています。
ただし、intやcharと同じ整数値を保持する変数ですが。
intとcharではその解釈が違うように、ポインタ型も固有の解釈を持っています。
ポインタ変数の場合はメモリ上のオブジェクトへの参照として解釈されます。
しかし、データの格納場所だけでは何を表しているか解らないため、intやcharなどの型名を使ってポインタの指すデータがどんな意味なのかを知るわけです。
以上がポインタ変数で、ポインタとは、そのメモリ上の位置を指す事或いは物を言います。
黒板を指す時に棒を使ったりしますね、アレもポインタと言いますが同じ意味です。
次にアセンブリ言語に於けるポインタですが、これも基本的にＣ言語と変わりません。
つまり、メモリ上の何かの場所を指す物です。
アセンブリ言語の場合、データの参照先としてだけでなく、次のジャンプ先を表すこともあります。
実際には変数を表しても、ジャンプ先を表しても、参照時にはそのアドレスに飛ぶ(読みに行く)訳ですから、何ら差はないと思っていただいても良いでしょう。
アセンブリはとにかくまずアドレスありきなのです

Q.多次元配列の考え方とは？(Ｃ言語)

A.そもそも配列とはなんなのか考えてみましょう。
「配列とは変数を沢山(多くの場合任意の数)集めた物です。」と言う説明はされたことが多いと思います。
さらに一歩進みましょう、「配列はメモリ上にアドレス値が連続した領域を確保し、型のサイズ毎に区切って使う物。」と言う解釈もできますね。
では多次元になるとどうなんでしょう？
良くある考え方は二次元なら平面、三次元なら立体のイメージで云々と言う物なのですが。
実際メモリは線形(一次元)方向に使わないととてもコストが高くなるので、多次元な領域構築は行いません(そもそも三次元以上が表現できないｗ)
多次元配列の配置はそれぞれの処理系で実装上どう行われているか知りませんが、多くの場合はint arr[2][3]に対して以下のように確保されると思われます。(少なくとも規格でこう扱えるように決められてると思います。)
arr
[0,0][0,1][0,2][1,0][1,1][1,2]
 これが何を表しているか解りますか？
配列とは「メモリ上にアドレス値が連続した領域を確保し、型のサイズ毎に区切って使う物。」ですから。
上記の並びを以下のように区切るとある事実が見え始めます。
arr
「[0,0][0,1][0,2]」「[1,0][1,1][1,2]」
 解りましたか？つまりはarr[2][3]とは「要素数3の配列の配列(要素数2)」なんです。
別の説明をしてみましょう、配列の要素を指すarr[0][1]とは、*(arr[0]+1)のシンタックスシュガー(構文を簡単にする構文)ですから。
同じように宣言を見てみると「arrから*(arr[2]+3)まで領域を確保する。」とも読めます、さらに進んで「arrから*(*(arr+2)+3)まで領域を確保する」と読むことが出来ますね。
この方法をarr[0][0]に適用すると***arrになります。
と言うことで、Ｃ言語での多次元配列は配列の配列の(配列の...)配列と言うことになります。

Q.変数宣言で実際に何をしてるの？(Ｃ言語)

A.またＣ言語を前提とします。
int iでＣコンパイラは何をしているのでしょう？
これは、メモリを確保し、それに対してiと言う名前であるというリンカへの情報をシンボルテーブルと言う物に格納します。
さらに、シンボルテーブルにはコンパイル時にintとして扱うという情報も格納します。
つまり、メモリを確保するコードを生成して、後にリンカが相対アドレスへと変換するまでの別名を付けます。
そして、シンボルテーブルに参照時にはintとして扱うと言うフラグを入れて置くわけです。
さらに、メモリ展開時に使うメモリ領域のアドレスがファイル形式に拠りますが大体決まっている為、仮のアドレスを割り当てます。
リンク時にはその情報を用いて、他の変数等も参照してアドレスを調整し、リンクするオブジェクトコード群に現れる関係する変数i と結びつけます。
＃この時点でもまだ仮のアドレスで、実際にはプログラムがロードされた時に実アドレスに変換されます。

Q.え？モジュール外からアクセスできるの？(HSP)

A.出来ます。
具体的には区切り文字として@を使います。
変数名@モジュール名とするとアクセスできてしまいます。
モジュール名を付けていない場合、デバッガで追うことでHSPシステムがそのモジュールに付ける一意な名前が解りますので、それを利用しても良いでしょう。
名前を付ける方が簡単で楽ですけどね。