7
\$\begingroup\$

I have a program that makes operations on strings and this is the principal function of one of those operations. This works perfectly, but it is not efficient:

private void printString(ArrayList<String> operations, ArrayList<String> set) {
    int numerOfStrings = 0;
    int numberOfletters = 0;
    String toPrint = operations.get(1);
    outOfLoop: for (int i = 0; i < set.size(); i++) {
        String[] toFind = set.get(i).split(" ");
        for (int k = 0; k < toFind.length; k++) {
        if (toPrint.equals(toFind[k])) {
            String[] splited = set.get(i).split(" ");
            for (int j = 0; j < splited.length; j++) {
            numberOfletters += splited[j].length();
            }
            numerOfStrings = splited.length;
            break outOfLoop;
        }
      }  
    }
    System.out.println(numerOfStrings + " " + numberOfletters);
}

Explanation:

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

  1. For the arrayList of operations, I get always 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 have as operation print foo, I have to do these steps:

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

      • Inside set, I can have this situation:

        position 1 : {car tree hotel}
        ...
        position n : {foo lemon coffee}
        
      • When I find the string foo, I have to print the number of strings inside that position and the number of letters of each string, so in this case, I will print:

        3(number of strings) 14(sum of number of letters)

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

\$\endgroup\$
2
  • \$\begingroup\$ what if you search for oo should he also give position n?(your code do but I suspect that may not be the case). Also your use case says number of letters of each string. Shouldn't be that 3 - 4 - 6? \$\endgroup\$
    – chillworld
    Jun 6, 2014 at 11:07
  • \$\begingroup\$ sum of number of letters. \$\endgroup\$
    – OiRc
    Jun 6, 2014 at 11:19

3 Answers 3

4
\$\begingroup\$

Let me first do a review without getting into the logic of the method. Before I start making changes I've commented some smelly places in your original code:

//Try to use the most generic type in your arguments. You don't really need an ArrayList<>
//a List<> will suffice.
private void printString(ArrayList<String> operations, ArrayList<String> set) {     
    int numerOfStrings = 0;
    int numberOfletters = 0;
    //why take a list parameter when you only use one value (the second element?!)
    String toPrint = operations.get(1); 
    outOfLoop: for (int i = 0; i < set.size(); i++) {
        String[] toFind = set.get(i).split(" ");
        for (int k = 0; k < toFind.length; k++) {
            if (toPrint.equals(toFind[k])) {
                // duplicated work: toFind == splitted
                String[] splited = set.get(i).split(" "); 
                for (int j = 0; j < splited.length; j++) {
                    numberOfletters += splited[j].length();
                }
                numerOfStrings = splited.length;
                //goto is considered evil
                //Besides, goto to label is not neccessary here.
                //A simple `break` would suffice
                break outOfLoop;  
            }
        }
    }
    //you should return the results and let the caller of the method
    //decide what to do with them
    System.out.println(numerOfStrings + " " + numberOfletters);
}

So, in the first refactoring iteration I've ended up with:

public static class Result {
    public final int numerOfStrings;
    public final int numberOfletters;

    public Result(int numerOfStrings, int numberOfletters) {
        this.numerOfStrings = numerOfStrings;
        this.numberOfletters = numberOfletters;
    }

    @Override
    public String toString() {
        return numerOfStrings + " " + numberOfletters;
    }
}

private Result process(String word, List<String> set) {
    int numerOfStrings = 0;
    int numberOfletters = 0;

    for (int i = 0; i < set.size(); i++) {
        String[] toFind = set.get(i).split(" ");
        for (int k = 0; k < toFind.length; k++) {
            if (word.equals(toFind[k])) {
                String[] splited = set.get(i).split(" ");
                for (int j = 0; j < splited.length; j++) {
                    numberOfletters += splited[j].length();
                }
                numerOfStrings = splited.length;
                break;
            }
        }
    }
    return new Result(numerOfStrings, numberOfletters);
}


@Test
public void run() throws Exception {
    Result result = process("foo", Arrays.asList("car tree hotel","foo lemon coffe"));
    System.out.println(result);
}

This keeps the method logic intact, but fixes all the issues I mentioned in the comments.

But actually I think the method could be a lot simpler:

private Result process(String word, Iterable<String> set) {
    for (String string : set) {
        if(string.contains(word)) {
            //" +" is a regex patten for "one or more spaces"  
            int numberOfWords = string.trim().split(" +").length;
            int numberOfLetters = string.replace(" ", "").length();
            return new Result(numberOfWords,  numberOfLetters );
        }
    }
    return new Result(0, 0);
}

This version is more readable, but could be optimized for performance. As always with performance you should first check if optimizing here would make any impact on the application as a whole. Sacrificing readability might not be worth it.

Optimizations might include:

  1. avoid new string creation using trim()
  2. avoid new string array creation using split()
  3. avoid new string creation using replace()
  4. avoid iterating over string multiple times - count letters and words while looking for word (instead of contains)
