0
\$\begingroup\$

I've written this function that concats strings:

public void find(ArrayList<String> operations, ArrayList<String> set) {
  String toMerge = operations.get(1);
  String fromMerge = operations.get(2);
  outer: for (int i = 0; i < set.size(); i++) {
     String[] toSet = set.get(i).split(" ");
     for (int k = 0; k < toSet.length; k++) {
    if (toMerge.equals(toSet[k])) {
        for (int j = 0; j < set.size(); j++) {
        String[] fromSet = set.get(j).split(" ");
        for (int x = 0; x < fromSet.length; x++) {
            if (fromMerge.equals(fromSet[x])) {
            for (int c = 0; c < toSet.length; c++) {
                set.set(j, set.get(j)+ ' ' +  toMerge.concat(' ' +toSet[c]));
                set.set(i, " ");
                }
                break outer;
            }
          }
        }
      }
    }
  }
}

This function takes as parameter an arrayList of operations, and an arrayList of set:

  1. For the arrayList of operations, I always get a specific position, so I don't iterate. It is always \$O(1)\$.

  2. for the arrayList of set, I have to iterate, or rather, as I think of that to proceed:

    For example, if I have as operation move foo bar, I have to do these steps:

    • First of all, I have to find where foo is:

      • Inside set, I can have this situation:

        position x : {bar tree hotel}
        ...
        position y : {foo lemon coffee} 
        
      • When I find the string foo, I have to find the position of bar (I made an iteration as to find foo) and then i have to concat the foo string into bar string in this way:

        position x : {bar tree hotel foo lemon coffee}
        ...
        position y : {} 
        

My program works as well as my function, but it is a nasty and inefficient solution. How can I improve the efficiency of this function?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Looks like you've been changing your code back and forth, and the two versions are significantly different. If you're actively improving your code, perhaps wait until you're sure about the change. -- Couldn't you knock down some time by getting an index of the substring with .indexOf(String), then doing the concat with the index with .substring(index, yourString.length())? \$\endgroup\$ Commented Jun 6, 2014 at 16:30
  • \$\begingroup\$ @BobbyDigital now it is complete. \$\endgroup\$
    – OiRc
    Commented Jun 6, 2014 at 16:31

1 Answer 1

3
\$\begingroup\$

Here is what it looks like you're trying to do:

  1. loop through set, loop through each individual word in set, until you find toMerge.
  2. When you find that, you then restart the loop through set, and each word in set until you find fromMerge.

This is producing a redundancy in the case that your initial loop iterates over fromMerge, but continues the loop because it is only looking for toMerge. The approach I would take to improve it would be to search for both in the same loop, thereby eliminating the redundant second loop.

public void find(ArrayList<String> operations, ArrayList<String> set) {
    String toMerge = operations.get(1);
    String fromMerge = operations.get(2);
    int toMergeIndex = -1, fromMergeIndex = -1; //add search indexes
    for (int i = 0; i < set.size(); i++) {
        if (set.get(i).indexOf(toMerge) > -1)
            toMergeIndex = i;
        if (set.get(i).indexOf(fromMerge) > -1)
            fromMergeIndex = i;
        if (toMergeIndex != -1 && fromMergeIndex != -1)
            break;
    if (toMergeIndex == -1 || fromMergeIndex == -1){
        throw new Exception();//Failed, didn't find. Deal with as you wish   
    }
    else{
        set.get(fromMergeIndex) += " " + set.get(toMergeIndex);
        set.get(toMergeIndex) = " ";
    }

This is the only efficiency improvement that I can think of. Hope it helps!

\$\endgroup\$
1
  • \$\begingroup\$ good solution,really appreciate it. \$\endgroup\$
    – OiRc
    Commented Jun 6, 2014 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.