第九章 名前をつける
名前空間Xのうち、既に使われている名前の集合Aがある。
本中ではアルファベットを3つ並べた通りを基本に話を進めていたが、PCを扱う点で大切なのが、XおよびAが要素がたくさんありすぎてすべてをリストとして持てないときに、決める名前xがXもしくはAに含まれるか否かを確かめる方法があるのか‥‥
リストが存在するとして、ベタに参照する本中のハッシュ法ならば、使われていない名前は充填率が100%でなければ見つかる。しかし、時間がかかる。
判定までの試行回数の分布がアルゴリズムの善し悪しの評価として使えそう。
アルゴリズムとしての性能を上げる話題より、今回は統計的な話で。
IANAが名付けている、2文字からなる国コードの使われ方の問題。
二文字は無作為に使われているのか、なにか偏って選ばれているのか。
下に、行を1文字目、列を2文字目に使われているアルファベットとして、1なら使用されている、0なら空いているものとして行列を用意した。
行と列については周辺度数が決まるから、これをもとに0か1をランダムに入れる。
これをいくらか用意して実際のものと比較すれば、モンテカルロ法
考えられるすべての場合をやり尽くせば、正確検定になる。
実際のところ、の場合を出し尽くすのは厳しいので、モンテカルロ法を使うことになるだろう。
R的には、この行列をクラスタリングしてみたりすると、もっときれいな分布になったりするかもしれない。
アルファベット順にA〜Zと並べて入るが、アルファベットそのものに特に優劣をつけてはいないので、並び替えると楽しいことがあるかもしれない。
n<- 26 # アルファベット namespace<- as.matrix(expand.grid(1:n,1:n,1:n)) # アルファベット3桁。 trials<- 1000 # ある充填率に対して何回名前決めシミュレーションを行うか。 BY<- 100 # 名前空間の中で使われている名前の個数の刻み具合。 Res<- matrix(0,trials,length(seq(from=1,to=nrow(namespace),by=BY))) dimnames(Res)<- list(1:trials,seq(from=1,to=nrow(namespace),by=BY)/nrow(namespace)) for(t in 1:trials){ for(x in seq(from=1,to=nrow(namespace),by=BY)){ packing<- sample(1:nrow(namespace),size=x) i<- 0 Sam<- ceiling(runif(1,min=1,max=nrow(namespace))) while(i<nrow(namespace)){ i<- i+1 if(any(packing==Sam)==FALSE){ # 名前が見つかったら終了。 break } Sam<- Sam+1 # 見つからなかったらもう一回。 } Res[t,which(seq(from=1,to=nrow(namespace),by=BY)==x)]<- i } } Xlim<- c(1,ncol(Res)) Ylim<- c(min(Res),max(Res)) layout(Layout) matplot(t(Res),type="p",pch=1,cex=0.1,col=5,xlim=Xlim,ylim=Ylim, frame=FALSE,xlab="Spatial ratio",ylab="Trials",axes=FALSE,log="") par(new=TRUE) # 見つかる平均値を描く。 plot(rowMeans(t(Res)),type="l",lwd=1,log="", xlim=Xlim,ylim=Ylim,xlab="",ylab="",frame=FALSE,axes=FALSE)
M<- matrix(c(0,1,1,0,0,0,1,0,0,0,0,1,1,1,0,1,1,0,1,0,1,1,0,0,0,1, 0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0, 1,0,1,0,1,0,0,0,0,0,0,1,1,1,0,0,0,0,1,1,0,1,0,0,0,0, 1,1,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0, 1,1,0,1,1,0,1,0,1,1,1,0,0,1,0,1,0,1,1,0,0,1,0,0,1,0, 1,1,1,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,0,0,0, 1,1,1,0,1,0,1,0,0,0,1,0,1,1,0,1,0,0,1,1,1,1,0,0,0,0, 0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,1,1,0,0,0,0,0,0, 1,1,1,0,0,1,1,0,0,0,1,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0, 0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0, 0,0,1,1,0,1,0,1,0,0,0,1,1,0,0,1,0,0,1,1,1,0,0,0,0,0, 1,0,1,0,0,0,1,0,1,0,0,0,1,1,0,1,0,0,1,1,0,0,0,0,0,0, 1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,0,0,1,1,1,0,0,0,0,1, 1,1,1,0,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,1,0,1,0,0,0,0, 1,1,1,1,0,1,0,0,1,1,0,0,1,1,0,0,0,1,1,1,0,0,0,0,0,0, 0,0,0,0,0,0,1,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0, 1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0, 1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,0,1,1,0,0,0,0,0,0, 1,1,1,0,1,0,1,0,1,0,0,1,1,0,0,1,0,0,0,0,1,0,1,0,0,0, 1,1,0,0,1,0,1,1,1,0,0,1,1,0,0,1,0,0,1,1,0,0,0,0,1,0, 1,0,1,0,0,0,1,1,0,0,0,1,1,1,0,0,0,1,0,0,0,1,0,0,1,0, 0,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0, 1,1,0,0,0,0,1,0,0,0,1,0,1,0,0,1,0,1,0,1,0,0,0,0,0,1, 1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,1,0,0,0,1,0,0,0,1,1,1,0,0,1,0,0,1,0,1,0,0,0,0,0, 1,1,1,1,0,0,0,0,0,0,1,0,1,1,0,0,0,0,1,1,1,0,0,0,0,0),26,26) dimnames(M)<- list(LETTERS,LETTERS)
