需要有关代码优化的建议

Question

我正在尝试生成两个输入字符串的子序列，但我的代码需要很长时间才能生成 output.Just 需要优化给定的建议 code.Below 是代码

  import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;



class Subsequences {

       public static void combinations(String suffix,String prefix,List seq){
        if(prefix.length()<0)return;
//        System.out.println(suffix);
        seq.add(suffix);
        for(int i=0;i<prefix.length();i++)
         combinations(suffix+prefix.charAt(i),prefix.substring(i+1,prefix.length()),seq);
    }

    public static void main(String args[] ) throws Exception {

        List seq1=new ArrayList();
        List seq2=new ArrayList();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int N = Integer.parseInt(line);
        for (int i = 0; i < N; i++) {
        combinations("",br.readLine(),seq1);
        combinations("",br.readLine(),seq2);
        seq1.retainAll(seq2);
        if(seq1.size()>1){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
        seq1.clear();
        seq2.clear();
        }


    }
}

这里我使用递归生成字符串的所有子字符串，并使用 retainAll 将所有这些存储到 arraylist.Then 我比较 then.I 之间的任何公共元素目前需要 1.9 秒到 run.Need 在 1 秒内完成。

Answer 1

我假设你的意思是运行没有编译程序花费的时间太长了。我还假设您需要 CPU 剖析代码才能真正了解问题所在。我建议您在进行任何更改之前执行此操作。例如从visual vm开始甚至使用飞行记录器。

很可能大部分时间花在了您未展示的方法 combinations 上。

然而，对于这类问题，一个问题是假设创建对象是免费的，而它可以花费 90-99% 的时间。我建议你也做一个内存配置文件并尝试减少你创建的对象数量。

只有在尽可能多地调整内存和cpu使用率之后，您才可以考虑使用多线程。

Answer 2

我不完全确定你的 combinations 方法做了什么，但它肯定没有找到子字符串。使用名为 prefix 的变量来保存后缀，使用名为 suffix 的变量来保存前缀是使代码难以破译的好方法。您还引用了一个单独的 combinations 方法，其中包含 5 个参数，但您的 class 中没有。

您的性能问题可能是由于使用 List 而您应该使用 Set。将 ArrayList 替换为 HashSet，看看是否能解决您的问题。

需要有关代码优化的建议

Need advice on code optimization

java

string

optimization

substring