java System.arraycopy(...) 的时间复杂度？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7165594/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Time complexity of System.arraycopy(...)?
提问by Kowser
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)is a native method.
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)是本机方法。
What is the time complexity for this method?
这种方法的时间复杂度是多少？
采纳答案by bragboy
It will have to go through all the elements in the array to do this. Array is a unique data structure where you have to specify a size when you initialize it. Order would be the source array's size or in Big O terms its O(length).
它必须遍历数组中的所有元素才能做到这一点。数组是一种独特的数据结构，您必须在初始化时指定大小。顺序将是源数组的大小或在 Big O 术语中它的 O(length)。
Infact this happens internally in an ArrayList. ArrayList wraps an array. Although ArrayList looks like a dynamically growing collection, internally it does an arrycopy when it has to expand.
事实上，这是在 ArrayList 内部发生的。ArrayList 包装一个数组。尽管 ArrayList 看起来像一个动态增长的集合，但它在内部需要扩展时会执行 arrycopy。
回答by Kowser
I did some investigation and later decided to write a test code, here is what I have.
我做了一些调查，后来决定写一个测试代码，这是我所拥有的。
My testing code is given below:
我的测试代码如下：
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));
}
}
}
It produces result shown below
它产生如下所示的结果
for loop: 47
System.arrayCopy: 24
for loop: 31
System.arrayCopy: 22
for loop: 36
System.arrayCopy: 22
So, Bragboy is correct.
所以，Bragboy 是正确的。
回答by Hawkeye Parker
Here's some relevant source code from OpenJDK 8 (openjdk-8-src-b132-03_mar_2014). I found it with help from Java native method source code(note: instructions there are confusing; I just searched the source for relevant identifiers). I think Captain Ford's commentis correct; i.e., there are (many) cases where iterating each element isn't necessary. Note that not iterating each element doesn't necessarilymean O(1), it just means "faster". I thinkthat, regardless, an array copy must be fundamentally O(x), even if x isn't the number of items in the array; i.e., however you do it, copying gets more expensive with more elements in the array, and if you have a Very Big array, it will take a linearly Long Time. Caveat: I don't know for certainthat this is the actual source code for the Java you are running; only that this is the onlyimplementation I could find in the OpenJDK 8 source. I thinkthat this is a cross-platform implementation, but I might be wrong -- I definitely haven't figured out how to build this code. See also: Differences between Oracle JDK and Open JDK. The following comes from: /openjdk/hotspot/src/share/vm/oops/objArrayKlass.cpp
这是来自 OpenJDK 8 (openjdk-8-src-b132-03_mar_2014) 的一些相关源代码。我在Java 本机方法源代码的帮助下找到了它（注意：那里的说明令人困惑；我只是在源代码中搜索了相关标识符）。我认为福特船长的评论是正确的；即，有（许多）情况下不需要迭代每个元素。请注意，不迭代每个元素并不一定意味着 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);
}
回答by Rudi Kershaw
Just to sum up relevant comments on another question (flagged as a duplicate of this one).
只是总结对另一个问题的相关评论（标记为与此问题重复）。
Surely, it's just adding to the new array with all the entries of the other? Which would be O(n)where nis the number of values to be added.
当然，它只是将另一个条目的所有条目添加到新数组中？这将是O(n)，其中n是要添加的值的数量。
bragboy's answer agrees of course, but then I had thought that the only way to get a sure answer was to find the source code to get a canonical answer, but that isn't possible. Here is the declaration for System.arraycopy();
bragboy 的回答当然同意，但后来我认为获得确定答案的唯一方法是找到源代码以获得规范答案，但这是不可能的。这是声明System.arraycopy();
public static native void arraycopy(Object src, int src_position,
Object dst, int dst_position,
int length);
It's native, written in the language of the operating system, which means that the implementation of arraycopy()is platform dependant.
它是native用操作系统的语言编写的，这意味着它的实现arraycopy()是平台相关的。
So, in conclusion it's likely O(n), but maybe not.
所以，总而言之，它可能是O(n)，但也可能不是。
回答by MaxNevermind
I don't understand how Kowser's answer answers his own question. I thought to check the time complexity of an algorithm You have to compare its running time for inputs of different sizes, like this:
我不明白 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);
}
}
}
Output:
输出：
10
22
42
87
147
