英文:
What is the time complexity of assigning multiple elements to the array using the notation that uses only a single code line?
问题
我是指这样的情况:
int[] array = {1, 2 , 3, 4, 5};
其中每个数组索引的赋值都在“单行代码中完成”。
我并不确定在背后会发生什么,但我想象中的情况是,它类似于对数组中的每个索引进行迭代,然后将输入的整数赋值给该索引:
for (int i = 0; i < array.length; i++){
array[i] = <给定的输入> //对于 array[1],值将为 1;array[2] 的值为 2,依此类推...
}
如果是这样的话,时间复杂度是 O(n) 对吗?
虽然再次强调,这只是我对多次对数组进行赋值的情况的假设。
英文:
I am referring to something like:
int[] array = {1, 2 , 3, 4, 5};
Where the assignment of a value to each array index is done "all in a single line of code".
I do not really know for sure what happens in the background with this,
but what I have imagined is that it's something like an iteration through each index in the array, and then assigning the inputted int to that index:
for (int i = 0; i<array.length; i++){
array[i] = <given input> //for array[1] the value will be 1, array[2] is 2 and so on...
}
If that is the case, it is in O(n) right?
Though again, it is just my assumption of how the multiple assignments to an array occurs.
答案1
得分: 3
非常相关,所以请查看:Java:声明大小为 n 的数组的大O时间是多少?
初始化数组的生成字节码涉及到 newarray
指令,其复杂度为 O(n),因为每个元素在进行任何其他操作之前都会被初始化为默认状态。详见:JVM 规范,第576页:
> [...] 新数组的每个元素都被初始化为数组类型的元素类型的默认初始值(§2.3,§2.4)。
此外,您在此处使用的是数组初始化器,因此让我们查看字节码:
public class Main {
public static void main(String[] args) {
int[] array = {1, 2 , 3, 4, 5};
}
}
... 编译为 ...
public class Main {
public Main();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: iconst_5
1: newarray int
3: dup
4: iconst_0
5: iconst_1
6: iastore
7: dup
8: iconst_1
9: iconst_2
10: iastore
11: dup
12: iconst_2
13: iconst_3
14: iastore
15: dup
16: iconst_3
17: iconst_4
18: iastore
19: dup
20: iconst_4
21: iconst_5
22: iastore
23: astore_1
24: return
}
请注意 newarray
和传递给它的 iconst_5
。这属于代码中的“new int[5]
部分”,其中 iconst_5
实际上是 5
(“整数常量 5”)。请忽略 dup
和 astore_1
,它们对于问题不太重要。
请注意 iconst_0
、iconst_1
和 iastore
块,它们对其他整数常量重复。iastore
是将值存储到数组中的指令,其中第一个参数是索引,第二个参数是值。在 iastore
之前的两行是参数。因此,您看到的是字节码读取数组初始化器中的每个元素并将其存储在数组中。
因此,您显示的这个一行代码在字节码级别上实际上非常类似(或等效)于这个:
public class Main {
public static void main(String[] args) {
int[] array = new int[5];
array[0] = 1;
array[1] = 2;
array[2] = 3;
array[3] = 4;
array[4] = 5;
}
}
正如您所见,您显示的一行代码在字节码级别上实际上是 2 * O(n)。
英文:
Very related, so check it out: Java: what's the big-O time of declaring an array of size n?
The resulting bytecode for initializing an array involves the newarray
instruction, which is O(n) as each element is initialized to the default state before anything else. See: JVM Spec., page 576:
> [...] Each of the elements of the new array is initialized to the defaultinitial value (§2.3, §2.4) for the element type of the array type.
What you are using here additionally is an array initializer, so let's check out the bytecode:
public class Main {
public static void main(String[] args) {
int[] array = {1, 2 , 3, 4, 5};
}
}
... is compiled to ...
public class Main {
public Main();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: iconst_5
1: newarray int
3: dup
4: iconst_0
5: iconst_1
6: iastore
7: dup
8: iconst_1
9: iconst_2
10: iastore
11: dup
12: iconst_2
13: iconst_3
14: iastore
15: dup
16: iconst_3
17: iconst_4
18: iastore
19: dup
20: iconst_4
21: iconst_5
22: iastore
23: astore_1
24: return
}
Notice the newarray
with iconst_5
passed to it. This belongs to the "new int[5]
part" of the code, where iconst_5
is just 5
("integer constant 5"). Ignore the dup
and astore_1
, they're not so important for the question.
Notice the iconst_0
, iconst_1
and iastore
block, which is repeated for other integer constants. iastore
is the instruction to store a value in an array, where the first parameter is the index and the second parameter is the value. Two lines before the iastore
are the arguments. So what you see is that the bytecode reads each of the elements in your array initializer and stores it in the array.
So what the one-liner does is actually very similar (or equivalent) to this:
public class Main {
public static void main(String[] args) {
int[] array = new int[5];
array[0] = 1;
array[1] = 2;
array[2] = 3;
array[3] = 4;
array[4] = 5;
}
}
As you can see, the one-liner you've shown is actually 2 * O(n) at bytecode-level.
答案2
得分: 1
The answer from @akuzminykh is nice and sufficient.
But what you are fishing for is compile time preparation of data.
static final String STR = "...非常长的字符串...";
This string is compiled as a UTF-8 string in the constant pool of the class. A Java String will normally hold its data as an array of UTF-16 (2-byte) chars, but the newest Java versions can hold a byte array together with an encoding of it. So assume this to be the case for our string constant.
Then still, the bytes need to be copied.
Hence for n bytes, it's still O(n). But it will be fast and (likely) on the native code side. A string of 1 character will be loaded faster than a string of 10,000 characters. But the real effect is probably not measurable, not suitable for optimization.
英文:
The answer from @akuzminykh is nice and sufficient.
But what you are fishing for is compile time preparation of data.
static final String STR = "....very long string ...";
This string is compiled as UTF-8 string in the constant pool of the class. A java String will normally hold its data as array of UTF-16 (2 byte) chars, but the newest java versions can hold a byte array together with an encoding of it. So assume this to be the case for our string constant.
Then still the bytes need to be copied.
Hence for n bytes still O(n). But it will be fast and (likely) on the native code side. A string of 1 character will be loaded faster than of 10 000 characters. But the real effect probably not measurable, not apt for optimisation.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论