問題
突然ですが、皆様はこれらの英語を訳せるでしょうか？
情報で使う意味で訳してくださいねぇ～！
1. integer
2. Two's complement
3. exclusive OR
4. Boolean
5. bitwise operation
6. sentinel
7. self-balancing binary search tree
8. memory allocation
9. short-circuit evaluation
10. pseudorandom number
答え
皆様はどれくらい正解できたでしょうか？
全部正解できたらすごいですよぉ～！
以下に、正解と、各用語に関する簡単な説明を付けたいと思います。
お時間ありましたら、ぜひとも最後まで読んでいってください！きっと1つ、新たな知識がつくと思いますよ！
※とはいっても、今回は管理人（ばるとーく）が主観でよく見る単語を選んでいるのでどうでしょうか...
まずは、一旦正解を発表します。「答えだけ知りたい！」って人はここだけでも見ていってください。
1. 整数
2. 2の補数
3. 排他的論理和
4. 真偽値(論理型、ブーリアン型)
5. ビット演算
6. 番兵
7. 平衡二分探索木
8. （動的）メモリ割り当て
9. 短絡評価
10. 疑似乱数
1. integer
まずは"integer"です。日本語訳すると「整数」となります。
プログラミング言語でも"int"として登場します。
その名の通り、int型変数は整数を扱うことができます。
小数を扱えるdouble型変数と一緒に覚えておくとよいでしょう！
※ちなみに余談ですが、一部の分野ではdouble型を使うことは避けられます。
それはどんなときかというと、「厳密な値が要求されるとき」です。
double型変数は「浮動小数点数方式」といって、機械内部にある32bitや64bitのメモリの範囲内で小数を表す形式を採用しています。有限桁で表す必要上、その数には誤差がどうしても含まれます。それを許容できない分野では使うのを控えるべきと言われています。参考までに
2. Two's complement
正解は「2の補数」です。
2の補数とは、コンピュータ内部で負の数を表すための方法で、簡単に言うと「もとの数の0と１を入れ替えた数に1を足した数」として表します。
わかりやすく図に表してみるとこうなります。
たとえば、2進数10110010 の補数を考えてみましょう。
まず、各位の0と1を入れ替えます。すると下図のように、01001101となります。
ここに、1を足します。下図のように、01001110となることがわかります。これが10110010の補数というわけです。
ちなみに、この補数の特徴として、「元の数と補数の和が0になる」という性質があります。
10進数の計算でも、例えば128と-128の和は128 + (-128) = 128 - 128となるので0ですよね？
これと同じことが起こります。下図を見てみましょうか。
ここで、単に「0」という数字は上の位にも下の位にも、無限に「0」という数字が続くことは自明であると思います。
ということは、補数を作るために反転させると、上の位にも下の位にも、無限に「1」という数字が続くようになります。
今回の例でも左から3桁目から1が繰り上がりしていますが、ここから無限に繰り上がりが起こるため、計算結果は0になるのです。
3.exclusive OR
正解は「排他的論理和」でした。略してXORとも書きます（この記事では以降XORと書きます）。
これは何でしょうか？
簡単に言うと、xとyのXORとは、「xとyの真偽値が一致してないなら真、一致していれば偽」という演算子です。
この図を見てもらえればいいと思います。x OR y が真かつ、x AND y が偽の時に x XOR y が真になっていることがよくわかります。
※本当は記号があるんですが...今回は文字でやらせてもらいます。そこについてはまた今度のクイズにて、にしましょう...
4.Boolean
こちらの正解は「真偽値(論理型、ブーリアン型)」でした！どれかを答えられてればOKです。
これは、簡単に言うと「左辺と右辺が等しいかどうかを判定したその結果しか持たないデータ型、つまり、この型は『真(true)』または『偽(false)』のどちらか1つの数値しか持たない型」と思ってもらったらいいと思います。
例えば、x + 5 >= 10（x∈R） という式があるとしましょう。
ここで、x < 5の時は x + 5が10を超えないため真偽値は「偽(False)」となり、逆にx >= 5の時はx + 5が10以上になるため真偽値は「真(True)」となります。
5.bitwise operation
正解は「ビット演算」でした。
そもそもビットとは、2進数 0 と 1 で表される数のことで、コンピュータ内部での演算にはこれが用いられています。このビットを多数並べたものを「ビット列」と言いますが、これをビット単位で論理演算したり、ビットを移動させたりするものを「ビット演算」と言います。
現代のプログラミング言語では、我々が普段使っている10進数を用いて演算のプログラムを書くことができます。10進数で書いたとしても、コンピュータ側は難なく計算を行ってくれます。
しかし、その計算をする過程で、我々人間が普段使っている10進数をコンピュータ自身が扱える2進数に変換する必要があるため、実質的に行っている演算はビット演算と同じです。
本来ならばビット演算子についての説明もすべきではあるのですが、これをここに書くと長くなりますので、別の記事にまとめさせていただきます...
6. sentinel
こちらの答えは「番兵」となります。
番兵とは、プログラムにおけるいわば「ダミーの値」を表し、特定の入力を検知したり、配列の先頭・終点を示したりするために置かれます。
例えば、リングバッファについてみてみましょう。これは「円環リスト」とも呼ばれ、最後の要素が最初の要素を指すように、円環状（リング状）に繋がれたデータ構造です。
以下の図をご覧ください。今回はリストの大きさを5とし、非負整数（0以上の整数）が入力されるものとします。また、プログラミングでは0から数えることが多いですが、今回はわかりやすくリストを1-indexed（1番目、2番目……と数える形式）で数えています。
リストの6番目に-1が入っています。入力が非負整数であることから、「listの次のインデックスに入っている数が-1なら次に参照するインデックスを1にする」というプログラムを簡単に組むことができます。
ここで、「わざわざそんなことしなくても、『5のインデックスに数字を入れたら、次のインデックスを1にする』というプログラムでいいのでは？」と思う方もいるでしょう。
確かに、それでも実装自体はできます。しかし、もし急に「リストの長さを100にしたい」のような要求が入ったとしたらどうでしょうか？番兵を使えば、変更すべきは「リスト長」のみで済みます。圧倒的楽に実装を済ませることができるのです。
7. self-balancing binary search tree
やたら長いですねぇ...
こちらの答えは「平衡二分探索木」です。日本語も長いですねっ（笑）
簡単に言うと、平衡二分探索木とは、「木の高さの差がなるべく小さくなるように変形する仕組みを備えた二分探索木」と言えます。
まずそもそも、「二分探索木」とは、「『ノードより小さな入力を左へ、大きな入力を右へ』のようなルールを備えることで、線形探索よりも高速にデータの探索を行えるようにするためのデータ構造」です。
普通にリストを昇順にならべて、インデックスの小さい方から探索を行うと計算量はO(n)です。
一方、二分探索木を用いるといわば「二分探索」の状態になり、「このノードより大きいか小さいか？」のようにリストを半分ずつ調べることができるため、平均計算量はO(log n)となり、かなり高速になることがわかります。
しかし、二分探索木にも弱点はあります。それは、「最悪計算量がO(n)である」という点です。
あれ...？線形リストと同じですね？なぜでしょうか...？
実は、直前のノードより大きな（あるいは小さな）値しか入力されなかったとき、この二分探索木はただの連結リストになってしまうわけです。連結リストは線形リストですので、計算量はO(n)になります。
ちょうど以下の図のような状況ですねぇ
（引用:https://cattech-lab.com/science-tools/simulation-lecture-mini-8/）
逆に、値が左右に均等に分けられ、きれいな三角形に近づけば近づくだけ、計算量はO(log n)に近づいていきます。
そして、そうなるようにノードを調節する機構を備えた二分探索木を「平衡二分探索木」と言います。
AVL木や赤黒木が有名でしょうか...
8. memory allocation
こちらは、「（動的）メモリ割り当て」が答えです。似たような訳なら正解です！
実は、単なる memory allocation はメモリ割り当て全般を指しますが、C言語などでよく意識するのは『動的』メモリ割り当て（Dynamic Memory Allocation）ですね！というわけで、ここからは動的メモリ割り当てにフォーカスしていこうと思います。
これは「プログラムの実行中に必要なだけメモリ領域を確保する」ことを指します。
当たり前ですが、コンピュータが使えるメモリ領域は限られています。しかも、たいていのコンピュータではいくつかのプログラムが同時に動いているため、1つのプログラムのためにすべてのメモリ領域を確保することはできません。
そのため、基本は使いたいメモリ領域を間借りしながらシステムは動きます。どんなプログラムも、初期装備みたいな感じで、変数を宣言すると、それに見合ったメモリ領域が自動で割り当てられます。
しかし、例えば配列の大きさを途中で変えないといけなくなったとしましょう。これは簡単にはできません。なぜなら、その変数に見合っただけのメモリしか与えられないため、勝手にその範囲外に出ようとするとエラーになるからです。
そこで役立つのがこの「メモリの動的割り当て」です。あとからメモリを追加することができるので、サイズを増やすことが可能になるわけです。
またまたC言語を例に出しますが、malloc関数を使うことでこれを実現できたりします。
注意しないといけないのは、「動的に割り付けたメモリは自分で片付けないといけない点」です。プログラムが初期装備としてくれたメモリ領域はプログラムが片付けてくれますが、あとから動的に割り付けたメモリ領域はこのプログラムの管轄外ですので、必ず解放しなければならないのです。C言語ではfree関数がそれを担います。
9. short-circuit evaluation
これは「短絡評価」が正解です。
これは分岐（if文）で論理積や論理和を使ったときに走る処理で、「A and B(A or B)という論理式の真偽値がAのみによって確定する場合、後ろの演算を省略する」という仕組みです。
一体なぜこのような仕組みが取り入れられているのでしょうか？
たとえば、以下のようなコードを見てみましょう。C言語で書いています。
#include<stdio.h>
int main(void){
int x, y, z; //整数型の変数x, y, zを宣言
scanf("%d %d %d", &x, &y, &z); //x, y, zの数値を入力
if(x + y >= 5 && x - y != z){ //「x + yが5以上」かつ「x - yがzと等しくない」を満たせばYes
printf("Yes\n");
}else{ //そうでなければNo
printf("No\n");
}
return 0;
}ここで、例えば x=1、y=3のとき、前半の処理(x + y >=5)の真偽値がfalseになるためこのif文全体の真偽値もfalseです。
そしたら、後半の分岐判定を省略したいですよね？これが「短絡評価」と言われるものです。
やっても意味のない真偽値判定の演算を省略するので、「演算速度・効率が上がる」メリットがあります。
10. pseudorandom number
答えは「疑似乱数」でした！
これ知ってる人はなかなかすごいですよぉ～！
そもそも、「乱数」というのは漢字の通り「ランダムな値」を意味します。疑似乱数とは、「とある関数にとあるseedをいれて作った見せかけの乱数」というわけです。つまり、seedが同じだと全く同じ順に数字が表れることになります。
とはいえ、疑似乱数なんて昨今の世の中ではよくつかわれるものではあるので、避けるべきものでもないでしょう...
管理人のひとこと
このクイズも第2回も作成予定なので、ぜひチェックしてください！
ただ、その時は問題数を6問くらいに絞ろうかなと思ったり...（10問は多すぎた）
あと、答えを書いた記事を作ってから、を心がけましょうぞ...
他にもいろんな記事を書いています。お時間ありましたら、ぜひともご覧ください！（「記事一覧」より確認できます）
最後までお読みいただきありがとうございましたっ！
コメント