CGIでこの処理許されますか?

じぇい 1999/06/09(水) 22:37:56
え～、、質問内容が見えない題名なのですが、、（うまく表現できませんでした。）、前に一度同じようなことを質問したのですが、また、気になってしまいました。

質問内容は、どの程度の大きさの処理までだったら一般的に許されるか、、ということなのですが、。
現在メーリングリストを一応完成させています。その処理の中で、多分最も大きな処理であると考えられるのが「検索」です。
具体的には、年齢と性別と居住地を指定して、すべてのファイルから適したデータを50件ずつ表示するというものです。

1,すべてのデータをファイルから取り出して、一行ずつ配列に格納していく。
2,foreachで配列ひとつひとつに処理を与える。
3,与える処理は、まず、splitでそれぞれ「,」でばらし、年齢、性別、居住地がマッチするものだけを取り出す。

もし、最も効率が悪くなった場合は3の処理を最後までやることになります。（すなわちすべてのデータをsplitでばらして、それぞれマッチするかどうかを調べることになります。）
また、一つのデータ（一行当たり）は最高でも500バイト平均300バイトくらいです。

データの数は1000あっても許されるでしょうか?（サーバーに負担がかかり過ぎるかどうかという意味で。）
もしくは、ファイルに収めるデータの数はどれくらいまでだったら大丈夫でしょうか?（一般的に。）

B-Cus 1999/06/09(水) 23:24:43
この手の質問には、答えは存在しないでしょうね。

マシンのスペックにもよりますし、そのマシンを何人が使ってるか、
他のプロセスがどれくらい動いているかにもよります。そもそも
許す/許さないを判断する普遍的な基準など存在しません。
# マシンのスペックを教えろ、と言っているのではありません。念のため。

しかも実際負荷がかかってるかどうかは、ユーザにしかわかりませんので、
外部の者からは何も言えません。

結論としては、大丈夫かもしれないし、大丈夫じゃないかもしれない。

> 具体的には、年齢と性別と居住地を指定して、すべてのファイルから
> 適したデータを50件ずつ表示するというものです。
ちゃんとしたデータベースは、事前に値のハッシュを作成して、
インデックスを作っておきます。検索時はインデックスを参照するので、
全てのファイルをなめ回すようなことはしません。UNIX+perlで簡単に
やるなら、dbmopenあたりを使うのも一つの手です(perl5ならtieだっけ?)。

もちろん、データの規模にもよりますので、全てのファイルをなめる
方法が絶対ダメというわけではありません。

…とまぁ、全然参考にならん答えですが、これ以上は何とも言えません。

じぇい 1999/06/09(水) 23:29:16
そうですか、、。
わかりました。なんとかやってみます。

＞ちゃんとしたデータベースは、事前に値のハッシュを作成して、
＞インデックスを作っておきます。
削除処理のほうではこれを行っています。
検索のほうでもやってみます。（できれば大きなデータを扱いたいので）

ご回答どうもありがとうございました。

じぇい 1999/06/09(水) 23:29:43
[[解決]]
解決押すの忘れてました。。。

じぇい 1999/06/09(水) 23:54:17
あっ、、すいません。
＞削除処理のほうではこれを行っています。
削除処理では別の方法を行っていました。（どうでもいいんですが）

それで、ちゃんと意味がわかってなかったんですが、
＞ちゃんとしたデータベースは、事前に値のハッシュを作成して、
＞インデックスを作っておきます。
なんとなく感覚はつかめるのですが、、ハッシュを作成しておく、、というのは、別に、そのデータへのショートカットみたいなものを検索用に作っておく、、というようなものですか？
簡単な例ではどんな感じのものがあるでしょうか？

B-Cus 1999/06/10(木) 00:47:35
一例ですが…

$data=<<END;
root:*:0:0:Charlie &:/root:/bin/csh
toor:*:0:0:Bourne-again Superuser:/root:
daemon:*:1:1:Owner of many system processes:/root:/sbin/nologin
operator:*:2:5:System &:/usr/guest/operator:/bin/csh
bin:*:3:7:Binaries Commands and Source,,,:/:/sbin/nologin
games:*:7:13:Games pseudo-user:/usr/games:/sbin/nologin
news:*:8:8:News Subsystem:/:/sbin/nologin
man:*:9:9:Mister Man Pages:/usr/share/man:/sbin/nologin
uucp:*:66:66:UUCP pseudo-user:/var/spool/uucppublic:/usr/libexec/uucp/uucico
xten:*:67:67:X-10 daemon:/usr/local/xten:/sbin/nologin
pop:*:68:6:Post Office Owner:/nonexistent:/sbin/nologin
wnn:*:127:7:Wnn user:/nonexistent:/sbin/nologin
nobody:*:65534:65534:Unprivileged user:/nonexistent:/sbin/nologin
zxr400:*:1001:1001:zxr400:/home/zxr400:/usr/local/bin/tcsh
cvs:*:2000:2000:CVS:/home/cvs:/nonexistent
END
dbmopen(%TABLE,"dbm-file",0666);
foreach ( split("\n",$data) ){
　($user,$pass,$uid,$gid,$gecos,$shell) = split(":");
　$TABLE{$user} = $gecos;
}
dbmclose(TABLE);

