Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Hey Folks! Being in the world of competitive programming, every one of us often face TLE (Time Limit Exceeded) Errors. Reducing TL of one's code is one of the most crucial phase of learning for programmers.
One of the most popular platform for competetive programming is codechef.
By-default : Codechef has the TL (Time Limit) for any problem as 1 sec. Java Language has a multiplier of 2 and phython has multiplier of 5.
Java being a heavy language, does uses extra space and time for loading the framework into code-cache along with the main program. But its not the memory issue, one generally faces but TLE.
So, one of the most common way of reducing TL of one's code is to use fast input and otput methods. This really helps. Java is also called a slow language because of its slow input and output. So, many a times, just by adding fast input output to their program and without making any changes in their logic, coders are able to get AC (ALL CORRECT).
Most problem setters explicitly reduce TL and multipliers of their problem so as to force users to learn and use fast input output methods.
Moreover, we often encounter problem statements saying: "Warning: Large I/O data, be careful with certain languages (though most should be OK if the algorithm is well designed)”. This is a direct hint given to users to use Faster I/O techniques.
The ways of I/O are:
- Scanner class
- BufferedReader class
- User-defined FastReader Class
- Reader Class
Java coders generally use Scanner Class in the following way:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int k = s.nextInt();
int count = 0;
while (n-- > 0) {
int x = s.nextInt();
if (x%k == 0)
count++;
}
System.out.println(count);
}
}
But even if its easy and requires less typing but it is not recommended as its very slow. In most of the cases we get TLE while using scanner class. So, instead of using Scanner class, why not try something new.
So, here are some of the classes which are used for fast input and output.
BufferedReader class
Although, this class is fast but its not recommended as it requires lot of typing. It reads the code from the character-input stream entered by user and buffering characters and hence provides an efficient way reading of characters, arrays, and lines. However, reading multiple words from single line increases its time complexity because of the use of Stringtokenizer and hence this is not recommended. However, it reduces the running time to approx 0.89 s.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int count = 0;
while (n-- > 0){
int x = Integer.parseInt(br.readLine());
if (x%k == 0) count++;
}
System.out.println(count);
}
}
Here,
BufferedReader is a class commonly used in Java language.
Work : It reads the text from a given Input stream (like code stored in a file) by buffering characters and hence reads characters, arrays or lines.
StringTokenizer is also a class.
Work : It allows an application to break a string in our code into tokens. This class is retained for compatibility reasons. Howener, its use is discouraged in new code and new users are not advised to use this class. This is mainly because this class's methods do not distinguish among identifiers, numbers, and quoted strings.
The Integer.parseInt() java method is a method.
Work : It is mainly used in parsing a String method argument into an Integer object. The Integer object is a wrapper class for the int primitive data type of java API.
User-defined FastReader Class
This method uses both BufferedReader and StringTokenizer and takes the advantage of user defined methods. As a result, its time efficient and also requires less typing. This gets accepted with a time of 1.23 s. So, due to less typing, it is easy to remember and is fast enough to meet the needs of most of the question in competitive coding.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main{
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next(){
while (st == null || !st.hasMoreElements()){
try {
st = new StringTokenizer(br.readLine());
}
catch (IOException e){
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt(){
return Integer.parseInt(next());
}
long nextLong(){
return Long.parseLong(next());
}
double nextDouble(){
return Double.parseDouble(next());
}
String nextLine(){
String str = "";
try{
str = br.readLine();
}
catch (IOException e){
e.printStackTrace();
}
return str;
}
}
public static void main(String[] args){
FastReader s=new FastReader();
int n = s.nextInt();
int k = s.nextInt();
int count = 0;
while (n-- > 0) {
int x = s.nextInt();
if (x%k == 0)
count++;
}
System.out.println(count);
}
}
Here,
FastReader is a userdefined Class which uses bufferedReader and StringTokenizer class. Both these classes are defined above and are very fast, hence reducing Time Limit of our code.
Reader Class
There is the fastest way but is not recommended since it is difficult to remember and is cumbersome in its approach. It effectively reduces the Time Limit of the code to just 0.28 s.
The reader class uses inputDataStream. It reads through the stream of data provided and also uses read() method and nextInt() methods for taking inputs.
Java.io.DataInputStream class lets an application read primitive Java data types from an underlying input stream in a machine-independent way.
The read() method is used to read a single character from our code. This method reads the stream of our code till:
- Some IOException has occurred
- It has reached the end of the stream while reading.
This method is declared as abstract method i.e. the subclasses of Reader abstract class should override this method if desired operation needs to be changed while reading a character.
NOTE :
- This method does not accepts any parameters
- It returns an integer value which is the integer value read from our code.
- Returned value can range from 0 to 65535.
- It returns -1 if no character has been read.
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main{
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException{
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException{
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg) c = read();
do{
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg) return -ret;
return ret;
}
public long nextLong() throws IOException {
long ret = 0;
byte c = read();
while (c <= ' ') c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException {
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg) c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}
if (neg) return -ret;
return ret;
}
private void fillBuffer() throws IOException{
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException {
if (din == null)
return;
din.close();
}
}
public static void main(String[] args) throws IOException{
Reader s=new Reader();
int n = s.nextInt();
int k = s.nextInt();
int count=0;
while (n-- > 0) {
int x = s.nextInt();
if (x%k == 0)
count++;
}
System.out.println(count);
}
}
Some of the common methods used are:
- close() : It is an abstract void method and closes the stream of data and releases any system resources associated with it.
- mark(int readAheadLimit) : It marks the present position in the stream.
- markSupported() : It returns the boolean value and checks whether stream supports the mark() operation.
- read() : It returns an integer value and reads a single character.
- read(char[] cbuf) : It returns an integer value and reads characters into an array.
Having implemented all these, even if our code continues to give TLE, we have to resort to our basic approach i.e by changing the logic of code and reduce it's Time Complexity to O(1), O(n) or O(log n).
The maximum time complexity that a code can have is decided by the costaints and the Time Limit mentioned in the problem statement. Generally, the Time Limit is 1 sec and the its the constraints that vary. If the constraint is 10^8, then maximum time complexity of code which can pass without getting TLE is O(N).
NOTE:
Time complexity of a function (or set of statements) is considered as:
- O(1) : if our code doesn’t contain any loop, recursion or call to any other non O(1) time function.
- O(n) : if our code contains only a single for - loop or while - loop.
- O(n^c) where c is the number of nested loops present in our code.
- O(log n) : if the loop variables are divided or multiplied by some constant amount.
With this article at OpenGenus, you must have a good idea of how to make your Java code execute faster. Enjoy.
