CODEWITHSUNDEEP
javastringoptimizationsubstring
Nilesh
Nilesh

Reputation: 49

Need advice on code optimization

I am trying to generate the subsequences of two input string but my code is taking long to produce output.Just need advice for optimizing the given code.Below is the code

  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();
        }


    }
}

Herein I am generating all the substrings of a string using recursion and storing all of these into arraylist.Then using retainAll I compare any common element between then.I currently takes 1.9 sec to run.Need to do it under 1 sec.

Upvotes: 0

Views: 64

Answers (2)

Misha
Misha

Reputation: 28163

I am not entirely sure what your combinations method does, but it definitely isn't finding substrings. Using a variable named prefix to hold a suffix and a variable suffix to hold a prefix is a great way to make your code hard to decipher. You also reference a separate combinations method with 5 parameters that isn't present in your class.

Your performance problem could be due to using a List where you should be using a Set. Replace ArrayList with HashSet and see if that fixes your problem.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533720

I assume you mean it is taking too long to run not compile the program. I also assume you need to CPU profile the code to really know what the problem is. I suggest you do this before making any changes. Eg start with visual vm or even use flight recorder.

Most likely most of the time is spent in the method combinations which you haven't shown.

However for this sort of problem, one issue is the assumption that creating objects is free when it can be 90-99% of the time spent. I suggest you also do a memory profile and try to reduce the number of objects you create.

Only after tuning memory and cpu usage as much as possible, you might consider using multiple threads.

Upvotes: 1

Related Questions