- PR -

ランダムアクセスファイルを使ってバイナリサーチ

1
投稿者投稿内容
Dream
常連さん
会議室デビュー日: 2004/01/29
投稿数: 43
投稿日時: 2004-10-07 00:03
今１００メガ以上のテキストファイルがあり、これから効率よくデータを抽出しようとしています。このファイルには各行にナンバーが昇順で振ってあります。

No.　Data１　　Data2
１　　AAAA　　DDDDDD
２　　BBBB　　XXXXX　　　　　といった感じのファイルです。

あるナンバーを持つデータをこのファイルから抜き出すということを、約１０万回繰り返し行うので、効率を考えて、ランダムアクセスファイルを用いて、バイナリサーチをして、求めるデータを抜き出そうとしました。
ところが、
比較的、小さいナンバーを検索しているうちはいいのですが、大きいナンバーを検索していると、フリーメモリーの現象量が大きくなって来ています（すぐにフリーメモリーの量が少なくなってしまいます）。そのせいなのかはわからないのですが、途中でぴたっとプログラムが止まってしまいます。でもメモリエラーはでません。　
ちょっと困っています。

そこで質問なのですが、ランダムアクセスファイルは、あまりメモリを消費しないで直アクセスができると思っていたのですが、seek(long byte)で大きなバイト数を指定した場合というのは、やはりメモリの消費が大きいのでしょうか？
あと、自分なりの解決法として、数が大きい場合は降順に並べ直したファイルに対して検索をかけるようにしようと考えているのですが、もしみなさんでしたら、このような大きなファイルにアクセスする場合には、どのように対処されますか？
お知恵をお貸しいただければ幸いです。
Kissinger
ぬし
会議室デビュー日: 2002/04/30
投稿数: 428
お住まい・勤務地: 愛知県
投稿日時: 2004-10-07 00:09
Dreamさん、こんにちは。

私なら RDBを使用します。
七味唐辛子
ぬし
会議室デビュー日: 2001/12/25
投稿数: 660
投稿日時: 2004-10-07 00:09
ソートして検索するのであれば、2分検索アルゴリズムでやれば、かなり高速で検索できます
さて表題の件ですが、自分ならＤＢに保存してＳＥＬＥＣＴ文で検索します。
Dream
常連さん
会議室デビュー日: 2004/01/29
投稿数: 43
投稿日時: 2004-10-07 00:21
そうですね。
RDBを忘れてました。解決しそうで、安心しました。
どうもありがとうございました。

あと、まだ気になるのですが、
ランダムアクセスファイルはseek()で大きなバイト数を与えるのを繰り返すと、効率はよくないものなんでしょうか？
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2004-10-07 08:03
unibon です。こんにちわ。

引用:

Dreamさんの書き込み (2004-10-07 00:03) より:
そこで質問なのですが、ランダムアクセスファイルは、あまりメモリを消費しないで直アクセスができると思っていたのですが、seek(long byte)で大きなバイト数を指定した場合というのは、やはりメモリの消費が大きいのでしょうか？

http://java.sun.com/j2se/1.4/ja/docs/ja/api/java/io/RandomAccessFile.html#seek(long)
を使われているのですよね？
確かめてはいませんが、seek でメモリが大量に消費されるとは思えません。プログラムの他の個所が原因ではないでしょうか。なお、止まったところで、もし Windows ならば Ctrl + Break を押すと、その瞬間のスタックトレースが表示されますので、糸口になる可能性もあります。

引用:

Dreamさんの書き込み (2004-10-07 00:03) より:
あと、自分なりの解決法として、数が大きい場合は降順に並べ直したファイルに対して検索をかけるようにしようと考えているのですが、もしみなさんでしたら、このような大きなファイルにアクセスする場合には、どのように対処されますか？

