System.arraycopy(...)的时间复杂度是什么？

Question

System.arraycopy(...)的时间复杂度是什么？

javaalgorithmtime-complexity

40

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 是一个本地方法。

这个方法的时间复杂度是多少？

- Kowser

任何与复杂性有关的参考都是值得赞赏的。 - Kowser

请参考以下网址：https://dev59.com/BHE85IYBdhLWcg3wdDIM - Alvin Wong

5个回答

5

我进行了一些调查后，决定编写测试代码，以下是我的代码。

我的测试代码如下：

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));
    }
  }

}

它生成如下所示的结果。

for loop: 47
System.arrayCopy: 24

for loop: 31
System.arrayCopy: 22

for loop: 36
System.arrayCopy: 22

所以，Bragboy是正确的。

- Kowser

1

+1 - 那个测试是在哪个操作系统上运行的？因为正如我最近的回答中所详细说明的那样，arraycopy() 的实现可能会依赖于平台。 - Rudi Kershaw

当时我使用的是最新版本的Ubuntu操作系统。我的电脑是联想ThinkPad i5处理器，8GB内存。我记不清楚操作系统和电脑的具体细节了。 - Kowser

你在温暖的Java环境和大数值上测试过它吗？ - Grigory Kislin

@GKislin 不，只是简单地运行。 - Kowser

@Kowser但这些数字毫无意义。我还发现了另一种度量方法：https://faisalferoz.wordpress.com/2007/12/24/loop-vs-systemarraycopy/，但我不确定它是否正确。 - Grigory Kislin

@GKislin 不错的发现。我想看到多次运行的平均值。读这篇文章很有趣。它考虑了不同的数组大小，这是一件好事，因为我们可以看到不同的数组大小所花费的时间也不同。那么这里的 O(?) 是什么呢？显然我的性能分析并不完美；-）我很想知道。深入挖掘JDK源代码可能会有帮助。你有什么想法吗？ - Kowser

5

这是来自OpenJDK 8的一些相关源代码（openjdk-8-src-b132-03_mar_2014）。我在Java本地方法源代码的帮助下找到它（请注意：那里的说明很混乱；我只是在源代码中搜索相关标识符）。我认为Captain Ford的评论是正确的；也就是说，有（许多）情况下不必迭代每个元素。请注意，并非对每个元素进行迭代不一定意味着O（1），它只是“更快”。我认为，无论如何，数组复制必须从根本上是O（x），即使x不是数组中项的数量；也就是说，无论你怎么做，随着数组中元素的增加，复制变得越来越昂贵，如果你有一个非常大的数组，它将花费线性长的时间。警告：我不确定这是否是您正在运行的Java的实际源代码；我只知道这是我在OpenJDK 8源中找到的唯一实现。我认为这是跨平台实现，但我可能是错的--我绝对没有弄清楚如何构建这个代码。另请参见：Oracle JDK和Open JDK的区别。以下内容来自：/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);
}

- Hawkeye Parker

2

总结另一个问题的相关评论（标记为本问题的重复）。

当然，只需将所有条目添加到新数组中即可。这将是O（n），其中n 是要添加的值的数量。

bragboy的答案当然也同意，但我曾经认为获得确定答案的唯一方法是找到源代码以获得规范答案，但这是不可能的。这里是System.arraycopy（）的声明。

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

这段代码是使用操作系统的语言编写的 native，这意味着 arraycopy() 的实现取决于平台。

因此，总的来说时间复杂度可能是 O(n)，但也有可能不是。

- Rudi Kershaw

“...找到源代码是不可能的...”，但你可以获取本地方法的源代码。请参阅Java本地方法源代码。 - Hawkeye Parker

1

@HawkeyeParker，你可以获取特定平台上本地方法的源代码。当然，这并不能告诉你在所有其他平台上该本地方法可能会是什么样子。有可能存在针对新系统的糟糕实现。 - Rudi Kershaw

我同意。当然，想要确切地知道，你肯定需要实际运行的代码的真实源代码。 - Hawkeye Parker

1

我不明白Kowser的回答如何回答他自己的问题。我认为要检查算法的时间复杂度，你需要比较不同大小的输入所需的运行时间，就像这样：

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);
    }
  }

}

输出：

- MaxNevermind

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bragboy · Accepted Answer

30

要完成这个操作，必须遍历数组中的所有元素。数组是一种特殊的数据结构，在初始化时必须指定大小。在大O表示法中，其顺序将是源数组的大小或O(length)。

实际上，在ArrayList中会内部执行此操作。 ArrayList包装了一个数组。虽然ArrayList看起来像是一个动态增长的集合，但是在内部当它需要扩展时，它执行的是arraycopy操作。

- bragboy

5

O(n)已经足够接近，但实际上我认为它只是O(length)，即要复制的长度，而不是源数组的长度。 - Robert Harvey

5

你能否举个整数转换为字符串的例子？我认为arraycopy没有进行任何转换，根据文档：

否则，如果以下任一条件成立，则抛出ArrayStoreException…°src参数是具有原始组件类型的数组，而dest参数是具有引用组件类型的数组 °...

- user85421

9

回答不正确！system.arrayCopy是一个本地方法，可使用单个memcpy / memmove实现。 - jdramaix

3

对于多种数据类型，它并不需要遍历所有元素。对于许多数据类型，它能够进行块拷贝，这样可以更快地完成操作。只要数组类型相同，就不需要进行任何类型检查。如果源数组和目标数组是相同的，那么速度会稍微变慢一些（取决于平台，可能会慢很多！），但通常情况下，System.arraycopy 比迭代更加高效。 - Captain Ford

4

一次memcpy/memmove的时间仍与复制量成比例，而且它并不总是一次memcpy/memmove（由于类型检查和转换）。 - user2357112

显示剩余9条评论