So I was trying to implement the Floyd-Warshal algorithm for shortest distance pairs. My first implementation of the algorithm lead to time limit exceeded while the second version using a 2d array was successful. Can anyone point out why is the TLE coming in the first implementation?
Note: 1000000 = infinity
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains an integer V denoting the size of the adjacency matrix. The next V lines contain V space separated values of the matrix (graph). All input will be integer type.
Output: For each test case output will be V*V space separated integers where the i-jth integer denote the shortest distance of ith vertex from jth vertex. For INT_MAX integers output INF.
Sample Input:
2
2
0 25
10000000 0
3
0 1 43
1 0 6
10000000 10000000 0
Sample Output:
0 25
INF 0
0 1 7
1 0 6
INF INF 0
Code approach 1 (giving TLE):
/*package whatever //do not write package name here */
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
public static int parseInt(String no){
if(no.equals("10000000") || no.equals("INF")){
return Integer.MAX_VALUE;
}
else
return Integer.parseInt(no);
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
StringBuffer sb = new StringBuffer();
int t = Integer.parseInt(sc.nextLine());
while(t-->0){
int n = Integer.parseInt(sc.nextLine());
ArrayList<String[]> adj = new ArrayList<>(n);
for(int i=0;i<n;++i){
String[] input = sc.nextLine().split(" ");
adj.add(input);
}
for(int k=0;k<n;++k){
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
int cur = parseInt(adj.get(i)[j]);
int iToK = parseInt(adj.get(i)[k]);
int kToJ = parseInt(adj.get(k)[j]);
int infinity = Integer.MAX_VALUE;
if(iToK!=infinity && kToJ!=infinity && cur>iToK+kToJ)
adj.get(i)[j] = Integer.toString(iToK+kToJ);
if(parseInt(adj.get(i)[j])==infinity)
adj.get(i)[j]="INF";
}
}
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
sb.append(adj.get(i)[j]+" ");
}
sb.append("\n");
}
}
sc.close();
System.out.println(sb);
}
}
Second Approach (passed all test cases successfully):
/*package whatever //do not write package name here */
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
StringBuffer sb = new StringBuffer();
int t = sc.nextInt();
while(t-->0){
int n = sc.nextInt();
int[][] adj = new int[n][n];
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
adj[i][j] = sc.nextInt();
for(int k=0;k<n;++k){
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
adj[i][j] = Math.min(adj[i][j],adj[i][k]+adj[k][j]);
}
}
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(adj[i][j]==10000000)
sb.append("INF"+" ");
else
sb.append(adj[i][j]+" ");
}
sb.append("\n");
}
}
sc.close();
System.out.println(sb);
}
}
In short, each iteration of the first solution is much slower than each iteration of the second one. At each iteration, you do the following:
Integer.parseInt, which is pretty slow. You can check this answer: https://stackoverflow.com/a/22783022/12463032, to see that each parse takes about 60 ns, which is probably more than 10 times slower than all other operations in the loop. It should make sense: at the very least parseInt takes time linear on the length of the string. Moreover, the function is not trivial (at the very least, parseInt must check that the number is an integer).Integer.toString, which again takes time linear of the length of the string. Moreover, it involves object (string) creation, and your time may increase because of memory processing (e.g. GC may not work that well in your settings, and don't forget about memory allocation).On a higher level, you violate Item 50 from "Effective Java" (http://wavelino.coffeecup.com/pdf/EffectiveJava.pdf): Avoid strings when other types are more appropriate. You perform numerical computations on your data; therefore, you should store them as numbers.