C言語関係掲示板過去ログ７３８

C言語関係掲示板

過去ログ

No７３８　数百ＭＢの大規模な配列を使いたい

[戻る]　[ホームページ]

No.9114		数百ＭＢの大規模な配列を使いたいのですが投稿者---v__v(2003/08/29 14:26:03)
		はじめまして、よろしくお願いします。Ｃ言語は経験年数は長いのですが、それほど詳しくなく、ここ数日悩んでおり、お助け頂けないでしょうか。　本題ですが、５００ＭＢ、２００ＭＢなどの大きな配列（メモリ領域）を確保し、データを入れてソート等をした後、ファイル出力をしてデータファイルを完成させたいのですが、スタテック領域で１８ＭＢほどしか確保できず、困っております。何か良い方法はありますでしょうか？　マロックも試しましたが、ダメで１８MB程度まで。開発環境かＯＳの設定が悪いのかとも思っています。　現状は、ＨＤＤ上にファイルを書き出し、この操作で実現を検討しておりますが、ものすごい処理時間を要すと見られ、できればＰＣのメモリ上で実現したいのですが。　環境は、WIN2000,メモリ１GB、C++ビルダー５です。初心者的な基本が分かっていない質問かもしれませんがよろしくお願いします。

No.9116		Re:数百ＭＢの大規模な配列を使いたいのですが投稿者---あかま(2003/08/29 16:33:15)
		>１行毎に領域を確保したら何とかなりました。たぶんこれでいけると思いますが、200Mものメモリを確保すると、まず間違いなくHDD上に仮想メモリとして確保してしまいますので高速処理のためにメモリ上だけで…というのは多分無理です。前にハッシュを使いソートしたときにメモリを確保しすぎて逆に遅くなったことがあります。メモリの消費を抑えるために、元のファイルを分割してはどうでしょうか？例えば要素をアルファベット順に並べる時、元ファイルから要素を読み出して、その頭文字が'a'のファイル、'b'のファイル…'z'のファイルと作っていきます。その後ファイルごとにソートして、全てのファイルをアルファベット順にマージすれば元ファイルのソートができあがります。

No.9154		Re:数百ＭＢの大規模な配列を使いたいのですが投稿者---v__v(2003/09/02 12:47:21)
		>メモリの消費を抑えるために、元のファイルを分割してはどうでしょうか？ >例えば要素をアルファベット順に並べる時、 >元ファイルから要素を読み出して、その頭文字が'a'のファイル、'b'のファイル…'z'のファイルと作っていきます。 >その後ファイルごとにソートして、全てのファイルをアルファベット順にマージすれば元ファイルのソートができあがります。返事が遅れましたが、皆さん、アドバイスありがとうございます。結局、分割して１００個の個々にソートされたファイルを作成し、これを少しずつバッファリングして、大小比較をして、１つの統合ファイルに書き込むことで目的を達成できました。この時、何故かファイルは同時に２２個までしか開けない問題にあたりましたが、順次バッファリングすることで回避しました。ありがとうございました。

No.9169		Re:数百ＭＢの大規模な配列を使いたいのですが投稿者---たか(2003/09/02 20:38:12)
		マージソートというのをご存じでしょうか？これなら同時に開くファイル数を３個に抑えられます。(入力２個、出力１個もしくは入力１個、出力２個) バッファを全部ファイルに置くので速度的には遅くなるとお思いでしょうが、これが結構速くてnlog(n)、つまりクイックソートと同程度のオーダーです。もちろんファイルの入出力によるオーバーヘッドが大きいので小さいデータですとメモリ上のバブルソートにも負けるでしょうが、 Nが大きくなるとかなり高速であることを私の所で実験して確かめています。