Java Collection addAlle Komplexität

Question

Gibt es eine Java-Sammlung mit einer Komplexität von O (1) und nicht O (n) für die addAll-Operation, oder muss ich meine eigene Sammlung implementieren? Mit einer effizienten verknüpften Liste sollte die Operation Collection1.addAll (Collection2) die zweite Sammlung an die erste anhängen, indem der erste Knoten von collection2 zum letzten von Sammlung 1 hinzugefügt wird und die anderen folgen. Aber es ist nicht so, dass ich in die Dokumentation lese, es scheint einen Iterator zu benutzen, also denke ich, dass die Komplexität O (collection2.size) ist.

Ist das richtig?

Answer 1

Auch die Optimierung für verknüpfte Listen funktioniert nur, wenn Sie Elemente von einer verknüpften Liste zu einer anderen verschieben.

Sie könnten eine eigene Art von Sammlung jedoch, die eine weitere Ebene der Indirektion, i. e. enthält eine Sammlung von Sammlungen. Auf diese Weise ist das Hinzufügen einer ganzen Sammlung ziemlich billig und wiederholt sich. Indizierung oder Längenbestimmung kann jedoch sehr teuer werden.

Answer 2

ArrayList ist wahrscheinlich in dieser Hinsicht so gut wie es geht, aber es hängt auch von der gelieferten Sammlung ab. Die Best-Case-Komplexität ist O (1), aber nur dann, wenn die toArray() Methode der bereitgestellten Collection ebenfalls eine konstante Komplexität aufweist.

Die System.arraycopy() Aufruf, der die tatsächliche Zuteilung tut ist O (1), ohnehin kompliziert ist, siehe unten:

// java.util.ArrayList.addAll 
// Oracle JDK 1.8.0_91 
public boolean addAll(Collection<? extends E> c) { 
    Object[] a = c.toArray(); // O(?) <-- depending on other type 
    int numNew = a.length; 
    ensureCapacityInternal(size + numNew); // Increments modCount 
    System.arraycopy(a, 0, elementData, size, numNew); 
    size += numNew; 
    return numNew != 0; 
} 

Es gibt einige Meinungsverschiedenheiten darüber, ob System.arrayCopy ist eine Konstante Zeitbetrieb . Some say no. Others suggest it is.

Nach to this benchmark I hacked together, es ist irgendwo in der Mitte. Die Copy Times bleibt bis zu 100 Array-Elementen ziemlich konstant, wird aber von da an linear. Ich vermute, dass dort eine Art Paging stattfindet. So effektiv System.arrayCopy hat lineare Zeit Komplexität, es sei denn, die Arrays sind sehr klein.