データの管理の方法について

Question

私は中学生です。
休日や平日の暇な時間を使って、趣味でプログラミングをしています。
今回、私は数百体の生物を肉食・草食などに分け、食物連鎖の世界を模倣しようと考えています。
このプログラムでは百単位の大量なデータを扱うことになり、また、生物の死亡・生殖などもシミュレートしようと思うので、
データを途中で追加・削除することのできるSTLのlistクラスを使用しようと考えました。

ここで質問なのですが、このようなプログラムの場合、listクラスを使うのは正しいでしょうか？
それとも、普通の配列変数を使ったり、他の方法でデータを管理したほうがよいでしょうか？

私はいくつかの参考書や、ネットでの情報を見てきましたが、
いままでlistクラスを使ったプログラムは一度も見たことがありません。
どなたか回答をお願いしますｍ(_ _)ｍ

GOOD-Fr · Accepted Answer

「趣味のプログラム」ということなので、細かい突っ込みはどうかとは思いましたが・・・。

時間があるときにちょこちょこ、という感じでプログラムを楽しんでいるのだと文章から想像します。「今度はどの STL クラスを使おうかな」と考えている時間もきっと楽しいんだと思いますが、たぶん本当に楽しいのは「食物連鎖の世界を模倣」する「本当のプログラム」をしているときですし、それが完成して「世界」を見ているときではないかと思います。

そういう意味では、STL を選んだり使い方を覚えたり、というのは、「あまり楽しくない」ほうのプログラムに入るはずです。もちろん、「趣味のプログラム」ですから、いつのまにか食物連鎖の話を忘れてしまって、「STL を覚えた」だけになってしまったとしても、それはそれで「面白かったし、有意義だった」という考え方もあると思います。ですが、やはり「ライブラリの使い方」を考える時間があるのなら、「本質的な部分」に目を向けたほうが有意義だと思います。

さて、質問者の方は「とりあえず配列でテストをしてみた」と言っています。つまり、STL は使わなくても「制限事項付きならなんとか動作する」わけですね。それなら、いっそ、配列で作ってしまったらいいんじゃないでしょうか？

「配列は要素数が限られてるから、今回みたいに数が決まってなかったり、あとから数が増えるときには使えないので、STL を使おうと考えたんです」と言うでしょう。それは確かに正しいです。が、たかだか（この「たかだか」は数学用語の「たかだか」です）「100単位のデータ」を扱えればいいだけなら、とりあえず１ケタ、それでも心配なら２ケタ上の 10000要素の配列を確保すればいいのです。仮に１要素のデータが10KB あるとしても、この配列のためのメモリは「たかだか 100MB」に過ぎません。実際、BLOB データを含まない、数値や文字のデータだけで 10KB というのは、１要素としてはとてもたくさんのデータだと思います。（４バイト整数で 2500個にもなります）　今日のメモリ量から考えて、100MB 程度は大したことはありません。ギガバイトクラスのメモリを搭載しているパソコンはめずらしくありませんよね。2GB のメモリのうちの 100MB は「たかだか 5%」にしか過ぎないのです。この程度のメモリをどうするか悩む暇があるのなら、「確保しちゃったほうがよほど簡単」だと思います。

つぎに、「百単位の大量なデータ」を扱うので、STL のどのクラスを選ぶかが重要だ、ということですが、これはすでに書いたように大きなポイントではありません。
なぜか？STL のパフォーマンステストをするときはたいてい 10万以上の数を相手にしています。さきほど list クラスで実測してみましたが、10万件の push_front や push_back、イテレータを使ってすべての要素にアクセスのどれもが 100ms から速いものでは 25ms で完了しています。つまり、１つの要素へのアクセスに要する時間は「１マイクロ秒」もかからないのです。

「それでもほんのわずかでも速いほうがいい」というのも、正しい考え方でしょう。では、あるプログラム全体の実行時間で 10% が STL の内部でとられていたとします。（ひとつのライブラリで 10% もの計算時間を消費する、というのは、普通では考えられないほど大きな値です）　あなたがクラスを選びなおして、「STL に関して２倍の速度」のクラスを見つけたとします。実行時間はどのくらいになるかというと、10% が半分になるわけですから、5%。これに他の部分の実行時間を足して 95% になります。逆にクラス選択がよくなくて、「２倍の時間がかかる」ものを選んだとします。この場合、STL 部分が倍になって 20%、これに 90% を足しますから 110% です。
100% が 95% になっても 110% になっても、大した差とは言えません。それなら、残りの 90% の部分をアルゴリズムなどの工夫で「ほんの１割」向上するだけで、このプログラムは 91% の実行時間で動作することになります。半分にできれば 55% です。どうせ頭と時間を使うのなら、「STL 選び」よりも「もっと速いアルゴリズム」に使うほうが楽しいですよね。実際のプログラムでは STL だけで 10% もの時間を消費してしまうことはありえません。たぶんかなり多く見積もっても、たかだか 2%、現実的なところでは 0.1%以下でしょう。多少、クラス選択を間違えたところで、全体の実行時間の中では誤差です。ストップウォッチを握りしめないとわからない程度の差をつめるために、プログラム作成が止まったままになってしまったのではもったいないと思いませんか？

