Komplexität von addAll() bei Collections

[Windwalker]

Hallo,

ich möchte mein Programm beschleunigen und hierbei eine große Schleifen-Iteration durch Mengen-Operationen ersetzen.
Hierbei benutze ich die Methode addAll(Collection c) und möchte alle Elemente eines großen Sets einem anderen anfügen.

set2.addAll(set1);

Da mein set1 sehr groß ist, interessiert mich nun, wie addAll() funktioniert.

for (Object o: set1)
  set2.add(o);

Falls es, wie hier im Beispiel, über alle Elemente von set1 iteriert und sie nacheinander set2 anfügt, dann würde meine alternative Implementierung keine Verbesserung mit sich bringen.

Wisst Ihr, wie die interne Funktionsweise von addAll() ist?
Danke!

 

[SlaterB]

Set und List sind nur Interface, theoretisch ist nichts dazu bekannt,

die Java-Standard-Collections erben aber alle von AbstractCollection,
dessen Quellcode sollte bei jedem JDK dabei sein (suche nach src.zip)

    /**
     * {@inheritDoc}
     *
     * 

This implementation iterates over the specified collection, and adds
     * each object returned by the iterator to this collection, in turn.
     *
     * 

Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is
     * overridden (assuming the specified collection is non-empty).
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     * @throws IllegalStateException         {@inheritDoc}
     *
     * @see #add(Object)
     */
    public boolean addAll(Collection<? extends E> c) {
	boolean modified = false;
	Iterator<? extends E> e = c.iterator();
	while (e.hasNext()) {
	    if (add(e.next()))
		modified = true;
	}
	return modified;
    }

da man über die andere Collection nicht viel mehr weiß als dass ein Iterator vorhanden ist,
wird es freilich nicht viel mehr andere Verfahren geben

 

[0x7F800000]

wird es freilich nicht viel mehr andere Verfahren geben

Das hoffe ich nicht. Es würde zwar so auch gehen, aber es wäre nicht die schnellste variante. Wenn man zB an ein ArrayList der größe 100 eine andere Collection der Größe 1000000 auf diese art und weise, element für element, added, dann muss der speicherplatz unterwegs ~13 mal neuallokiert werden, was total verschwenderisch ist. Da wäre es doch viel schöner, wenn man ArrayList zunächst darum bittet, von anfang an genug platz zu allokieren, und erst dann mit dem rüberkopieren anfängt.

Und wenn man ArrayList zu ArrayList added, wäre solche Schleife mit Iteratoren eh viel zu lahm: da beide auf arrays basieren, wäre man mit System.arraycopy wohl um einiges besser dran.

Da kann man an vielen Stellen was machen, ich hoffe mal, dass die API-Autoren das auch gemacht haben. Aber sicherheitshalber sollte man wohl in den quellcode schauen, wozu ich grad keine Lust hab

 

[SlaterB]

stimmt

ArrayList:

    /**
     * Appends all of the elements in the specified collection to the end of
     * this list, in the order that they are returned by the
     * specified collection's Iterator.  The behavior of this operation is
     * undefined if the specified collection is modified while the operation
     * is in progress.  (This implies that the behavior of this call is
     * undefined if the specified collection is this list, and this
     * list is nonempty.)
     *
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> if this list changed as a result of the call
     * @throws NullPointerException if the specified collection is null
     */
    public boolean addAll(Collection<? extends E> c) {
	Object[] a = c.toArray();
        int numNew = a.length;
	ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
	return numNew != 0;
    }

LinkedList machts auch mit Object-Array + speziellem add, obwohl mir dort ein Iterator mit normales add nicht groß anders erscheint

 

[0x7F800000]

jjaa, genau, ensureCapacity() klingt guuut