He commented that the reason why the execution time became TLE by using var for the counter variable of the for statement was not caused by var. I added it as a addictive point for beginners. (Added at 19:30 on 9/6/2020)
~~ I was solving the problem with AtCoder, and I was surprised that there was a considerable difference in execution time between var and type in the counter variable of the for statement, so I wrote this article. ~~
~~ MS allows var to be used for the counter variable of the for statement, and I also use it for business purposes. ~~ ~~var - C# Reference | Microsoft Docs~~
~~ However, it may not be good to use var for the counter variable of the for statement in the competition pro with limited execution time. ~~ ~~ (Because I am a beginner in competition, please point out if you make a mistake) ~~
It was when I was solving "AtCoder Begginner Contest 057 C-Digits in Multiplication". When I submitted it, it became TLE, but even if I look at other AC codes, there is no difference in the solution.
However, when I looked closely, there was a difference in the part where var was used in the for statement, so I changed the type of the counter variable in the for statement to long. Then, I passed by AC.
I compared it with the source code that I actually submitted. The source code just changed the type of the counter variable in the for statement. The language is "C # (.NET Core 3.1.201)".
| Execution time(ms) | Source code | |
|---|---|---|
| For var | 2206 | Submission#16188260 - AtCoder Beginner Contest 057 |
| For long | 97 | Submission#16518402 - AtCoder Beginner Contest 057 |
It is said that there is such a difference in execution time just by changing the variable type of the for statement to long.
Since var is type inference, if you want to make it long, you have to specify the type with a suffix.
As you can see by looking at the source code, For var
for (var i = 1; i * i <= N ; i++)
It was stated.
The MS documentation describes the type determination as follows:
The type of an integer literal is determined by its suffix as follows: A literal type without a suffix is the first of the int, uint, long, and ulong types that can represent its value.
Integer Numeric-C # Reference | Microsoft Docs
In the case of var, the initial value of i is as small as 1, so the type is determined as int.
The restrictions on N are as follows, so
1 ≦ N ≦ 10^{10}
The maximum value of int, 2,147,483,647, has been exceeded and it has overflowed.
If you increment with overflow, it will be negative.
If you try to execute the following source code, i will be -2147483648.
Incrementing to a positive maximum will result in a negative maximum.
int i = int.MaxValue;
i++;
Due to the overflow, an infinite loop occurred in for and it became TLE.
Therefore, when the for statement of the source code was corrected to the following, it became AC safely.
for (var i = 1L; i * i <= N ; i++)
| Execution time(ms) | Source code | |
|---|---|---|
| var +For suffix L | 93 | Submission#16539970 - AtCoder Beginner Contest 057 |
| For var | 2206 | Submission#16188260 - AtCoder Beginner Contest 057 |
| For long | 97 | Submission#16518402 - AtCoder Beginner Contest 057 |
Moreover, var + suffix L is slightly faster.
However, as a mechanism, the type of var is determined at compile time, so if the type can be specified properly, it will be the same IL (intermediate language of .NET) as when the type is specified. Therefore, it can be said that the performance does not change. Details: c # --Will using'var' affect performance? --Stack Overflow (Added on 9/12/2020)
In the competition pro, be aware of the type when using var for the counter variable of the for statement. If you have a time limit such as a competition pro, you may forget the suffix or cast if you are in a hurry, so I thought it would be okay to write the type properly. ~~ In competition pro, it seems better to write the type properly without using var for the counter variable of the for statement. ~~
Recommended Posts