为什么在使用 ArrayList<String[]> 而不是 int[][] 时会出现超出时间限制 (TLE) 错误？

Question

所以我试图为最短距离对实现 Floyd-Warshal 算法。我的算法的第一个实现导致超过时间限制，而使用二维数组的第二个版本是成功的。谁能指出为什么 TLE 会出现在第一个实现中？
注：1000000 = 无穷大

输入：输入的第一行包含一个整数 T，表示测试用例的数量。然后是 T 个测试用例。每个测试用例的第一行包含一个整数 V，表示邻接矩阵的大小。接下来的 V 行包含矩阵（图形）的 V space 个分隔值。所有输入均为整数类型。

输出：对于每个测试用例，输出将是 V*V space 个分隔的整数，其中第 i-j 个整数表示第 i 个顶点与第 j 个顶点的最短距离。对于 INT_MAX 整数输出 INF.

示例输入：

2
2
0 25
10000000 0
3
0 1 43
1 0 6
10000000 10000000 0

示例输出：

0 25 
INF 0 
0 1 7 
1 0 6 
INF INF 0

代码方法 1（给出 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);
    }
}

第二种方法（成功通过所有测试用例）：

/*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);
    }
}

Answer 1

简而言之，第一个解决方案的每次迭代都比第二个解决方案的每次迭代慢得多。在每次迭代中，您执行以下操作：

Integer.parseInt，速度很慢。你可以查看这个答案：，看到每次解析大约需要 60 ns，这可能比循环中所有其他操作慢 10 倍以上。它应该是有道理的：至少 parseInt 花费的时间与字符串的长度呈线性关系。此外，该函数并不简单（至少，parseInt 必须检查数字是否为整数）。
Integer.toString，这同样需要时间与字符串的长度成线性关系。而且，它涉及到对象（字符串）的创建，你的时间可能会因为内存处理而增加（例如GC在你的设置中可能效果不佳，并且不要忘记内存分配）。

在更高的层面上，您违反了“有效 Java”中的第 50 条 (http://wavelino.coffeecup.com/pdf/EffectiveJava.pdf)：在其他类型更合适时避免使用字符串。您对数据进行数值计算；因此，您应该将它们存储为数字。

为什么在使用 ArrayList<String[]> 而不是 int[][] 时会出现超出时间限制 (TLE) 错误？

Why am I getting Time Limit Exceeded (TLE) error when using ArrayList<String[]> instead of int[][]?

java

performance

arraylist

multidimensional-array

floyd-warshall