HSPTV!掲示板

JAVAでいうところのジャグ配列（のような機能）を使った処理がしたいと考えています。
今から具体例を挙げますが、それがより楽に・無駄なく実装出来るならば、
ジャグ配列にこだわる必要は全く無いことを先に述べておきます。


・0〜N-1の整数から1つ選ぶというくじ引きに、P人が参加した。
・参加者は何を選択するか決める。
・当選番号はMであると発表する。
・Mを選んだ人がいない場合は何もしない。
・Mを選んだ人の中から抽選で一人に絞り込む。

ということを実装したいと考えています。
なお、スクリプト中ではN=100、P=10000としており、
また参加者が選ぶ数字はランダムに決定するようにしています。

	randomize
	#const N 100
	#const P 10000
*main
	dim num,P
	dim select,N
	repeat P
		num(cnt)=rnd(N)
		select(num(cnt))++//その数字を書いた人数を記録しておく
	loop
	M=rnd(N)
	dialog"当選番号は"+M+"です。"
	if select(M)=0:dialog"当選者はいませんでした":end
	hit=rnd(select(M))
	hitcnt=0
	repeat P
		if num(cnt)=M{
			if hit=hitcnt{
				dialog str(cnt)+"さんが当選しました。"
				break
			}
			else{
				hitcnt++
				continue
			}
		}
	loop
	end

さて、この処理では、例えば抽選の結果9999さんが当選することになった場合、
10000回のループと比較をしなければいけません。
今これは10000回だから良いものの、これが100万回やもっと多くなった場合、
処理が複雑になった場合に厖大な時間が必要となります。


「誰が何を書いたか」を予め二次元配列で確保しておくという手もありますが、
ジャグ配列が使えないとなると（例えば全員が50と書く可能性も想定できるので）
100*10000の配列が必要となります。
これも参加者が100万人に変わったり、1〜100万までの数字に、となった場合に
厖大なメモリを消費してしまうという問題があります。

	randomize
	#const N 100
	#const P 10000
*main
	dim num,P
	dim select,N
	dim data,N,P
	repeat P
		num(cnt)=rnd(N)
		data(num(cnt),select(num(cnt)))=cnt
		select(num(cnt))++//その数字を書いた人数を記録しておく
	loop
	M=rnd(N)
	dialog"当選番号は"+M+"です。"
	if select(M)=0:dialog"当選者はいませんでした":end
	hit=rnd(select(M))
	dialog str(data(M,hit))+"さんが当選しました。"
	end

ジャグ配列が使えるならば、
「合計して参加者分の配列さえあれば良く、ループによる比較も要らない」
ため、メモリも時間もかからないということになります。

ということでジャグ配列（ないしはそれに類するもの）を実装したいのですが、
何か良い方法はないでしょうか。

良く分かりませんが、参加者が選ぶとする数字をランダムで決める
のなら、配列に保存する必要は無いですよ？

その都度、参加者にランダムな数値を与えて、比較するだけです。

>>100*10000の配列が必要となります
この意味が理解出来ません、10000の配列の各要素に100までの値を
入れるだけなのでは？

言い方が悪かったようで誤解を招いてしまったようですが、
参加者の番号は実際はランダムに決めるのではなく、ユーザーが与えます。
どんな番号が与えられてもいいという意味でスクリプト上ではランダムにしています。

/*こんなのじゃダメなの？*/

  randomize
 #const N 100
 #const P 10000

 sdim nn,,N
 repeat P :nn(rnd(N))+=str(cnt)+"\t" :loop
                           :ss = nn(rnd(N))
 split ss,"\t",ss          :ii = stat-1
 mes strf("当選者 = %4d 人",ii)
 mes strf("抽選者 = %4d 番",ss(rnd(ii)))

あたり番号が決まってから参加者が番号を選ぶようにすれば、はずれの番号を選んだ人を記録する必要がないので簡単になりますね。
そうできない場合でもシーケンシャルな操作なので百万やもっと多くなってもそこが問題にはなりにくいと思いますが。
あなたの望むような操作をするならfortunehillさんのように文字列にするか、もしくはモジュール変数を使うしかないような気がしますが、
どちらも配列の拡張によるメモリの再確保などで時間がかかるので速度が速くなるかはわからないです。
モジュール変数によるサンプルは以下です。

#module datamod data,total
#modfunc setdata int i
		data.total=i
		total++
		return
#modcfunc getdata int i
		return data.i
#modcfunc gettotal
		return total
#global

randomize
	#const N 100
	#const P 10000
*main
	dimtype data,vartype("struct"),N
	repeat N
		newmod data,datamod
	loop
	repeat P
		num=rnd(N)
		setdata data(num),cnt
	loop
			
	M=rnd(N)
	mes "当選番号は"+M+"です。"
	if gettotal(data(M))=0:mes "当選者はいませんでした":stop
	hit=rnd(gettotal(data(M)))
	mes str(getdata(data(M),hit))+"さんが当選しました。"

ご回答頂きありがとうございます。

文字列を使って保存するという発想はなかったので、
ジャグ配列を実装する代わりに
文字列を使って格納するfortunehillさんの考えを基に組み上げようと思います。

目的は解決しましたので、解決チェックを付けます。

「文字列型配列は個々の要素が可変長なため、
　そのメモリをint配列に見立てることでジャグ配列のようなメモリ構造を取れる」
のよねえ。少なくとも過去ログで暇人さんがやってられたのを見かけてますが。


どうでもよさそうですが、気になったことをちょいと。

参加者4万人が同一の数字を選び、その中から一人の当選者を決定を考えると、

fortunehillさんのコードの計算速度を見てみると、こちらの環境で38秒(splitが大半を占める)。
一方、真夏のストーブさんが最初に提示しているコードは40ms。大きな差です。


そもそも質問者は作り上げた配列構造に対してどれだけランダムアクセスしたいのか。
例題のようにアクセス回数が1，2回程度なら複雑な配列構造を生成するオーバーヘッドのほうが大きくなる可能性が高い。
結局は、作りたいものの特性と相談ですね。。


くじの選択肢(N)が増えることによるメモリ増加は、
擬似的な連想配列に放り込めばよさそうだが・・・そのメモリ増加と引き換えに失う処理速度はいかなるものか。
NとPの比率か何かで処理方法を変えるストラテジーパターンみたいなのを用意できるなら最高なんですけどネ。


今後同じ問題に当たった人の参考になるように解決済みですが書き込み。

その数を選んだ人の人数とそのうちの一人を記録しておいて、
誰かがその数を新しく選んだ時に「1/(今までにその数を選んだ人)」の確率で新しく選んだ人を
更新するとサイズNの配列2つとP回のループで実現出来ないでしょうか
元々randが2回だったのがP+1回必要になるのと計算誤差の蓄積が心配ですが