配列とリストの使い分け

[戻る]
いしだ 2011/01/05(水) 14:40:01
MFCアプリケーションで、あるオブジェクトの集合を扱うために
配列(CArray)とリスト(CList)のどちらを使うべきか考えています。
なお、今回はSTLは除かせていただきます。

Scribbleという古いMFCサンプルを調べていて疑問に感じたので、
質問させていただきます。

配列は中間要素へのアクセスが速い代わりに中間要素への代入や削除が遅い
というのはよく理解していることなのですが、
このサンプルでは、ストロークオブジェクト自体の集合はリスト形式で、
各ストロークごとの座標の集合はCPointの配列形式で扱っています。
座標情報自体も特にランダムアクセスをするような箇所は無く、
Addで追加していった座標の配列をあとからforループで参照しているだけのようなので
すが、
これはなぜ配列形式で扱っていると思われますでしょうか。

このような使いかたならリストのほうが適しているのではと思ったのですが。

仲澤@失業者 2011/01/05(水) 16:59:11
特にどちらで無ければいけないといったコードではありませんね。
m_strokeListはRemoveHead()を使っているので、この部分でやや有利
というだけのようです。
ストロークもCArray<CPoint,CPoint>なので、高速描画や、パス変換
等に有利とも言えませんね。描画も平凡な実装です。

たぶん、本アプリは、
1.ストロークの中身の点の削除や編集は行わないが、
2.ストロークごとの削除や編集は行う
という前提があるのでしょう。

>このような使いかたならリストのほうが適しているのではと思ったのですが。

一般にCArrayの弱点が露呈した段階でリストに切り替えるのが吉といえます。
本アプリの場合は

typedef CArray< POINT> POINT_ARY;
class CStroke
 :public POINT_ARY
{};

の様に実装したほうが後々の機能追加が有利かも知れませんねぇ(vv;)。

PATIO 2011/01/05(水) 17:15:46
CListのメンバー関数をMSDNで調べてみると解りますが、
配列内のデータを必ず先頭から順番に見て行く方法で
アクセスするだけであれば、CListで支障は有りません。
確か、CListの方がデータの追加等は早かったと記憶しています。
実際に実測した事は無いので今のPCでどの位の差が出るのかは
解りませんけれど。

逆に配列上のデータを添え字でアクセスしたい場合は、
CArrayを使った方が良い事になります。
それぞれのクラスで特徴がありますからMSDNできちんと
性質を調べて理解した上で使い分けるようにした方が
良いでしょう。

仲澤@失業者さんが書かれているように
一般的にCArrayの方が通常の配列に近い感覚で
使用できるため利用時の制約が少なく使いやすいのは確かです。
性能上の問題が無いのであれば、CArrayの方が融通が利きます。
後から添え字で直接参照する必要が出た場合にも簡単に対応
できますし。

厳密にこう使わなくてはいけないというものでは無いので
よほど効率が悪い使い方をしない限りはどちらで対応しても
良いのではないかと思います。

PATIO 2011/01/05(水) 17:21:40
すいません、私が書いた部分は既に理解されていると書かれていました。
蛇足でした。

maru 2011/01/05(水) 17:33:54
SCRIBBLEはあくまでサンプルであり、その目的は MSDN によれば、「広範な MFC の機
能を簡単に説明」することのようです。
http://msdn.microsoft.com/ja-jp/library/f35t8fts(VS.80).aspx

そして、SCRIBBLE で説明している「広範な MFC の機能」に、配列(CArray)とリスト
(CList)に関するものは含まれていません。従って、オブジェクトのコレクションが何
であろうと気にしていないわけです。
それで、何故 CList ではなく CArray を使っているかという理由は、、、
「サンプルの製作者」でないと分からないでしょう。

私の想像では、このサンプルを見る人は Windows プログラミングの初心者(多分 C 
言語のレベルも低い人)達なので、リスト構造より、配列の方が理解しやすいと思っ
た、のでは無いでしょうか。
配列なら添字でデータをアクセスできますが、リストだと関数経由になりますから、
その辺も分かりやすいと思います。