\$\endgroup\$
7
  • \$\begingroup\$ @the second your solution you said This version is more readable, but could be optimized for performance, i think is not possible to avoid iterate,or not? \$\endgroup\$
    – OiRc
    Jun 6, 2014 at 11:16
  • \$\begingroup\$ EDIT: Answer added at the end \$\endgroup\$
    – rzymek
    Jun 6, 2014 at 11:24
  • \$\begingroup\$ oh i have understand this,but this sentence confused me,but could be optimized for performance. \$\endgroup\$
    – OiRc
    Jun 6, 2014 at 11:26
  • \$\begingroup\$ "goto is considered evil" - nice, inaccurate, unexplained, irrelevant, and generally misleading comment to add. No 'goto' in java, named breaks are fine and not evil, and changing it to a simple 'break' instead of a named break may not even have any efficiency impact whatsoever! \$\endgroup\$ Jun 6, 2014 at 12:07
  • 2
    \$\begingroup\$ string.contains(word) does not perform equally. ("this is some test".contains("so") is true, while "so" it not one of the string split on " "). I would add boundaries and use a regex. (string.matches(".*\\b" + word + "\\b.*") for example, though that would not work if the word contains some special characters. a combination of startsWith, endWith and contains with padding spaces would work but be more verbose) \$\endgroup\$
    – njzk2
    Jun 6, 2014 at 14:33
3
\$\begingroup\$

This will be a code-style focused review, as the other answers didn't address that yet:

Indentation:

your indentation style is either unconventional or got f*cked up by the SE markdown, either way:

  1. Indentation standard step is 4 spaces. (you are using 2)
  2. Block contained items are indented one step. Block delimiters are not indented.

Applying this to your code it becomes something like this:

private void printString(ArrayList<String> operations, ArrayList<String> set) {
    int numberOfStrings = 0;
    int numberOfLetters = 0;
    String toPrint = operations.get(1);
    outOfLoop: for (int i = 0; i < set.size(); i++) {
        String[] toFind = set.get(i).split(" ");
        for (int k = 0; k < toFind.length; k++) {
            if (toPrint.equals(toFind[k])) {
                String[] splited =set.get(i).split(" ");
                for (int j = 0; j < splited.length; j++) {
                     numberOfLetters += splited[j].length();
                }
                numberOfStrings = splited.length;
                break outOfLoop;
            }
        }
    }
    System.out.println(numberOfStrings + " " + numberOfLetters);
}

Code-Smells

sniff-sniff

  1. this looks a lot like arrow-code, that needs to be flattened.
    Solution: Introduce methods to do stuff for you. countLetters(String s) would be a start.

  2. splited and numberOfletters are a little off (orthographically and casing). "correct would be" splitted and numberOfLetters.

  3. System.out.println(); is almost never a good sign. Your method does two things here. It analyzes the two strings and then prints the result. Methods should always do just one thing. This is called Single Responsibility Principle. I would expect a method printString to take a String and print it to some output.

  4. String toPrint = operations.get(1); This one is a candidate for an ArrayIndexOutOfRangeException. Keep in mind, that operations does not necessarily contain more than one Item! As you only use a single string either way, you should just give toPrint in the parameters directly.

\$\endgroup\$
2
\$\begingroup\$

I came up with a similar solution to @rzymek's.

Variables named numberOf… would be better named …Count.

I've renamed other variables to have more meaningful names, such as requiredWord, sentence, and sentences. If you are indeed dealing with words and sentences, you'll want to handle delimiters such as punctuation. In that case, a BreakIterator.getWordInstance() would come in handy.

For clarity, I've split part of the function into a helper that examines just one sentence.

The search for the required word happens while processing each word, such that there is only one pass needed.

public static class WordAndCharCount {
    public final int wordCount, charCount;
    public static final WordAndCharCount NOT_FOUND = new WordAndCharCount(0, 0);

    public WordAndCharCount(int wordCount, int charCount) {
        this.wordCount = wordCount;
        this.charCount = charCount;
    }

    @Override
    public String toString() {
        return this.wordCount + " " + this.charCount;
    }
}

private static WordAndCharCount examine(String requiredWord, Iterable<String> sentences) {
    for (String sentence : sentences) {
        WordAndCharCount r = examine(requiredWord, sentence);
        if (r != null) {
            return r;
        }
    }
    return WordAndCharCount.NOT_FOUND;
}

private static WordAndCharCount examine(String requiredWord, String sentence) {
    String[] words = sentence.split(" ");
    boolean foundWord = false;
    int charCount = 0;
    for (String word : words) {
        charCount += word.length();
        if (foundWord || word.equals(requiredWord)) {
            foundWord = true;
        }
    }
    return foundWord ? new WordAndCharCount(words.length, charCount) : null;
}
\$\endgroup\$
1
  • \$\begingroup\$ thanks a lot for the solution, i will try also your solution. \$\endgroup\$
    – OiRc
    Jun 6, 2014 at 11:28

Your Answer

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

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