のドキュメントには次のようにArrayDeque書かれています:
このクラスは、スタックとして使用された場合は Stack よりも高速になり、キューとして使用された場合は LinkedList よりも高速になる可能性があります。
ArrayDequeをスタックとして使用する場合と を使用する場合の違いについては言及されていませんArrayList。 をArrayListスタックとして使用する場合は、次のようにします。
list.add(object); // push
object = list.remove(list.size() - 1); // pop
ArrayListこのようにのみを使用した場合、 のパフォーマンスは よりも劣ることがわかりましたArrayDeque。この違いの原因は何でしょうか? 単に の呼び出しだけが原因ではないはずです。内部的には、 とはsize()どちらも を使って実装されており、必要に応じて がより大きな配列に置き換えられるので、パフォーマンスはほぼ同じになるはずです。ArrayListArrayDequeObject[]
ベストアンサー1
両方の実装の主な違いはサイズ変更戦略です
ArrayListは新しいサイズ にサイズ変更されoldCapacity + (oldCapacity >> 1)、約 50% 増加します。デフォルトの容量は 10 なので、サイズ変更後の容量は 15、22、33、49、73、109、163、244、366... になります。ArrayDeque常に 2 の累乗にサイズ変更されます。サイズ変更すると、容量が 2 倍になります。デフォルトの 16 から始まり、サイズ変更後の容量は 32、64、128、256、... になります。
そのため、ArrayDeque は、配列のコピーのためにコストがかかるサイズ変更操作を大幅に減らして、より高い容量に到達します。つまり、デフォルト サイズの ArrayList に 256 を格納するには、9 回のサイズ変更呼び出しが必要ですが、ArrayDeque では 4 回しか必要ありません。配列のコピーは高速ですが、メモリ コピー コストに加えて、新しいデータ セット用にスペースを解放するための GC も必要になる場合があります (ArrayDeque は 2 の累乗に揃えられているため、パフォーマンスが向上する可能性もあります)。
headどちらのデータ構造も、 & tail(ArrayDequeue) または add(Last) size(ArrayList)のいずれかへの直接アクセスによるプッシュとポップの計算量は、最善の場合 O(1) です。