dbmopen(%TABLE2,"dbm-file",0666);
print "$TABLE2{bin}\n";
dbmclose(TABLE2);

実行結果:
　Binaries Commands and Source,,,
てな感じ。

要は「dbm＝perlのハッシュをそのまま格納できるファイル」です。
　1,山田太郎,東京都
　2,田中次郎,富山県
　3,宮田三朗,東京都
　　　　:
という DB1 を作っておき(番号がキーね)、さらに
　東京都,1:3
　富山県,2
　　　:
という DB2 を作っておけば(こっちは県名がキー)、県名で検索したい場合、
　DB2によると東京都の人は1番と3番
　DB1によると1番は山田太郎、3番の人は田中次郎
というのが高速に(ファイルを全部なめなくても)わかるわけで。

で、こういうのを総合的にやってるのが、OracleやPostgreSQLなどの
リレーショナルデータベースなわけです。

じぇい 1999/06/10(木) 01:21:05
なるほど！
かなりわかりやすかったです。

しかし、、ということは、年齢でも性別でも所在地でも検索したいとなったら、ファイルは3つ分作らなければいけないということですね。、、？
まあ、ファイルサイズが大きくなっても、処理が早くなるほうが嬉しいのですが、、。

あと、年齢だけでなく、性別や所在地すべてを指定して検索したいときは、どのような処理を行えばいいでしょうか?

まずは年齢で検索して、その中で性別と所在地がマッチするものを選ぶ、、というようなことを行うのでしょうか?、、しかし、、それだと場合によっては結局総なめのような形になる可能性もあるし、、。

B-Cus 1999/06/10(木) 07:44:08
> 年齢でも性別でも所在地でも検索したいとなったら、ファイルは
> 3つ分作らなければいけないということですね。、、？
そうですね。全部 dbmでやるなら。

> まずは年齢で検索して、その中で性別と所在地がマッチするものを選ぶ、
> というようなことを行うのでしょうか?
そうです、というか、年齢で検索、性別で検索、所在地で検索し、
全てにマッチした人だけを表示する、と。

でもまぁ、ここらへんは考え方次第で、ありうるパターンの数は
　100(年齢)*2(性別)*47(所在地)
ですから、キーが10000個くらいのインデックスを作っておけば一発で引けます。

> それだと場合によっては結局総なめのような形になる可能性もあるし、、。
軽い処理ではないでしょうが、全部なめるより絶対にマシです。
特に対象データが数千/数万/数十万くらいになると明らかに違うと思います。

…RDBって、複数項目による検索ってどういうふうに実現してるのかなぁ。
誰か教えて。

じぇい 1999/06/10(木) 16:39:38
[[解決]]
どうもありがとうございました。
一応僕の最初の質問は解決したと思うので解決を押しておきます。

>100(年齢)*2(性別)*47(所在地)
>ですから、キーが10000個くらいのインデックスを作っておけば一発で>引けます。
というのは、年齢、性別、所在地だけのキーを持ったインデックスとは別のもう一つファイルを作るということですね。。?

>…RDBって、複数項目による検索ってどういうふうに実現してるのかなぁ。
それはすごい気になります。、、というかハッシュという方法自体、どういう構造になっているのでしょうか？（ポインタ、、とかそこらへんかな、、。）

じぇい 1999/06/10(木) 18:15:19
＊保存方法＊（データはコンマで区切って保存）
1,メールアドレスをキーとして、その他すべてのデータを値としたハッシュを作成 %mail
2,性別をキーとして、メールアドレスを値としたハッシュを作成 %sex
3,年齢をキーとして、メールアドレスを値としたハッシュを作成 %age
4,所在地をキーとして、メールアドレスを値としたハッシュを作成 %place

＊検索方法＊（仮に性別、年齢、所在地から検索するとした場合）
@sex = split(/,/, $sex[$hoge1]);
@age = split(/,/, $age[$hoge2]);
@place = split(/,/, $place[$hoge3]);

foreach $sex (@sex){
　　$data[$sex] = 1;
}
foreach $age (@age){
　　$data[$age]++;
}
foreach $place (@place){
　　$data[$place]++;
　　if($data[$place] < 3){
　　　　delete $data[$place];
　　}
}

