Reducing For loops - Code Optimization

Question

I am new to Java and looking for code optimization techniques. This code is giving the expected output using two for loops and I want to reduce/eliminate the loops (if possible).

public static void main(String[] args) {
        String dummy = "Hello how are you";
        String[] strArr = dummy.split(" ");
        for(int i=0; i < strArr.length;i++){
            String word = strArr[i];
            for(int j=word.length(); j > 0; j--){
                System.out.print(word.charAt(j - 1));
            }
            System.out.print(" ");
        }
    }

Output: olleH woh era uoy

Please advice.

This belongs on [CodeReview](https://codereview.stackexchange.com) — Vince, Aug 20 '17 at 15:59
I am not asking for CodeReview, rather the optimization techniques. — user182944, Aug 20 '17 at 15:59
It is impossible to reduce the number of loops. You can change the type of loop to a while or a do-while loop but you need at least 2 looping constructs if you want your code to work — Coder, Aug 20 '17 at 16:02
What are you exactly trying to achieve here? You can theoretically eliminate a loop just refactoring out in a method, e.g. `printReversedWord(String)`. Complexity-wise you are already at O(n) and you won't get better because you need to read the string. Or maybe you are looking for patterns that substitute for loops? Say streams. — Gil Vegliach, Aug 20 '17 at 16:02
Its a for loop inside another for loop, hence the complexity is O(n2) — user182944, Aug 20 '17 at 16:04
@user182944: in general two nested loops would give you square complexity. In this case, if you look closer, you will see that the number of times you print a char is exactly the length of the string. More precisely your complexity is `O(n + sum_i word_i.length) = O(n + n) = O(n)` — Gil Vegliach, Aug 20 '17 at 16:09
The problem with this question is that ***you did not present a problem*** - you are prematurely optimizing. This doesn't cause a bottleneck, you don't specify any time requirements, etc.. You just wanna "optimize" it, which doesn't make much sense without context. What do you feel is wrong with your code? — Vince, Aug 20 '17 at 16:10
@user182944: Added an example where you "unnest" the for loops. — Gil Vegliach, Aug 20 '17 at 16:39
This micro-optimization attempt cannot bring any benefit. Output to the console dominates the running time and can't be reduced. Also, tricking the code to eliminate the inner loop will certainly worsen performance. — , Aug 21 '17 at 06:53

score 5 · Accepted Answer · answered Aug 20 '17 at 16:04

Since the complexity of printing the output would remain the same, all you can do is to "hide" the loops into existing methods that do what you want, not eliminate them, because the amount of work the system needs to perform remains the same in terms of the number of characters that need to be processed.

You can hide the nested loop by using string reversal technique described in this Q&A. The outer loop can be pushed into String.join:

String[] data = {"quick", "brown", "fox"};
System.out.println(
    String.join(
        " "
    ,   Arrays.stream(data)
           .map(s -> new StringBuilder(s).reverse().toString())
           .toArray(String[]::new)
    )
);

Demo.

@GilVegliach `.collect(Collectors.joining(" "))` would be cooler. — maaartinus, Aug 20 '17 at 18:29

score 1 · Answer 2 · answered Aug 20 '17 at 16:38

As I stated in my comment the complexity is already O(n) and you cannot get better because you need to read the input string. Anyway, there is a way to "unnest" the two for loops: reverse the whole string, split on spaces, and reverse the resulting array.

Example:

"Hello how are you"
"uoy era woh olleH"
"uoy" "era" "woh" "olleH"
"olleH" "woh" "era" "uoy"

Code:

public static void main(String[] args) {
    String dummy = "Hello how are you";

    int n = dummy.length();
    StringBuilder sb = new StringBuilder(n);
    while (--n >= 0) sb.append(dummy.charAt(n));

    String[] tokens = sb.toString().split(" ");
    n = tokens.length;
    while (--n >= 0) System.out.print(tokens[n] + " ");
}

Instead, if you are after cools java 8 Stream tricks, read dasblinkenlight's answer.

score 1 · Answer 3 · answered Aug 20 '17 at 16:45

This is another simple solution using StringTokenizer.

It takes only O(n).

public static void main(String[] args) {

    System.out.println(reverseStringWordByWord("Hello How are you"));

}

public static String reverseStringWordByWord(String input) {
    StringBuilder result = new StringBuilder();
    StringTokenizer sToken = new StringTokenizer(input, " ");
    while (sToken.hasMoreTokens()) {
        StringBuilder thisToken = new StringBuilder(sToken.nextToken());
        result.append(thisToken.reverse() + " ");
    }
    return result.toString();
}

Reducing For loops - Code Optimization

3 Answers3