シャドウアレイとは何ですか?どのように実装されますか?コンパイラの最適化について読んでいるときにこの用語に出くわしましたが、それに関する実質的なリファレンスは見つかりませんでした。
3 に答える
配列を使用して、リスト、キュー、スタックなどの動的にサイズ変更可能な抽象データ型を実装する場合、発生する明らかな問題は、配列自体が自由にサイズ変更されないことです。ある時点で、配列に十分なアイテムを追加すると、最終的にスペースが不足します。
この問題の単純な解決策は、使用されている配列のスペースがなくなるまで待ってから、新しい大きな配列を作成し、古い配列から新しい配列にすべてのアイテムをコピーして、新しい配列の使用を開始することです。
抽象データ型の実装を使用するシャドウ配列は、これに代わるものです。古い配列がいっぱいになるまで待つ代わりに、使用されている配列に満杯のしきい値が渡された後、2番目のより大きな配列が作成されます。その後、アイテムが古い配列に追加されると、複数のアイテムが古い配列からシャドウ配列にコピーされます。これにより、古い配列がいっぱいになると、そのすべてのアイテムがすでに新しい配列にコピーされます。
単純な「最後にすべてをコピーする」アプローチの代わりにシャドウ配列の実装を使用する利点は、各追加操作に必要な時間がはるかに一貫していることです。
私はそれを動的配列の一形態と考えています。
シャドウという用語は、優れたパフォーマンスでサイズを変更しようとするが、簡単なインターフェイスの背後に隠されている基礎となるアルゴリズムを指します。(たとえば、JavaのArrayList)
これはあなたが探しているものですか?(一番下までスクロールします。)