while (($key, $value) = each(%data)) {
　　push(@true_data, $mail[$key])
}

こんな感じでしょうか?（ファイルの入出力は省いています。）

しかし、、each(%data)の部分では、ファイルの先頭から処理してくれるのでしょうか?、、じゃないとすると、、日付順にするのにまたややこしい処理が、、、。

じぇい 1999/06/10(木) 18:18:55
ありっ、、上の処理じゃだめですね、、。
最後のpushのところですべてにマッチしているデータかどうか判断しないとダメですね、、。（、、とすると、、上の処理は効率の面で間違ってますかね、、?）

B-Cus 1999/06/10(木) 20:48:57
> @sex = split(/,/, $sex[$hoge1]);
split(/,/,$sex{$hoge1}) ですよね?
ま、流れとしてはそんな感じでよろしいんじゃないかと…。

> @sex = split(/,/, $sex[$hoge1]);
> @age = split(/,/, $age[$hoge2]);
これの逆引きハッシュ、例えば
　$r_age{メールアドレス}=年齢、$r_sex{メールアドレス}=性別
を作っておいて、
　foreach ( split(/,/,$place{$hoge3}) ){
　　if( $r_age{$_} == hoge2 && $r_sex{$_} eq $hoge1 ){
　　　push(@true_data,$_);
　}
とする手もあるし(一番絞り込めそうなものから順に調べる…でも遅いかも…)、

> @sex = split(/,/, $sex[$hoge1]);
> @age = split(/,/, $age[$hoge2]);
> @place = split(/,/, $place[$hoge3]);
ここらへんを文字列でソートしておいて、3配列を先頭から
順に検索していく方法もあるだろうし。

どっちが高速かは僕にはわからんので、いろいろな方法で試してみてください。
# いずれもガチガチのハードコーディングですが…。

> というのは、年齢、性別、所在地だけのキーを持ったインデックスとは
> 別のもう一つファイルを作るということですね。。?
この文面からは理解してくれてるかどうかわからんので、コード例を出しますと、
　dbmopen(%TABLE,"dbm-file",0666);
　@true_data = split(",",$TABLE{"25:MALE:TOKYO"});
　dbmclose(TABLE);
ということです。この場合のインデックスの種類は、最高でも10000程度、という意味。

DBMにはいくつか種類があって、それぞれサイズや項目数などの制限がある場合が
あります。そこらへん調べておいてください(青ラクダ本に書いてあります)。
# GNUのDBMは制限なしだったかな?

> ハッシュという方法自体、どういう構造になっているのでしょうか？
値(文字列)を特定の数で割ったり余剰を取ったりすると、比較的かたよりのない数に
なります。これをハッシュ値といいます。

例えば「abc」ある文字列のハッシュ値が468になったとすると、その値を468の場所に
格納しておきます。で、「abc」を検索する場合は、同様の処理をすると468という数が
出てくるので、直接468番が格納してある場所(事前に記録しておく)に飛べば、全データを
調べる必要がなくなる、と。

と書くと非常に簡単に思えますが、ちゃんとした(速い)ハッシュは数学/情報工学の
領域です。深いところは僕にはさっぱりわかりません。

じぇい 1999/06/10(木) 23:05:33
どうもありがとうございました。

＞　dbmopen(%TABLE,"dbm-file",0666);
＞　@true_data = split(",",$TABLE{"25:MALE:TOKYO"});
＞　dbmclose(TABLE);
＞ということです。この場合のインデックスの種類は、最高でも
＞10000程度、という意味。
はい、それは理解しています（つもりです。）

まあ、考えてたらいろんな方法が浮かんできたので、それぞれで試してみます。まあ、メーリングリスト、、ってことに絞ったらどれでもよさそうな気もしてきましたが、、。

＞ちゃんとした(速い)ハッシュは数学/情報工学の
＞領域です。
また勉強する機会でもできたら勉強してみます。^^;

ちなみに、
＞しかし、、each(%data)の部分では、ファイルの先頭から処理して
＞くれるのでしょうか?、、じゃないとすると、、日付順にするのに
＞またややこしい処理が、、、。
この文章は無視してください。自分でもわけのわからないこと書いてました。^^;
要は、どうやって、日付順にしようかな、、って悩んでただけなので。

じぇい 1999/06/11(金) 00:04:16
あっ、、あと、、
dbmopenっていうのは、追加書き込みとかflockの使い方とかは、普通のopenと同じようにやっていいんでしょうか？

じぇい 1999/06/11(金) 16:24:52
すいません。
らくだ本にしっかりと”現時点ではBDMファイルをロックする機能は備わっていない”と書いてました。

[上に] [前に] [次に]