How did I write the Olympiad in Java or why is it better not to use Scanner
Yesterday, the Regional stage of the All-Russian Olympiad for schoolchildren ended. I participated in it and chose the Java language for this. The main reason why I decided to write the Olympiad specifically in Java was that at that time I knew it quite well and understood how it implemented most of the basic data structures and functions. IntellijIDEA also greatly facilitated fruitful coding in situations where time is a decisive factor. Yes, there are JetBrains development environments for many other languages, but among these languages there are not those that are commonly used in sports programming, not counting Python, but I was afraid to use it here because this language is known for gluttony.
However, our friend, named after the Indonesian island, turned out to be even slower in some situations than a voracious snake.
I will not delve into the conditions of the problem, in the solution of which I was faced with the fact that the program does not manage to cope with the task in the time given, but I note one fact: the solution that I wrote was a reference (that is, the judges in the test package provided identical solution, but on C), did not have infinite loops and other things, and its complexity was O (n).
With restrictions that n <= 20,000, and one second is available for the program to work, the question arose of who ate the time.
And as a result, we can say with accuracy that
Now we’ll take a closer look at how this function works.
The function itself consists of only one line
But what is happening inside this function is much more interesting to us.
The first step is checking and here it is very important to understand what it is and where it comes from. And here everything is quite simple. It is nothing more than a line of our console written in the form, and if this object (read as the line we entered) is an instance , then Scanner concludes that the line entered is the desired number and returns it. Everything is good here and the complexity of this operation is O (1). From this we can conclude that introducing only one number on the line, we practically do not waste time converting the input into a number. So we go further.
And here the hero of the occasion appears.
If the line received by Scanner is not int, or if there are several of them, then this line of code is called:
And here’s what’s hidden under it:
Before that, I saw no reason to embed the full code, but now that we have reached the point, I think it's time to sort it out in detail.
The first three lines are just protection from the fool.
And then, as we are told by the comments of those who wrote this code, there is a check “but we didn’t find such a pattern?”, But in our case this check will always return false, because at the last stage we already checked that the line we received not int.
And what do we see at the end? Realizing that there are no more quick search methods, Scanner surrenders and launches an endless loop that will end only if something that suits us is found by exhaustive search.
And what is the complexity of this sorting? There, it seems, of course, the two-pointer method is used or something similar to it, but this in any case does not save from a lot of checks.
You can correct me, but I see O (n ^ 2) there, because otherwise I cannot explain where so much time could go.
Bottom line: in the case when you need the program to really quickly read integers from the console, do not trust this business
However, our friend, named after the Indonesian island, turned out to be even slower in some situations than a voracious snake.
I will not delve into the conditions of the problem, in the solution of which I was faced with the fact that the program does not manage to cope with the task in the time given, but I note one fact: the solution that I wrote was a reference (that is, the judges in the test package provided identical solution, but on C), did not have infinite loops and other things, and its complexity was O (n).
With restrictions that n <= 20,000, and one second is available for the program to work, the question arose of who ate the time.
And as a result, we can say with accuracy that
Scannerhis function was also the culprit nextInt(). Now we’ll take a closer look at how this function works.
The function itself consists of only one line
return nextInt(defaultRadix);. But what is happening inside this function is much more interesting to us.
The first step is checking and here it is very important to understand what it is and where it comes from. And here everything is quite simple. It is nothing more than a line of our console written in the form, and if this object (read as the line we entered) is an instance , then Scanner concludes that the line entered is the desired number and returns it. Everything is good here and the complexity of this operation is O (1). From this we can conclude that introducing only one number on the line, we practically do not waste time converting the input into a number. So we go further.
if ((typeCache != null) && (typeCache instanceof Integer)
&& this.radix == radix) typeCacheObjectIntegerAnd here the hero of the occasion appears.
If the line received by Scanner is not int, or if there are several of them, then this line of code is called:
String s = next(integerPattern());And here’s what’s hidden under it:
public String next(Pattern pattern) {
ensureOpen();
if (pattern == null)
throw new NullPointerException();
// Did we already find this pattern?
if (hasNextPattern == pattern)
return getCachedResult();
clearCaches();
// Search for the pattern
while (true) {
String token = getCompleteTokenInBuffer(pattern);
if (token != null) {
matchValid = true;
skipped = false;
return token;
}
if (needInput)
readInput();
else
throwFor();
}
}Before that, I saw no reason to embed the full code, but now that we have reached the point, I think it's time to sort it out in detail.
The first three lines are just protection from the fool.
And then, as we are told by the comments of those who wrote this code, there is a check “but we didn’t find such a pattern?”, But in our case this check will always return false, because at the last stage we already checked that the line we received not int.
And what do we see at the end? Realizing that there are no more quick search methods, Scanner surrenders and launches an endless loop that will end only if something that suits us is found by exhaustive search.
And what is the complexity of this sorting? There, it seems, of course, the two-pointer method is used or something similar to it, but this in any case does not save from a lot of checks.
You can correct me, but I see O (n ^ 2) there, because otherwise I cannot explain where so much time could go.
Bottom line: in the case when you need the program to really quickly read integers from the console, do not trust this business
Scanner.nextInt(). Even trivial Scanner.nextLineand splitting String into String [] and turning each of the members of this array into int will be much faster.