Entries

まさか「成分解析」のアルゴリズムが割れてただなんて……

 ファイルをあれこれ整理していると、昔懐かし「成分解析」の圧縮ファイルが出てきました。「更新無いかな?」とググってみると、なんとサイトが消えていたことが明らかに……。(一応WebArchiveで読めるけどね)
 しかし、『「成分解析」研究室』によると、なんとアルゴリズムまで解析されている模様。早速実装せねばと思い、あれこれ頑張った結果、HSPでのコード化に成功しました!
;初期設定
#const kindnum 100
#const byte 4
;■ランダム関数
#module
#defcfunc random array code
for k,byte@-1,-1,-1
code(k)*=214013
next
for k,byte@-1,-1,-1
if code(k)>255 {
if k!0 :code(k-1)+=code(k)/256
code(k)\=256
}
next
code(1)+=$26 :code(2)+=$9E :code(3)+=$C3
for k,byte@-1,-1,-1
if code(k)>255 {
if k!0 :code(k-1)+=code(k)/256
code(k)\=256
}
next
result=code(0)*256+code(1)
result&=$7fff
return result
#global
text="バファリン" :sdim output,32000

;(準備)
output=text+"の成分解析結果 : \n\n"
notesel buf :noteload "list.txt"
sdim kinds,kindnum
repeat kindnum
noteget get,cnt
kinds(cnt)=get
loop
dim kind_,kindnum :dim prcnt,kindnum

;■文字列の変換
dim code,byte
repeat strlen(text)
str_=peek(text,cnt)
p=3-cnt&3
code(p)+=str_
if code(p)>255 {
if p!0 :code(p-1)+=code(p)/256
code(p)\=256
}
loop

;■種類とパーセンテージの取り出し
percentsum=100
count=0
while percentsum>0
while
;1. 種類の決定
kind=random(code)\kindnum
flg=1
for k,0,count
if kind_(k)=kind :flg=0 :_break
next
if flg=1 {
kind_(count)=kind
count+
_break
}
wend
;2. パーセンテージの決定
prcnt(count-1)=random(code)\percentsum+1
percentsum-=prcnt(count-1)
wend

;■ソート関数
for i,0,count
max=i
for j,i+1,count
if prcnt(max) max=j
}
next
tmp=kind_(i) :kind_(i)=kind_(max) :kind_(max)=tmp
tmp=prcnt(i) :prcnt(i)=prcnt(max) :prcnt(max)=tmp
next

;(表示)
halfflg=0
for k,0,count
if prcnt(k)=100 {
output+=text+"はすべて"
}
else {
if prcnt(k)=50 {
if halfflg=0 {
output+=text+"の半分は"
halfflg=1
}
else {
output+=text+"のもう半分は"
}
}
else {
output+=text+"の"+prcnt(k)+"%は"
}
}
output+=""+kinds(kind_(k))+"で出来ています。\n"
next
mes output
stop
※「list.txt」とは、

下心
微妙さ
優雅さ
~(中略)~
成功の鍵
理論

といった、100行のテキストファイルです。詳しくは当該記事参照。

 以下、実装について。ご存じかと思われますが、HSPの整数型の最大値は2147483647(約21億、0x7FFFFFFF)です。C系の言語のようにunsignedな変数はありません。つまり、紹介記事のように、愚直にビットシフトするコードなんか組んだ日には盛大にオーバーフローすることになります(255*2^24=約43億>HSPの整数型の限界)。そもそもなんでビットシフトするかと言うと、足し算する位置をずらしているからなんですね。それも「<<3」=「8ビット(256倍)」=「1バイト」だけずらしている……つまり、普通に1バイトごと(の配列)に数値を保持すればいいのです!
 この方法の利点としては、ビットシフトだなんて面倒な考えが要らないところ。「配列に端から順に加算・繰り上がりをする」といった分かりやすいルーチンで済みます。幸い乱数のルーチンも、255*214013=54573315<<HSPの整数型の限界なので、余裕で対応できます。下の画像は、文字列を変換する流れを図で示したものです。
■文字列の変換
 ……ただ、結果をソートする辺りがちょっと面倒なことになっています。いや、アルゴリズムが難しいというわけではなく、本家と合わせるのが難しいのです。本家開発者のClockさんによると「qsort(クイックソート)しただけ」らしいのですが、それに合わせてクイックソートのコードを自力で組んで組み込んでも(同一%での)順番が合わない……。まあ、成分とパーセンテージ自体は合うので何の問題もないのですが。

 豆知識。有名な話ですが、「ツンデレ」とか「デレ」とかを調べると面白い結果になったりしますが、Clockさんによると偶然の産物だそうです。……いや偶然じゃねえだろ
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/20-5414636d

トラックバック

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Appendix

プロフィール

YSR

Author:YSR
「YSR」「YSRKEN」「◆YSRKENkO6Y(~2013/08/25)」「◆YSRKEN.ceVZZ(2013/08/26~)」として活動しています。
プログラミングと艦これが趣味です。
プロフ画像はCrystalDiskInfoの水晶雫ちゃんです。
主な創作物についてはhttp://ysrken.blog.fc2.com/blog-entry-76.htmlをご覧ください。

カレンダー(月別)

10 ≪│2017/11│≫ 12
- - - 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 - -

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数: