データ構造について構造体を使ったテクニックについての質問（ほぼ初心者）

質問

大学の研究で困っています。
数値計算をＣ（Ｃ＋＋）でやろうとしています。

枝が一本あって、その枝はノードのリストで作られています。その一つ一つのノードからまた新しい枝が作られています。新しい枝がない場合、float(精度を考えるとdoubleにしたい)型の情報を一つ持ちます。

全部で１億個くらいのノードをもつ予定です。（発展系はその二乗三乗と増えていきます。）そこでメモリを効率的に使うプログラミングを考えているのです。

struct leaf{
int init;
struct node top;
}

struct node{
struct node *next;
union pnt {
float *value;
struct leaf *sub;
} p;
}

この文法で動くのかまた他の方法があるかを聞きたくて書き込みしました。よろしくお願いします。（ＶＣ＋＋、Ｗｉｎ、２ＧＨｚ）

回答No.1

liar_adan · ベストアンサー

想定されているデータ型は(ご存じとは思いますが)「木(tree)」と呼ばれるもので、
アルゴリズム関係の本にはだいたい出てきます。
木を使う場合、
「二つのノードへのポインタを持つ」
「ノードに数値を記憶する」のが一般的な方法です。

質問のやり方では、共用体を使って数値とポインタをまとめようとしていますが、
この方法の問題は、
「入っているデータが、数値なのか、ポインタなのかわからない」
ところです。
正しい処理をするためには「これが数値かポインタか」を表す
フラグ変数を持たねばならず、そうするとメモリ節約の意味が無くなってしまいます。
普通に木を構成した方がいいかもしれません。

なお、
union pnt {
float *value;
struct leaf *sub;
}
のところでは、float *value;ではなくてfloat value;が正しいと思います。

一億個となると…どうかなあ。
一億って言ったら100メガですよね。
1ノードに16バイトかかるとしても1.6GB。
普通のPCの限界の2Gまでメモリを積んで、できるかできないかというところですね。
きついなあ…。

普通、こういうデータ構造では、ひとつひとつのノードごとに
malloc()を使ってメモリ確保をするのですが、
それだとmalloc()の管理用領域の分だけ無駄になるかもしれません。
配列を使って、ノード領域をまとめて確保し、
ポインタのかわりにlong型の「ノード番号」で管理する。
ポインタ参照のかわりに「ノード番号」→「実際のポインタへの変換」→「参照」の仕組を作っておく。
…という方法が考えられます。
こうしても、多少の節約になるくらいですが。

なお、「発展形はその二乗三乗」というのは、
現実に計算するのはたぶん不可能だと思います。
メモリ的にも無理だし、
仮に、1クロックで1ノードの処理が終わるとして(実際は10クロックぐらいはかかると思います)、
1億個の処理が完了するまでに0.05秒。
1億個×1億個だと、60日ぶっ通しで計算してできることになります。

ネガティブなこと書きましたが、できるところまでがんばってください。