> MFCアプリケーションで、あるオブジェクトの集合を扱うために
> 配列(CArray)とリスト(CList)のどちらを使うべきか考えています。
それぞれの利点・欠点は分かっていらっしゃるようですので、そのオブジェクトの
アクセス方法に応じて使い分ければいいでしょう。

ITO 2011/01/05(水) 18:33:14
うーーん、
  「Scribbleで扱っているCPointの要素数が、CListを使わなくても気にならない
   量である。」
 と「サンプルの製作者」が判断して、初心者に分かりやすい「CArray」を使ったよう
に思います。
 僕も要素数が1000や2000を超えないと速度的に問題にならないと思います。
 
  逆に、「サンプルの製作者」も、CListをよく理解していて、より多くの要素数を執
拗としているのならば、CListをすすめるのではないでしょうか。
 

 

ITO 2011/01/05(水) 18:35:41
訂正です。(^^;

>執拗としているのならば、
 
   ↓ 修正
>必要としているのならば、

いしだ 2011/01/06(木) 09:30:49
[[解決]]
みなさんありがとうございます。

どちらを使っても速度などに大した違いは無いから、
扱いやすい配列のほうを使ってるという程度だろうということですか。

マイクロソフト自身がMSDNのCArrayの説明に
「頻繁に再割り当てするとパフォーマンスが低下する」などと書いてるのに、
MouseMoveのたびに平気でAddで追加してますし、
この程度の処理ならそこまで考えることもないのでしょうね。

マップは明らかに目的が異なりますが、
配列とリストはどちらでも使えるケースが多いため、
いつもどちらを使うべきが考えてしまいますが、
問題が実感できない限りは配列を使うようにしていこうかと思います。

PATIO 2011/01/06(木) 13:17:53
「頻繁に再割り当てするとパフォーマンスが低下する」
これに関しては領域拡張をどの位の感覚で行なうのかとかも
関係するので単純にCArrayの使用でどの程度パフォーマンスが低下する
のかはこの辺の兼ね合いもあると思いますよ。
パフォーマンスの低下に関してもどの程度低下するのかまで
言及されていませんから、本当にクリティカルなケースで無ければ
気にしなくても良いレベルの低下かもしれません。
あと、扱うデータの規模の問題も当然ありますし。

組み込み系や性能要求が厳しいシステムでは考慮する必要が
あるかもしれませんけれど、これも規模との兼ね合いでしょう。
結局、ITOさんが書かれているように

「Scribbleで扱っているCPointの要素数が、CListを使わなくても気にならない量である。」

と言うのがあたりなんじゃないかなと言う気もします。
「MouseMoveのたびに平気でAdd」もしかり。

PATIO 2011/01/06(木) 13:19:08
あうあう。

これに関しては領域拡張をどの位の感覚で行なうのかとかも
             ↓
これに関しては領域拡張をどの位の間隔で行なうのかとかも

誤字でした。

いしだ 2011/01/07(金) 09:06:13
> Scribbleで扱っているCPointの要素数が、CListを使わなくても気にならない量である

こういうのはやはり作って動かしてみないと実感できないのでしょうね。
MSDNの説明でいきなり「頻繁に再割り当てすると〜」なんて言われると、
今回のように配列とリストどっちにするべきか迷ってしまいます。

#ただ、この程度の量なら配列でもいいだろうとなると、
#今度はなぜストロークのポインタはリストなんだと思ってしまいます…。

ITO 2011/01/07(金) 11:04:10
ん?
>ヒント  配列を使う場合は、あらかじめ SetSize で配列のサイズを確定し、
>    メモリを割り当てます。SetSize を使用せずに要素を配列に追加すると、
>        配列が頻繁に再割り当てされ、コピーされます。頻繁に再割り当てと
>        コピーを行うとパフォーマンスが低下し、メモリ断片化の原因になります。
ここかな?
 .net 2003版で古いですけど。
web上のVC 2010版も似たようなことが書かれてます。

これは、
 SetSizeで最大の配列のサイズを設定しておかないと、サイズが分からないので頻繁
 にメモリーを割り当てます。
ってことだと思います。
....... SetSizeを参照して下さい。


 CArrayもC++のテンプレートを参考にしているので、調べてみるのもいいかも
知れませんね。

ryo 2011/01/07(金) 12:46:49
1ストロークがCListで管理してるのは
最近の描画ソフトになら大抵実装されてる
「1作業ごとのヒストリー」みたいのを想定し
「○個前のストロークだけ無かったことにできる」機能を
作れるようになってるんじゃないかな

一回のストロークに含まれるPoint数はたかがしれても
まじめに絵を描くとなると
全ストローク分を管理するには、膨大なサイズになりかねないし

maru 2011/01/07(金) 14:27:38
> 今回のように配列とリストどっちにするべきか迷ってしまいます。
他の人がどう使っているかは関係ないのではないですか?前にも書いたように、この
サンプルはコレクションの使い方のサンプルではありません。
あくまで、自分のアプリケーションでそのデータコレクションをどのようにアクセス
するかを考えるべきです。

>ヒント  配列を使う場合は、あらかじめ SetSize で配列のサイズを確定し、
>    メモリを割り当てます。SetSize を使用せずに要素を配列に追加すると、
>        配列が頻繁に再割り当てされ、コピーされます。頻繁に再割り当てと
>        コピーを行うとパフォーマンスが低下し、メモリ断片化の原因になります。
配列とリストを比べた場合、メモリ断片化の頻度はリストのほうが大きいのでは?
と思っています。ただ、配列の場合、要素の追加を行うと配列全体の再割り当てと
全要素のコピーを行うので、そのコストは明らかにリストより大きくなります。
このことを考えると、この場合(Scribbleサンプル)、座標は配列ではなくリスト
で管理するほうが正しいと思っていますが、座標の順次アクセスは描画処理の中な
ので、追加のコストより順次アクセスの高速性をとったのかも知れません。

maru 2011/01/07(金) 14:37:38
一番肝心なことを書き忘れた。

> 問題が実感できない限りは配列を使うようにしていこうかと思います。
問題を実感してからでは遅い場合があります。
最初は少ない量でテストしていたので問題にならなかったが、テストの後半で量を
増やしたら、速度で問題になった。というようなことが有ります。
このときに配列->リストをやろうとしても既にプログラム中に xxx[i] などのコード
が大量にコーディングされていたらどうしますか?

勿論、そうならないようにデータコレクションのアクセス方法を抽象化して利用者側
にそのデータ構造を隠蔽するなどの対策を講じるんですけどね。
データ構造の設計は大切ですよ。

いしだ 2011/01/18(火) 10:55:53
みなさんありがとうございます。

> SetSizeで最大の配列のサイズを設定しておかないと、サイズが分からないので頻繁
> にメモリーを割り当てます。
> ってことだと思います。

これはもちろん理解しているつもりです。
ドラッグによる座標の追加となると事前にサイズは設定できないでしょうし、
マウス移動のたびに追加していたら何度も再割り当てされるでしょうし、
そうなるとなんで配列で管理しているのかなという当初の疑問になったのです。

> 1ストロークがCListで管理してるのは
> 最近の描画ソフトになら大抵実装されてる
> 「1作業ごとのヒストリー」みたいのを想定し
> 「○個前のストロークだけ無かったことにできる」機能を
> 作れるようになってるんじゃないかな

たしかに、ストローク内の座標配列はそれ自体が一つの情報を表現していて
途中の座標のみをいじるようなことは無いのに対して、
各ストロークは一つ一つが独立した情報で、大量のストローク内から
任意のストロークを削除したり順番を入れ替えたりすることもあり得るので、
リストで表現するというのもわかりますね。

> データ構造の設計は大切ですよ。

十分肝に銘じさせていただきます。
今回の件では、どっちを使うべきかちゃんと考えてみようとして
MFCのScribbleサンプルを参照してみたら、
当初の疑問(なぜ座標を配列で?)になったのですが、

> 座標の順次アクセスは描画処理の中なので、
> 追加のコストより順次アクセスの高速性をとったのかも知れません

こういうのはMSDNのCArrayの説明やサンプルソースからは感じ取れず、
経験によるところが多いのでしょうね。

古いスレッドには追加発言できません。