3.5MBちかくのテキスト辞書の扱い

質問

日本語１語が一行づつおいてあるテキスト辞書をプログラムでよびだす際、一回一回このファイルをopenすべきか、メモリにかきこんでしまうべきかまよっています。

プログラムの呼出側では何百回、何千回と辞書の頭から最後まで単語を検索する可能性があります。一語一語をfgetsをつかって読みこむか、char* 配列[300000]程度確保し、mallocをつかって読みこんだ文字列を格納したメモリ領域の先頭をこの配列に代入して、次からの呼出しはメモリでおこなえるようにするか。。。。

メモリを消費するのは断然後者だとは重いますが、どちらがいい方法といえるでしょうか。

回答No.4

nobe · ベストアンサー

こんにちは。
ご参考になりますと幸いです。

どういうシステムなのかが鍵となりますが
他にもいろいろ方法があるのですが、
仕組みが単純で実装が簡単な方法として
メモリへキャッシュするのとファイルでの読み込みを併用するのはどうでしょうか。

まず、根本的に申し上げますと、
fgetsの繰り返し読み込みとfread？などでメモリに一気に読み込むのは大差ありません。
Ｃのライブラリの実装にもよりますが基本的にファイルなどのストリームというものはメモリイメージとして扱われることが多いため、せっかく苦労してfreadのブロック読みをしてもfgetsしたほうが早かったなんてことはよくあるのです。
フラットフォームが変更される可能性あるいは将来的に他のシステムに移植されることがあるなら、fgetsを使ったほうが良いでしょう。
但しそのたびにファイルを開く、というのでは
コンピュータがもったいないと思います ^^;

昔扱ったシステムでこういうのがあります。
ものは図書館の文庫検索システムでした。

基本的に行を読み込むのは fgets です。
絶対に水準の低い open とか read は使いません。
水準の低い関数を好む人は大抵10年で技術者人生に
陰りが見えてきます(笑)。

あらかじめ頻繁に使用する頻度のキャッシュファイルを持っておきます。このファイルはあらかじめエントリ数を決めて置いて、メモリへ一度にキャッシュします。メモリへ読み込まれたキャッシュには無く頻度の低いものを検索する必要が出てきたときにファイルを開いて検索します。

ファイルを読みながら検索を行います。
ヒットしたらヒットしたことを記憶しておいて
ファイルを閉じます。ヒットしなければ最後まで読んで、大きな辞書を開いて探します。
そして見つかった単語をキャッシュの最後のエントリに加えてファイルを閉じるのです。

このときファイルを開いて検索したものは頻度が低い訳ですが１度は検索された訳ですから、先ほどのキャッシュファイルの最後のエントリ（メモリ上で）と入れ替えます。そして、このキャッシュが閉じられるときに同じキャッシュファイルへ保存するようにします。
つまり次回、もう一度同じ単語が検索されたら一番最初のメモリキャッシュで抽出されます。
頻度は２回に上がったので、キャッシュファイル内の優先順位が上がって最後から二番目に入れ替わります。
このようにして頻度順でメモリキャッシュ専用のキャッシュファイルを用意しておくのです。
実際のファイルシステムとの比率を考えてあまり小さすぎず大きすぎないサイズとするのが適当です。
パソコンレベルならキャッシュファイルのサイズは、５０００語前後が適当ではないでしょか。

より多くの人等が検索するならキャッシュファイルの語数を増やすべきですし、逆に少ないなら５０００語は多すぎるでしょう。ただし日本語だろうと英語だろうと普段使用する単語の種類は限られてきますので、５０００語程度で十分かと思います。

この方法では、
一番最初の稼動ではあまりパフォーマンスはよくありません。キャッシュファイルそのものにエントリが無いため、辞書ファイルからの検索が行われるためです。しかし使用する頻度順にキャッシュファイルに蓄えられてゆくためランニングパフォーマンスがよくなります。
そのためシステム稼動前にエージング（試験運用？）を行いキャッシュファイルをある程度完成したものにしておきます。作った人がやってもいいのですがボキャブラリに限りがあるので他人を動員したほうが良いものが出来ます。

ご参考になりましたでしょうか。
お役にたちますと幸いです。

回答No.3

muyoshid

こんにちわ。

> 何百回、何千回と辞書の頭から最後まで単語を検索する可能性があります。
断然、メモリに読込んで処理される事をお奨めします。
更に検索を高速化するために、読込んだメモリを、qsort() しておいた
方が良いでしょう。→ 検索する時はbsearch() です。
複数のプログラムがこの辞書を使用するのであれば、
　Unix/Linux 環境 → 共有メモリ
　Windows 環境 → メモリマップットファイル
を使用して、sort されたメモリを共有すると良いと思います。

回答No.2

nyan5504

メモリを消費するといっても所詮3MBです。20～30MBを超えるのでもない限り全部読み込んでください。

回答No.1

tatsu99

ＯＳは何でしょうか。また、当該プログラムが実行される環境で、メインメモリはどの程度確保されていますか。
また、検索に要する時間が多少かかっても良いのでしょうか、それとも、短時間で検索が出来ることが要求されているのでしょうか。
上記の回答により、採用すべきほうも異なってきます。