配列とリストの使い分け – プログラミング – Home

配列とリストの使い分け
 
通知
すべてクリア

[解決済] 配列とリストの使い分け

固定ページ 1 / 2

いしだ
 いしだ
(@いしだ)
ゲスト
結合: 17年前
投稿: 53
Topic starter  

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

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

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

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


引用未解決
トピックタグ
仲澤@失業者
(@uncle_kei)
Prominent Member
結合: 5年前
投稿: 828
 

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

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

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

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

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

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


返信引用
PATIO
(@patio)
Famed Member
結合: 3年前
投稿: 2660
 

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

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

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

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


返信引用
PATIO
(@patio)
Famed Member
結合: 3年前
投稿: 2660
 

すいません、私が書いた部分は既に理解されていると書かれていました。
蛇足でした。


返信引用
maru
 maru
(@maru)
ゲスト
結合: 17年前
投稿: 358
 

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
 ITO
(@ITO)
ゲスト
結合: 22年前
投稿: 1235
 

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

 


返信引用
ITO
 ITO
(@ITO)
ゲスト
結合: 22年前
投稿: 1235
 

訂正です。(^^;

>執拗としているのならば、

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


返信引用
いしだ
 いしだ
(@いしだ)
ゲスト
結合: 17年前
投稿: 53
Topic starter  

みなさんありがとうございます。

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

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

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


返信引用
PATIO
(@patio)
Famed Member
結合: 3年前
投稿: 2660
 

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

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

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

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


返信引用
PATIO
(@patio)
Famed Member
結合: 3年前
投稿: 2660
 

あうあう。

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

誤字でした。


返信引用
いしだ
 いしだ
(@いしだ)
ゲスト
結合: 17年前
投稿: 53
Topic starter  

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

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

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


返信引用
ITO
 ITO
(@ITO)
ゲスト
結合: 22年前
投稿: 1235
 

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

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

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


返信引用
ryo
 ryo
(@ryo)
ゲスト
結合: 23年前
投稿: 252
 

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

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


返信引用
maru
 maru
(@maru)
ゲスト
結合: 17年前
投稿: 358
 

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

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


返信引用
maru
 maru
(@maru)
ゲスト
結合: 17年前
投稿: 358
 

一番肝心なことを書き忘れた。

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

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


返信引用
固定ページ 1 / 2

返信する

投稿者名

投稿者メールアドレス

タイトル *

プレビュー 0リビジョン 保存しました
共有:
タイトルとURLをコピーしました