- 139 名前：名前は開発中のものです。 mailto:sage [2008/11/25(火) 13:07:00 ID:iVVKZxJp]
- >>137
もっともらしくウソついてんじゃねーよ
わざと言ってんだろ。明らかに初学者に対して悪意のあるウソだな
>リストは単純に舐めるだけでも遅い
誤り。「単純に舐める」＝シーケンシャルアクセスに有意差はない。
配列が有利なのはランダムアクセスの場合。
>データの検索（巡回）よりも追加と削除のほうが多いゲームなどない
比較方法の誤り。巡回回数と挿入回数を単純に比較しても意味はない。
コストの違いは以下のようにO記法で考えると分かりやすい。
・シーケンシャルアクセス（巡回）のコスト
配列はO(n)：要素数が増えると処理時間が増える
リストもO(n)：要素数が増えると処理時間が増える
・ランダムアクセス（インデクス値でアクセス）のコスト
配列はO(1)：要素数が増えても処理時間は変わらない
リストはO(n)：要素数が増えると処理時間が増える
・挿入、削除のコスト
配列はO(n)：要素数が増えると処理時間が増える
リストはO(1)：要素数が増えても処理時間は変わらない
O(1)はO(n)に対して非常に有利なので、
ランダムアクセスがありそうなら配列を、挿入がありそうならリストを選ぶのが一般的。
どちらもありそうなら実際に処理時間を計測してみるのが良い。
処理時間とは別に、メモリのフラグメントを嫌ってリストを避けたい場合は、
データ本体は配列構造に置き、管理はＺソートされたリスト構造に、
というように両方を組み合わせる手法もある（C++オブジェクトをメモリプールするのと同じことだけどね）。
とにかく、初学者は「どっちが勝ち」みたいな議論に振り回されないこと。
ぶっちゃけ実際に動かしてみて問題がないなら、なんであれそのやり方は正しい。
|
 |
