Zeitliche Komplexität von System.arraycopy(...)?

Question

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) ist eine einheimische Methode.

Wie hoch ist der Zeitaufwand für diese Methode?

Answer 1

Dazu muss es alle Elemente des Arrays durchgehen. Array ist eine einzigartige Datenstruktur, bei der Sie bei der Initialisierung eine Größe angeben müssen. Ordnung wäre die Größe des Quellarrays oder in Big O ausgedrückt seine O(Länge).

Dies geschieht in der Tat intern in einer ArrayList. ArrayList umhüllt ein Array. Obwohl ArrayList wie eine dynamisch wachsende Sammlung aussieht, führt es intern eine Arrykopie durch, wenn es erweitert werden muss.

Answer 2

Ich habe einige Nachforschungen angestellt und später beschlossen, einen Testcode zu schreiben, den ich hier vorstelle.

Mein Testcode ist unten angegeben:

import org.junit.Test;

public class ArrayCopyTest {

  @Test
  public void testCopy() {
    for (int count = 0; count < 3; count++) {
      int size = 0x00ffffff;
      long start, end;
      Integer[] integers = new Integer[size];
      Integer[] loopCopy = new Integer[size];
      Integer[] systemCopy = new Integer[size];

      for (int i = 0; i < size; i++) {
        integers[i] = i;
      }

      start = System.currentTimeMillis();
      for (int i = 0; i < size; i++) {
        loopCopy[i] = integers[i];
      }
      end = System.currentTimeMillis();
      System.out.println("for loop: " + (end - start));

      start = System.currentTimeMillis();
      System.arraycopy(integers, 0, systemCopy, 0, size);
      end = System.currentTimeMillis();
      System.out.println("System.arrayCopy: " + (end - start));
    }
  }

}

Das Ergebnis ist wie folgt

for loop: 47
System.arrayCopy: 24

for loop: 31
System.arrayCopy: 22

for loop: 36
System.arrayCopy: 22

Bragboy hat also recht.

Answer 3

Hier ist ein Teil des relevanten Quellcodes von OpenJDK 8 (openjdk-8-src-b132-03_mar_2014). Ich fand ihn mit Hilfe von Quellcode der nativen Java-Methode (Anmerkung: Die Anweisungen dort sind verwirrend; ich habe die Quelle nach relevanten Bezeichnungen durchsucht). Ich denke Kommentar von Kapitän Ford korrekt ist, d.h. es gibt (viele) Fälle, in denen die Iteration jedes Elements nicht notwendig ist. Beachten Sie, dass die Nicht-Iteration jedes Elements nicht bedeutet, dass unbedingt O(1) bedeuten, sondern nur "schneller". I denken dass eine Array-Kopie grundsätzlich O(x) sein muss, auch wenn x nicht die Anzahl der Elemente im Array ist; d.h., egal wie man es macht, das Kopieren wird teurer, je mehr Elemente im Array sind, und wenn man ein sehr großes Array hat, dauert es linear lange. Caveat: Ich weiß es nicht für bestimmte dass dies der eigentliche Quellcode für das Java-Programm ist, das Sie ausführen, sondern nur, dass es sich um den nur Implementierung, die ich in den OpenJDK 8-Quellen finden konnte. I denken dass dies eine plattformübergreifende Implementierung ist, aber ich könnte mich irren - ich habe definitiv nicht herausgefunden, wie man diesen Code erstellt. Siehe auch: Unterschiede zwischen Oracle JDK und Open JDK . Das Folgende stammt aus: /openjdk/hotspot/src/share/vm/oops/objArrayKlass.cpp

