How I wrote the Java Olympics or why it is better not to use Scanner

The Regional stage of the All-Russian School Olympiad ended yesterday. I participated in it and chose Java for this. The main reason why I decided to write the Olympiad specifically for 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 has also greatly contributed to productive coding, in situations where time is a decisive factor. Yes, JetBrains development environment is available 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 deeply into the conditions of the problem, in the solution of which I was faced with the fact that the program does not have time to cope with the task in the allotted time, but I note one fact: the solution I wrote was a reference one (that is, the judges in the test package provided an identical solution, but on C), did not have infinite cycles and other things, and its complexity was O (n).

With the restrictions that n <= 20000, and one second is available for the program, the question arose as to who ate the time.
')
And according to the results, it can be said with accuracy that the culprit was Scanner and its nextInt() function.

And now let's take a closer look at how this function works.

The function itself consists of just one line return nextInt(defaultRadix); .
But what is happening inside this function is much more interesting to us.

The first step is to check if ((typeCache != null) && (typeCache instanceof Integer)
&& this.radix == radix) if ((typeCache != null) && (typeCache instanceof Integer)
&& this.radix == radix) if ((typeCache != null) && (typeCache instanceof Integer)
&& this.radix == radix) and here it is very important to understand what typeCache and where it comes from. And here everything is quite simple. It is nothing more than a string of our console written in the Object form and if this object (read as the string we entered) is an Integer instance, then the Scanner concludes that the string 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 by entering only one number into the line we practically do not spend time converting input to a number.
So we go on.

And here the hero of the occasion appears.

If the line that Scanner received is not int or if there are several such lines, then this line of code is called:

 String s = next(integerPattern()); 

And under it is hidden that:

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

I didn’t see the point of inserting the full code before, but now that we’ve got to the point, I think it's time to look into detail.

The first three lines are just foolproof.

And then, as the comments of those who wrote this code suggest, we are checking “didn’t we have already found such a pattern?”, But in our case this check will always return false, because we have already checked at the last stage that the string we received not int.

And what do we see at the end? Realizing that there are no more quick search methods, the Scanner gives up and starts an infinite loop that will end only if something is found through the search.

And what is our difficulty in such a bust? There seems to be used, of course, the method of two pointers or something similar to it, but in any case it does not save from many checks.

You can correct me, but I see O (n ^ 2) there, because otherwise I cannot explain where so much time could have gone.

Bottom line: in case you need the program to really quickly read the integers from the console, do not trust this business Scanner.nextInt() . Even the banal Scanner.nextLine and splitting a String into String [] and turning each of the members of a given array into int will be much faster.