2

ArrayListリストの最初または途中に挿入すると、常にパフォーマンスが向上しますが、リストの最後に追加するだけなのでO(n)、最後の挿入は維持できます。O(1)

O(1)最初に挿入を作成し、O(n)平均して挿入を作成する方法についての高レベルのアイデアがありますがO(n/2)、基になる配列構造でそれが可能かどうかはわかりません。

私のアイデア

実際にArrayListは、しきい値に達したときに自分自身を「サイズ変更」するより大きな配列であるため、リストの最後だけでなく、リストの先頭と末尾の両方でサイズを変更できないのはなぜですか? これにより、最初に挿入できるようになりO(1)、途中で挿入を書き換えて、挿入自体の最短ルートを取ることもできます。(たとえば、 index に挿入する場合、に移動するよりも移動する1方が簡単です)。02n

Sun が最初にこれを行わなかった理由について、私が考える答えは、Arrays.copyOfand の拡張子の書き方にあると思いますSystem.arrayCopy。どちらもリストの先頭から開始し、より大きな配列にコピーします。これら 2 つのメソッドの Sun ソース コードを確認しましたが、私の Java スキル レベルでは少し高度です。

質問

私の考えでは、これが機能するかどうかについての主な質問が 2 つあります。

1)まず、サブ配列をより大きな配列の真ん中に挿入するように書き換え/オーバーロードできますArrays.copyOfか?System.arrayCopy

2) それを行うことの Big O への影響は何ですか?

それで、これは良い考えですか、それともこれを実行不可能にする明らかな何かが欠けていますか?

前もって感謝します！

4

3 に答える 3

2

あなたのアイデアは完全に実行可能であり、両端で要素を追加および削除することが一般的なケースである両端キューの実装には非常に理にかなっています。ArrayListユースケースの 99% は最後に追加されるだけなので、 にはあまり意味がありません。

の性質に関するあなたの質問についてはSystem.arraycopy、

a）はい、ある配列の中央を別の配列の内容で上書きarraycopyするために使用できます。

b) Java の固定サイズの配列では意味がないため、配列に挿入arraycopyしません。

「配列に挿入する」という考えに最も近いのは、まったく新しい、より大きな配列を作成 arraycopyし、2 つの入力配列から適切な範囲を ing することです。結果として得られるパフォーマンスは最高です。

于 2013-11-10T19:04:00.720 に答える
1

あなたが説明するものは、の考え方と一致しませんArrayList。

an の要素の順序は、ArrayListそれらが挿入される順序によって定義されます (この場合、もちろんインデックスを指定しない限り、常に末尾に追加します)。

挿入順序ではなく、オブジェクトのメンバーの値によって順序が定義されている場合は、LinkedList.

于 2013-11-10T18:55:45.933 に答える