最後に「vectorなどは削除・挿入などにかなりの時間がかかると聞いていました」ということですが、なるほど、よく勉強しているようですね。事前にいろいろ調べるのはいいことだと思います。でも、ちょっと頭でっかちになってるようですね。速い、遅い、と論議したところで、アクセスに要する時間はマイクロセカンドの単位です。100万回のアクセスでやっと１秒なのですから、大した問題ではありません。こういうところこそ、テストしてみるべきです。さらに、「かなりの時間がかかる」というのは、あくまでも大量のデータを相手にした場合の話で、計算機の世界で「大量」というのは、100とか1000ではありません。少なくとも数十万とか、最近なら数億などの単位です。このように「要素が１ケタ増えた時」などの計算時間を見積もるのにつかわれるのが「オーダー」です。

STL など、標準ライブラリはさすがによく作られていて、「悪くても N のオーダー」、いいものは「Log N のオーダ」もしくは「要素数に寄らず一定」です。Log N のオーダーというのは、実はかなり優秀で、要素数が１ケタ増えても計算時間は３倍程度にしかなりません。アルゴリズムが悪い場合、オーダーは N^2 から N^3 になることがありますから、N や Log N なら、「とてつもなく優秀」なアルゴリズムと言ってもいいのです。
質問者の悩んでいる「100単位の要素数」は最小単位の「１」と比較しても、わずか２ケタの差しかありません。この程度なら、N でも Log N でも数倍程度の差にしかならないのです。そして、計算時間全体に占める割合から考えると、STL のところで数倍程度の差がついたところで、全体の時間としては誤差の範囲になります。結論から言うと「どれを選んでもいっしょ」という答えになります。

最後になりますが、STL の中で list は vector と同じくらいよく使われるメジャーなクラスです。「そもそも、STL を使ってる人がいない」という話はともかく、STL 使いの中では多用されるほうだと思って間違いないでしょう。また、これが大事なポイントですが、STL はクラスを変えても要素へのアクセスのしかたがほとんど／まったく変わらないことが特徴です。つまり、とりあえずどれかの STL で作っておいて、あとで STL クラスだけ変更、ということが比較的簡単にできます。そういう意味でも、「どの STL にしようかなー」と悩んでしまってプログラムが進まない、というのは、あまりにももったいない、と思います。


「趣味のプログラムなんだから、好きなように楽しめばいい」と、思いましたが、あえていろいろと書いてみました。テストをしながらプログラムを進めている点など、とても「すじがいい」と思うので、あえて細かいこともいいましたが、言いたかったことは「本当に大事なことってなに？」ってことです。

「要素数が確定してないから、とりあえず必要量の２ケタ上ぐらい確保してしまえ」、「STL の使い方を悩んでいる時間があれば、配列でやっちゃえ」など、自分でも乱暴なところはかなりあると思っていますが、こんなところで止まっている時間があるのなら、ぜひ「食物連鎖の世界」を早く見たいものだ、と思ってあえて突っ込んでみました。お役にたてば幸いです。

GOOD-Fr · Answer

この勘違いは、いただけません。

> 一回、普通の配列変数で実装し、あたり判定をしてみたところ、100体でもかなりの負担がかかったので、大量のデータに入ると思っていました

サンプルでプログラムを作ってみて、あらかじめパフォーマンス等を確認する、という方法はとてもいいと思います。全部できあがっていざ動作させたら、計算の終了まで 100年かかるとわかった、では、報われませんから。

ですが、質問者の方がテストしているのは「あたり判定」のテストで、この処理が重かった、ということですよね。であれば、これは STL 以前の問題のはずです。どの STL クラスを使うのがいいか、というのは、それぞれのクラスの特性もありますが、あくまでもデータの出し入れや検索する時間などの差で決めるべきことです。が、今回の場合、時間がかかっているのは「取り出したデータを加工する」部分ですから、どのクラスを選ぼうと速度に関係ありません。

テストをしながらプログラムを進めるのはとてもいいことですが、テストの結果を正しく解釈しなければテストの意味がありません。質問者がおっしゃっていることは「データの格納方法にかかわらず、データの処理が重い」ということです。この処理に時間がかかるから「100件は大量のデータであり、STL で処理したらもっと重くなるに違いない」という考察は残念ながら的外れですね。

GOOD-Fr · Answer

> このようなプログラムの場合、listクラスを使うのは正しいでしょうか？

まちがいではないでしょう。
が、これだけでは判断できません。要求されているのは「データを途中で追加・削除することのできる」ということだけです。それなら、list でなくても、deque でも map でも set でも vector でもかまわないことになります。「百単位の大量なデータ」ということですが、この程度は「大量」には入らないので、どれを使ってもパフォーマンスも大差ないでしょう。

> いままでlistクラスを使ったプログラムは一度も見たことがありません。

そうですか？
Java なので厳密には STL ではありませんが、List を使っているのとか見かけますけどね。

ecogilis · Answer

こんにちわ。

listは、追加と削除の操作を高速に行う目的で考案されましたので、そのような操作は高速ですが、代わりにインデックスによる管理がされませんので、ランダムアクセスに向きません。
また、オンメモリ操作になるので、生物1固体あたりのデータ量と、個体数の最大を併せてメモリ内に収まりそうか、も判断の基準のひとつだと思います。

ランダムアクセスが必要無くデータ量としても少量であるならlistでいいと思います。

データの管理の方法について

「趣味のプログラム」ということなので、細かい突っ込みはどうかとは思いましたが・・・。

この勘違いは、いただけません。

> このようなプログラムの場合、listクラスを使うのは正しいでしょうか？

こんにちわ。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング