4

ArrayListなど、非常に一般的に使用されるクラスの一部については、公式のベンチマークがないようです。

挿入または削除のランタイムに関するドキュメントが見つかりませんでした。ArrayList に似たPython のListと比較すると、実行時の複雑さが十分に文書化されています (上記のリンクを参照)。

この投稿は、ArrayList からの要素の削除とコピーに関するある程度詳細なベンチマークを提供しましたが、正確な複雑さの分析はまだ提供していません。私は非常に長いデータ (〜 500,000 データ ポイント) を使用するプロジェクトに取り組んでいるため、ArrayList からのデータの削除または挿入が魔法のように一定の時間で動作すると仮定することはできません。この情報はどこで確認できますか?

4

1 に答える 1

2

Java の複雑さのクイック リファレンス:

しかし、実際には、ここで見つけることができるソースを見ることに勝るものはありません。

たとえば、ArrayList に追加するという特定の問題に関しては、次のことがわかります。

public boolean add(E e) {
           ensureCapacityInternal(size + 1);  // Increments modCount!!
           elementData[size++] = e;
           return true;
       }

この操作の複雑さは、明らかにensureCapacityInternalに依存します。

private void ensureCapacityInternal(int minCapacity) {
               modCount++;
               // overflow-conscious code
               if (minCapacity - elementData.length > 0)
                   grow(minCapacity);
           }

これはgrowに依存します:

private void grow(int minCapacity) {
           // overflow-conscious code
           int oldCapacity = elementData.length;
           int newCapacity = oldCapacity + (oldCapacity >> 1);
           if (newCapacity - minCapacity < 0)
               newCapacity = minCapacity;
           if (newCapacity - MAX_ARRAY_SIZE > 0)
               newCapacity = hugeCapacity(minCapacity);
           // minCapacity is usually close to size, so this is a win:
           elementData = Arrays.copyOf(elementData, newCapacity);
       }

したがって、成長操作は条件付きで行われ、多くの場合、追加は O(1) 操作になることがわかります。しかし、ここから配列が拡大する時期の詳細も確認できます。

于 2013-03-29T23:08:10.270 に答える