// Either oop or narrowOop depending on UseCompressedOops.
template <class T> void ObjArrayKlass::do_copy(arrayOop s, T* src,
                               arrayOop d, T* dst, int length, TRAPS) {

  BarrierSet* bs = Universe::heap()->barrier_set();
  // For performance reasons, we assume we are that the write barrier we
  // are using has optimized modes for arrays of references.  At least one
  // of the asserts below will fail if this is not the case.
  assert(bs->has_write_ref_array_opt(), "Barrier set must have ref array opt");
  assert(bs->has_write_ref_array_pre_opt(), "For pre-barrier as well.");

  if (s == d) {
    // since source and destination are equal we do not need conversion checks.
    assert(length > 0, "sanity check");
    bs->write_ref_array_pre(dst, length);
    Copy::conjoint_oops_atomic(src, dst, length);
  } else {
    // We have to make sure all elements conform to the destination array
    Klass* bound = ObjArrayKlass::cast(d->klass())->element_klass();
    Klass* stype = ObjArrayKlass::cast(s->klass())->element_klass();
    if (stype == bound || stype->is_subtype_of(bound)) {
      // elements are guaranteed to be subtypes, so no check necessary
      bs->write_ref_array_pre(dst, length);
      Copy::conjoint_oops_atomic(src, dst, length);
    } else {
      // slow case: need individual subtype checks
      // note: don't use obj_at_put below because it includes a redundant store check
      T* from = src;
      T* end = from + length;
      for (T* p = dst; from < end; from++, p++) {
        // XXX this is going to be slow.
        T element = *from;
        // even slower now
        bool element_is_null = oopDesc::is_null(element);
        oop new_val = element_is_null ? oop(NULL)
                                      : oopDesc::decode_heap_oop_not_null(element);
        if (element_is_null ||
            (new_val->klass())->is_subtype_of(bound)) {
          bs->write_ref_field_pre(p, new_val);
          *p = *from;
        } else {
          // We must do a barrier to cover the partial copy.
          const size_t pd = pointer_delta(p, dst, (size_t)heapOopSize);
          // pointer delta is scaled to number of elements (length field in
          // objArrayOop) which we assume is 32 bit.
          assert(pd == (size_t)(int)pd, "length field overflow");
          bs->write_ref_array((HeapWord*)dst, pd);
          THROW(vmSymbols::java_lang_ArrayStoreException());
          return;
        }
      }
    }
  }
  bs->write_ref_array((HeapWord*)dst, length);
}

Answer 4

Ich möchte nur relevante Kommentare zu einer anderen Frage zusammenfassen (die als Duplikat dieser Frage gekennzeichnet ist).

Sicherlich fügt es dem neuen Array einfach alle Einträge der anderen? Das hieße O(n) donde n ist die Anzahl der zu addierenden Werte.

Die Antwort von bragboy stimmt natürlich, aber ich hatte gedacht, dass die einzige Möglichkeit, eine sichere Antwort zu bekommen, darin besteht, den Quellcode zu finden, um den eine kanonische Antwort aber das ist nicht möglich. Hier ist die Erklärung für System.arraycopy();

public static native void arraycopy(Object src, int src_position,  
                                    Object dst, int dst_position,  
                                    int length);

Es ist native in der Sprache des Betriebssystems geschrieben, was bedeutet, dass die Implementierung von arraycopy() ist plattformabhängig.

Zusammenfassend lässt sich also sagen, dass es wahrscheinlich ist O(n) aber vielleicht auch nicht.

Answer 5

Ich verstehe nicht, wie Kowsers Antwort seine eigene Frage beantwortet. Ich dachte, um die Zeitkomplexität eines Algorithmus zu überprüfen, muss man seine Laufzeit für Eingaben unterschiedlicher Größe vergleichen, etwa so:

import org.junit.Test;

public class ArrayCopyTest {

  @Test
  public void testCopy() {
    int size = 5000000;
    for (int count = 0; count < 5; count++) {
      size = size * 2;
      long start, end;
      Integer[] integers = new Integer[size];
      Integer[] systemCopy = new Integer[size];

      start = System.currentTimeMillis();
      System.arraycopy(integers, 0, systemCopy, 0, size);
      end = System.currentTimeMillis();
      System.out.println(end - start);
    }
  }

}

Ausgabe:

10
22
42
87
147