過去ログ
No．１２３４ 配列よりも連結リストを使う利点
[戻る] [ホームページ]No.16437 |
連結リスト構造について 投稿者---Sciggepy(2004/08/30 22:01:02) |
||
Sciggepyです。 題名の通り、連結リスト構造についての質問ですが、配列よりも連結リストを使う利点には、どのようなものがありますか？ よく紹介されているものとして、 １．可変個のデータを扱う場合 ２．大量のデータに対する挿入や削除を行う場合 がありますが、１は配列でも可能ですし、２も挿入位置への移動にかかる時間を考えると、それほど有利とは思えません。 また、実際に起こった出来事なのですが、リストのノード数を何万という数にすると、確保したメモリ領域は1MBにも満たないのに、何MBものメモリを消費し、そのうち大幅なパフォーマンスの低下を引き起こしてしまいます。私のPCのメモリ容量は512MBですが、それでも速度が落ちることがありました。 その上での疑問です。 |
|||
| No.16439 |
Re:連結リスト構造について 投稿者---あかま(2004/08/30 23:05:50) |
||
>題名の通り、連結リスト構造についての質問ですが、配列よりも連結リストを使う利点には、どのようなものがありますか？ > >よく紹介されているものとして、 > >１．可変個のデータを扱う場合 >２．大量のデータに対する挿入や削除を行う場合 いや、もうこのまんまだと思います。 たいていのアルゴリズムはメモリと速度のトレードオフです。 「どっちが有利か」というのは問題に左右されますので一概には言えません。 >１は配列でも可能ですし、 でも、配列の拡張がめんどくさい（データ数が多くなると遅いかも）し、 無駄なデータ領域が発生する。 >２も挿入位置への移動にかかる時間を考えると、それほど有利とは思えません。 配列で追加の度に、後ろのデータをずらすのは辛い（やっぱりデータ数が多くなると…）。 とかでしょうか。 >また、実際に起こった出来事なのですが、リストのノード数を何万という数にすると、確保したメモリ領域は1MBにも満たないのに、何MBものメモリを消費し、 大抵はパフォーマンスのために領域サイズや位置が最適化されますので、確保した領域より大きくなります。 他にも要因があるかもしれません。 >そのうち大幅なパフォーマンスの低下を引き起こしてしまいます。私のPCのメモリ容量は512MBですが、それでも速度が落ちることがありました。 メモリ確保しすぎてHDDへのバッファリングが起きているのでは？ メモリの量もそうですが、OSに依存している気がします。 |
|||
| No.16440 |
Re:連結リスト構造について 投稿者---おでん(2004/08/30 23:22:08) |
||
> >１．可変個のデータを扱う場合 >２．大量のデータに対する挿入や削除を行う場合 > >がありますが、１は配列でも可能ですし、２も挿入位置への移動にかかる時間を考えると、それほど有利とは思えません。 > 片方向リストとして話しますが、本当でしょうか？ （データがファイルに格納されているなどして）最大数のわからない データの配列への格納はどうしますか？ また、リストの場合、挿入位置を検索してそこに挿入するのは確かに 手間（時間）がかかりますが、見つければそこに挿入するだけですね？ それに引き換え配列の場合は、位置を特定したらその後ろのデータを 全て移動しないと挿入できませんね？ どちらが楽（早い）でしょうか？ リストの挿入/削除は前後のデータにだけ依存して、それ以外のデータには 依存しない（検索時以外に見る必要が無い）のが特徴です。 100個のデータがあるリストor配列にデータを挿入する場合、 ・リスト→50回のポインタ手繰り＋挿入 ・配列→１回の位置決め＋50個のデータ移動＋挿入 になります。 #データが理想的にランダムな場合、既に設定されているデータ数の #５０％で挿入位置が見つかります。 あ！挿入位置って場所がわかってるんですよね？ 分からなければ、配列でも検索が必要ですね？ >また、実際に起こった出来事なのですが、リストのノード数を何万という数にすると、確保したメモリ領域は1MBにも満たないのに、何MBものメモリを消費し、そのうち大幅なパフォーマンスの低下を引き起こしてしまいます。私のPCのメモリ容量は512MBですが、それでも速度が落ちることがありました。 > 処理系依存の部分だと思います。 システムから切り出したメモリを上手に使う実装もあると思うし、 下手な（4バイトといわれてもページ単位・・・４〜８ＫＢ？・・・で システムメモリを取ってくるなど）処理系もあると思います。 |
|||
| No.16442 |
Re:連結リスト構造について 投稿者---ぽこ(2004/08/31 00:37:44) |
||
>また、リストの場合、挿入位置を検索してそこに挿入するのは確かに >手間（時間）がかかりますが、見つければそこに挿入するだけですね？ >それに引き換え配列の場合は、位置を特定したらその後ろのデータを >全て移動しないと挿入できませんね？ どちらが楽（早い）でしょうか？ データの使用分布が一様だとデータ数が多くなると配列の方が早いんでしょうかねえ。 |
|||
| No.16441 |
Re:連結リスト構造について 投稿者---Sciggepy(2004/08/31 00:20:43) |
||
ご返答ありがとうございました。 普通、30MB程度の割り当てでは、パフォーマンスの大幅な低下は起こらないはずですが、メモリブロックを大量に保持している場合は例外のようです。（試しに100MBを割り当てて、memsetで埋めてみましたが、パフォーマンスの低下は感じられませんでした。） |
|||