テキストファイルのまま、今のやりかたでやるのもアリだと思います。なお、降順にしたほうが良いのはあくまでも数が大きい場合だけですから、根本的な解決策にはならないような気もします(出現する値の頻度次第ですけど)。
ファイル容量にもよりますが、100MB程度ならば、メモリーにぜんぶまるごと読み込んでしまってから、メモリー上で検索しても良いのではないでしょうか。でも1GB位になると大きすぎてやはり難しいですね。
(Java は起動時のオプションで -Xmx を指定すれば使用可能なヒープメモリーを増やせます。)
さくらば
大ベテラン
会議室デビュー日: 2002/11/12
投稿数: 145
投稿日時: 2004-10-07 09:13
こんにちは、さくらばです。

引用:

unibonさんの書き込み (2004-10-07 08:03) より:
確かめてはいませんが、seek でメモリが大量に消費されるとは思えません。プログラムの他の個所が原因ではないでしょうか。


RandomAccessFile とはいえども、ファイルにはシーケンシャルにしかアクセスできない
のですから、seek で大きな数字をいれたら時間がかかってしまうのは当然だと思います。

引用:

ファイル容量にもよりますが、100MB程度ならば、メモリーにぜんぶまるごと読み込んでしまってから、メモリー上で検索しても良いのではないでしょうか。でも1GB位になると大きすぎてやはり難しいですね。


そんなときには MemoryMappedFile を使うのが常套手段です。

java.nio.channels.FileChannel#map メソッドでファイルをマップすることができます。
マップする領域もヒープではなく、JNI で直接メモリを確保するので、ヒープ領域の
サイズを気にすることもありません。

また、マップした後は java.nio.ByteBuffer として扱えるので、RandomAccessFile に
比べたら検索のスピードは段違いです。

unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2004-10-07 13:38
unibon です。こんにちわ。

引用:

さくらばさんの書き込み (2004-10-07 09:13) より:
引用:

unibonさんの書き込み (2004-10-07 08:03) より:
確かめてはいませんが、seek でメモリが大量に消費されるとは思えません。プログラムの他の個所が原因ではないでしょうか。


RandomAccessFile とはいえども、ファイルにはシーケンシャルにしかアクセスできない
のですから、seek で大きな数字をいれたら時間がかかってしまうのは当然だと思います。

これは違うと思います。やはり RandomAccessFile はシーケンシャルアクセスではなくランダムアクセスのはずです。
確かめるためにフロッピーディスクに1MBほどの大きさのファイルを入れて、seek(そのファイルの容量 - 10) したあと、read(10バイト)してみましたが、5秒ほどで読み込めました。ファイルをシーケンシャルで読んでたら数十秒はかかるはずです。
さくらば
大ベテラン
会議室デビュー日: 2002/11/12
投稿数: 145
投稿日時: 2004-10-07 17:47
こんにちは、さくらばです。

引用:

unibonさんの書き込み (2004-10-07 13:38) より:
引用:

RandomAccessFile とはいえども、ファイルにはシーケンシャルにしかアクセスできない
のですから、seek で大きな数字をいれたら時間がかかってしまうのは当然だと思います。

これは違うと思います。やはり RandomAccessFile はシーケンシャルアクセスではなくランダムアクセスのはずです。


ちょっと勇み足でした。すいません。
Java では FileInputStream クラスでも、RandomAccessFile クラスでも、JNI の部分で
はモードが違うだけで同じシステムコールを呼び出しています。ですから、OS がファイ
ルに対してランダムアクセスができるのであれば、ランダムアクセスになっていると思
います。

逆にいえば、Java のアプリケーションではどのようにランダムアクセスが実現されてい
るかは気にしなくてもいいということだと思います。でも、実現方法によって実行時間
が全然違うのですから、本当は気になるところでもありますね。

ところで、本題の方の
引用:

比較的、小さいナンバーを検索しているうちはいいのですが、大きいナンバーを検索し
ていると、フリーメモリーの現象量が大きくなって来ています（すぐにフリーメモリー
の量が少なくなってしまいます）。そのせいなのかはわからないのですが、途中でぴ
たっとプログラムが止まってしまいます。

に関してですが、これだけだとどこに原因があるかはよく分かりません。できれば追試が
できるようなコードを示していただけるといいのですが...
1

スキルアップ／キャリアアップ（JOB@IT）