Writing faster Java algorithms

C Speed?

I started competitive programming in C++ because it is the most common language on competitive programming sites out there. Of course, due to the famous STL library and the speed you get out of a C++ program. Switching to Java for writing algorithms has been a totally nice experience, and I found some ways to increase the speed of your Java algorithm in contests and projects generally.

Why write in Java?

• You use Java everyday for day-to-day tasks like Android or server-side development or probably Java was your first love. :))

• Most Data Structures you’ll need are easier to implement and readily available in the java.util.* package or java.io.* as opposed to C++ for example, where you have to import all the libraries you will need from STL or alternatively #include <bits/stdc++.h> header file which contains all the major classes you will need. The downside is that this header file is not present in C compilers like Microsoft Visual Studio C++ or Xcode’s Clang compiler.

• Most of the Java algorithms you will write will be bug free because the syntax is human friendly and the IDE will most times save you from yourself. There is also the wonderful debugging experience you get from popular IDEs like IntelliJ.

• Extensive documentation, age, libraries, resources and the ability to peek at the source code.

• WHY NOT?

Let’s get down to the speed tips:

1. Improve your IO operations

It is far easier to receive input from the terminal with Java’s Scanner class but it is relatively slower than using BufferedReader because :

• BufferedReader has larger buffer than Scanner: 8KB to 1KB

• Scanner uses regular expressions internally to read and parse Strings to their types in functions nextDouble() , nextInt() ,etc.. which we use when reading numbers from file for example, and well, regExp is slow.

Below is a demo showing the time taken by Scanner and BufferedReader respectively to read in integers from a file containing 2,000,000 numbers.

Scanner Implementation

Equivalent BufferedReader implementation

Let’s first define a static class named FastScanner , which contains a BufferedReader and a StringTokenizer

now you can add methods to return common types like int , double , char[] etc and don’t forget to always close the BufferedReader.

You can add methods to the FastScanner class to your requirement, in most contests, you’ll deal with integers, long, double, char[] ,strings.

# speed test

What about outputs?

I use the PrintWriter class in place of the traditional **System.out.println(), **it is roughly twice faster, nothing much… but speed is speed :)

** An important performance tip will be to group pieces of Strings together to form a single String (using StringBuilder()) before printing out from the output stream.

2. Use primitive types where necessary in place of Objects

Primitive values are stored in the stack, in the computer memory WHILE Objects are stored in the **heap. The most important thing to know about them in terms of speed is that, the stack **is a faster memory area than the **heap, **hence we have to consider this in our algorithms and use primitive types instead of object types when and where possible. The test here is actually going to be a short one:

This is like x40+ time difference in nanoTime just summing up numbers from 0 to 999. More complex tasks will cause greater variations in time

3. Use Arrays in place of ArrayLists where necessary

Arrays should be used in place of ArrayLists where necessary especially when the **size **of the array is known. Aside the speed of using Arrays over ArrayLists, it is actually more convenient to get a value in the array using arr[i][j] instead of arr.get(i).get(j) for Lists.

Even though the ArrayList was also initialised with the **size, **Array will of course be faster because of point 2 above. NOTE that you should use ArrayList when you don’t know the number of items that will be stored, because Lists are mutable.

4. Know when to use String “+” operator, StringBuilder and char[]

Manipulating Strings is a very important part of algorithms and data structure. This is the simple rule I follow when working with Strings:

• When printing or storing already known String values, concatenate them using “+”. For example, in

String myString = "I "+"am "+"a "+"Java Champion!";
// and in
System.out.println("I "+"am "+"a "+"Java Champion!");

The String “I am a Java Champion!” is actually stored as a single String value in the String pool, and it doesn’t make sense here creating a StringBuilder for something like this.

• Use StringBuilder when you are repeatedly adding, removing, or replacing Characters/Strings.

• AVOID using “+=” on Strings within loops.

• Use char[] when you’ll be mutating characters in the string a lot but the size of this string never changes. For example, getting all possible word permutations of Strings that can be formed from the word “javastrings”. There are 9979200 possible permutations and using a char[] would make it really easy to swap characters without having to rebuild a new string.

String str = "foobar";
//! `.toCharArray()` converts strings to character arrays
char[] characters = str.toCharArray();
//! characterArrays can be converted back to Strings
// using `String.valueOf()`;
String finalString = String.valueOf(characters);

Finally…

These optimisations will make your algos run faster. However, your algorithm has to be effective in the first place. Irrespective of programming language, time complexity and space complexity of an algorithm must be OPTIMAL.

My template for competitive programming in Java:

Happy coding !! ✌️🤖👨🏽‍💻

References:

• Difference between scanner and BufferedReader class in java

• https://www.geeksforgeeks.org/stringtokenizer-class-java-example-set-1-constructors/

• https://www.guru99.com/stack-vs-heap.html

• Original FastScanner template gotten from @agminadur