疑似サイコロのさらなる考察(配列とハッシュ)

ホームC#入門講座第2章:疑似サイコロ > 疑似サイコロのさらなる考察(配列とハッシュ)

疑似サイコロのさらなる考察(配列とハッシュ)

配列の導入

疑似サイコロの精度を確かめるためのプログラムはとても繁雑でした。あれがどうしても気になるので、配列を学ぶ前にフライングをして、配列を用いたバージョンを作成しました。

using System;

namespace NewWorld
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			int[] me = new int[6];
			
			for(int i = 0;i<6;i++)
				me[i] = 0;
			
			for(int i = 0;i<100000;i++)
			{
				DateTime dt = DateTime.Now;
				int x = dt.Millisecond;
			
				int y = x % 6;
				
				me[y]++;
			}
			
			for(int i = 0;i<6;i++)
				Console.WriteLine("{0}: {1} times",i+1 ,me[i]);
		}
	}
}

このプログラムをどう理解するか、あるいは理解しないかは任せます。けれども、以前よりはすっきりまとまっていると思います。そのスッキリ感さえ感じてもらえれば十分です。

C#の乱数機能

これまで「サイコロ」といってきましたが、「ランダムな数」を「乱数」と言います。C#には乱数を生成する機能があらかじめ備わっています。その機能を使って、上の精度測定プログラムに当てはめたのがこのソースコードです。

using System;

namespace NewWorld
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			int[] me = new int[6];
			
			for(int i = 0;i<6;i++)
				me[i] = 0;
			
			Random ran = new System.Random();
			for(int i = 0;i<100000;i++)
			{
				
    				int result = ran.Next(6);
    				me[result]++;
			}
			
			for(int i = 0;i<6;i++)
				Console.WriteLine("{0}: {1} times",i+1 ,me[i]);
		}
	}
}

結果はけっこういい感じです。極めて優秀なサイコロが作れます。

乱数というのはコンピュータの定番アルゴリズムの一種です。よりよい乱数を得るために様々な研究がなされ、いろいろな手法が生み出されています。興味があればぜひ自分で調べてみてください。

なお、私が作った乱数は「現在時刻のミリ秒」をシード(初期値)とするもので、C#のRamdom()メソッドは「コンピュータが起動してからのミリ秒」をシードとしています。コンピュータによる乱数はすべて「シード」と「アルゴリズム」によって計算が可能となり、よって予測も可能となります。真の乱数はやはり「確率を支配する神」にしか作れません。

コラム:ハッシュという概念

私が用いた「割り算の余り」を使うという方法は、一種の「ハッシュ関数」と呼ばれます。ハッシュ関数とは一方向の関数で、結果からもとの値を推測することができません。割り算の余りからもとになった数を導き出すのは不可能です。

このハッシュを用いて、高速なデータベースを運用することが可能になります。私はデータベースが得意なので、少し解説します。

上の配列では、配列名の後に[ ]を付けて指定することで、特定の値を取り出すことができます。ここで、[ ] の中に入れる数字を index とし、その配列に格納されている値を value とおきましょう。

仮りに、検索語は全部で6つであるとしましょう。その検索語は仮りに以下の6つであるとします。

これらの検索語を「ハッシュ関数」に通して得られた数字は0から5までの6個だとします。0から5という数字から検索ワードを復元することは不可能ですが、あるワードからは常に一定の数字が得られます。なぜなら、それがハッシュ関数の性質だからです。

検索ワード得られたハッシュ
YUI3
長澤まさみ1
蒼井優5
仲間由紀恵2
篠原涼子4
松嶋菜々子0

そこで、得られたハッシュを配列の index に登録し、ハッシュに対応するワードを配列の value に登録します。(word[index] = value;)

word[index]value
word[3]YUI
word[1]長澤まさみ
word[5]蒼井優
word[2]仲間由紀恵
word[4]篠原涼子
word[0]松嶋菜々子

これでデータベースはできました。では、"篠原涼子"と検索されたとします。

ハッシュを用いない場合、上のデータベースの value という列を上から順にチェックしていき、"篠原涼子"が入っている行を検索します。これは "YUI" の場合には能率が良いですが、"松嶋菜々子" の時は能率が悪くなります。よって、6個のデータがあるので「計算量」を3としましょう。

一方、ハッシュを用いる場合は、"篠原涼子"と検索された場合、まずハッシュ関数を通して 4 というハッシュを得ます。すると、ハッシュと index は同じですから、一発で word[4] という風にアクセスすることができます。これは"YUI"でも"松嶋菜々子"でも同じなので、「計算量」は一定の定数kとしましょう。kはハッシュを計算する分です。

データベースが小規模の場合、たとえば今回のようにデータ量が 6 の場合はハッシュを用いなくてもいいのですが、データ量が大きくなったとき、ハッシュを用いなければ「計算量」はそれに比例して大きくなっていきます。このような状況を専門的に「計算量はn」と言います。

一方、ハッシュを用いればデータが増えてもハッシュ関数の計算だけです。そのような状況を専門的に「計算量は1」と表現します。

一般的に考えるとデータベースが大きくなればなるほど検索時間がかかると思いがちですが、ハッシュというアルゴリズムによってその問題を克服できます。ただし、ハッシュが重なってしまったり、データテーブルがたりなくなったりする可能性もあるので、実際に使う場合はより複雑な構造のテーブルになります。

このようなハッシュを生成するためにも乱数の概念は用いられます。Googleの検索の秘密が少し分かりましたか?

なお、乱数の概念は暗号や整合性の確認の際にも用いられます。このように利用できるのは「シード(初期値)」と「アルゴリズム」を与えれば乱数が決まるという疑似乱数ならではの性質があるからです。たとえば、「65」というシードと「6で割った余りをハッシュとする」というアルゴリズムを与えれば、ハッシュは常に「5」になります。サイコロを作るプログラムの中では「シード」に時刻のミリ秒という見えないものを入れたので簡単に予測はできませんが、実行した瞬間のミリ秒さえ分かれば予測できます。このように、使い方によって乱数にもハッシュにもなるという便利な性質が疑似乱数にはあるのです。