[過去ﾛｸﾞ] Rust part20 (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
940: 2023/08/07(月)18:18 ID:UTlzilSe(1) AAS
VecDequeもその名の通りVec(正確にはどちらもRawVec)で作られていて
確保されている連続領域に対して未使用領域が末端か途中かの違いしかない
>>932は確保されている連続領域が埋まった時のコストを気にしているようだが
サイズNが埋まるまでの再配置の総コストは最悪ケースでもわずかN-1回の読み書きコストで済む
例えばサイズN/2が埋まった時にその倍のサイズNの新たな連続領域へ再配置するためにはN/2回の読み書きが発生
仮に最悪ケースでサイズ1からスタートしてもそれまでの累積の再配置コストはN/2+N/4+N/8+...+1 ＝ N-1が上限値となる
つまりサイズNが埋まるまでの再配置の総コストは最悪のケースで読み書きN-1回でありO(N)で済む
一方でサイズNが埋まるまでの再配置以外の読み書きが何回行われるかを今回のケースで考えると
次々とサイズが倍々に増えていく計算の場合は最小でも合計O(N)回の読み書きが起こり
次々とサイズがリニアに増えていく計算の場合は最小でも合計O(N^2)回の読み書きが起こり
もっと緩やかにサイズが増える場合や上述の増え方の場合でも普通に読み書きが多い計算なら合計O(N^2)を超える
現実のほとんどの計算においてVecの再配置コストO(N)は誤差となる
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.033s