配列,list,vectorの実行速度比較

白い時空
記事: 18
登録日時: 14年前
住所: 埼玉県さいたま市

配列,list,vectorの実行速度比較

投稿記事 by 白い時空 » 14年前

龍神録をC++で作ってみようと思った時に、
弾などの配列をvector,listに変えたら実行速度はどうなるか気になったので実験。

それぞれint型の配列を作り、挿入・削除を繰り返しているだけです。
乱数で、毎回全部消さないようにしています。
ソースコード:
► スポイラーを表示
この設定にした所、私の環境では
array_time:236[ms]
vector_time:193[ms]
list_time:91[ms]
こうなりました。
使う配列数が多いと、listがかなり早いです。

ただ、使う配列数が100以下等小さい場合、vectorがlistより早くなりました。

色々試した結果、
結論:
配列が100を超える場合は、 array > vector > list
配列が100を超えず少ない場合は、array > list > vector

考察:
100辺りでvectorの実行速度が遅くなるのは、erase時に配列をずらしているのが原因かな。
だとすると、構造体などサイズが大きい場合は、100以下でもvectorが遅くなったりするかも。


ちなみにdequeでもやってみましたが、どの場合でもかなり遅いです。
最後に編集したユーザー 白い時空 on 2011年4月28日(木) 01:20 [ 編集 2 回目 ]

アバター
GRAM
記事: 164
登録日時: 14年前

Re: 配列,list,vectorの実行速度比較

投稿記事 by GRAM » 14年前

ちょっと比較方法がまずい気がします。特に配列は実際には代入操作を持って削除としているのでそりゃ速いに決まってるじゃないですかw
削除というのであれば文字通り配列をずらしてその要素をなくしてしまうべきなのでは?
そもそもコンテナは用途におおじて使い分けるべきものだと思うので、オールマイティーな操作と要素数でもって比較検討するのはちょっと・・・という気もします。
dequeも先頭からの挿入や削除が高速なのでキューの実装にはデフォルトで使われていますしね。
しかし要素数が100以下だとeraseを使ったとしてもリストよりvectorが速いというのは意外ですしおもしろい結果ですね。
(追加の部分の差がどれくらいかちょっとわかんないですが)