2
\$\begingroup\$

I created two programs (one with JAVA8) to calculate the total count of uppercase and lowercase characters in given String. After checking the execution time JAVA8 is taking longer execution time than expected. Is there any possible way to optimize any of these code more to reduce execution time and complexity?

Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Counts
{
    public static void main(String arg[])throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int upperCase=0, lowerCase=0;
        String str=br.readLine();
        Long startTimeMemo = System.nanoTime();
        for (int k = 0; k < str.length(); k++) {
     // Check for uppercase letters.
        if (Character.isUpperCase(str.charAt(k))) upperCase++;
     // Check for lowercase letters.
        if (Character.isLowerCase(str.charAt(k))) lowerCase++;
        }

     System.out.printf("%d uppercase letters and %d lowercase letters.",upperCase,lowerCase);
     Long stopTimeMemo = System.nanoTime();
     System.out.println("");
     System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));
    }
 } 

JAVA8 Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Count2
{
    public static void main(String arg[])throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        Long startTimeMemo = System.nanoTime();
        System.out.println(countUpperCase(str) + " " + countLowerCase(str));    
        Long stopTimeMemo = System.nanoTime();
        System.out.println("");
        System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));
    }
    private static long countUpperCase(String s) {
    return s.codePoints().filter(c-> c>='A' && c<='Z').count();
}

private static long countLowerCase(String s) {
    return s.codePoints().filter(c-> c>='a' && c<='z').count();
}
}
\$\endgroup\$
4
  • \$\begingroup\$ Apart from the explanation @flamesdev already posted, note that your stream based code does not do the same thing as your original code (Character.isUpperCase is a whole different beast than c >= 'A' && c <= 'Z' ) and your time measurement is far from accurate. See stackoverflow.com/questions/504103/… for some pointers to get to somewhat accurate measurements. \$\endgroup\$
    – mtj
    Jul 7, 2021 at 5:00
  • \$\begingroup\$ What if I rewrite stream based code like this : int[] counts = {0, 0, 0}; str.codePoints().map(c -> Character.isUpperCase(c) ? 0 : Character.isLowerCase(c) ? 1 : 2).forEach(i -> counts[i]++); System.out.printf("%d uppercase letters and %d lowercase letters.%n", counts[0], counts[1]); will this work fine? \$\endgroup\$ Jul 7, 2021 at 8:29
  • \$\begingroup\$ Just as every for-each loop creates an iterator, a codePoints stream does likewise. So two codePoints() cost. The conversion to code point from one or two chars is also overhead. The good thing is, this loss almost never counts. Note that Character.isUpperCase has also a version for int code points. \$\endgroup\$
    – Joop Eggen
    Jul 7, 2021 at 10:19
  • \$\begingroup\$ If you rewrite the code as in your comment, nobody will be able to read it any more. Aim for maintainable and clean code, not for clever tricks or performance. \$\endgroup\$
    – mtj
    Jul 7, 2021 at 14:21

2 Answers 2

2
\$\begingroup\$

Readability first

Indent the code properly. Put every statement in its own line. Name identifiers properly (well, this is mostly done).

Separate the algorithm from input/output operations

I/O operations are slow. Sometimes it's ok to mix them, but if you want to benchmark your algorithm - move all I/O out of it. The best way would be to create separate functions for counting.

Make sure what you're benchmarking

The first code uses:

  • single loop (1)
  • breaking into chars (2)
  • conditional statement (3)
  • library functions like Character.isLowerCase (4)
  • output with System.out.printf (5)

The second:

  • different methods for uppercase/lowercase (1a)
  • iterators (1b)
  • breaking into code points (2)
  • filter (3)
  • lambdas (4a)
  • comparing with chars (4b)
  • adding strings (5a)
  • output with System.out.println (5b)

Also, you didn't provide us with your test data and test results. My guess is the slowest part is 5a, but that's only a guess. Check it.

Rewrite the code to have different methods with the same signature (without I/O operations!), then test them several times on comparable data. And keep watching on what are you comparing.

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

Your Java 8 example is less efficient because it iterates over the string's code points twice (once for the countUpperCase method and a second time for countLowerCase). In your first example, you can optimize the code by adding an else clause to the two if statements. Because, if a character is uppercase, you know that if cannot be lowercase, so there's no point in checking. Additionally, instead of calling the charAt method twice, you can call it once and then assign the result to a local variable for reuse.

Rewritten Loop

for (int k = 0; k < str.length(); k++) {
  char character = str.charAt(k);
  if (Character.isUpperCase(character)) {
    upperCase++;
  } else if (Character.isLowerCase(character)) {
    lowerCase++;
  }
}
\$\endgroup\$
5
  • \$\begingroup\$ thank you sir. Please confirm that you want me to rewrite code like this : for (int k = 0, n = str.length(); k < n; k++) { char c = str.charAt(k); if (Character.isUpperCase(c)) upperCase++; else if (Character.isLowerCase(c)) lowerCase++; } \$\endgroup\$ Jul 7, 2021 at 8:25
  • \$\begingroup\$ @user12218554 You're welcome. The code you provided adds the else clause I suggested, but it doesn't use a for-each loop. Would you like me to edit my post to include a rewritten version of your code? \$\endgroup\$
    – Johann
    Jul 7, 2021 at 9:17
  • \$\begingroup\$ Sure sir. It will be really helpful. Thank you \$\endgroup\$ Jul 7, 2021 at 11:58
  • \$\begingroup\$ @user12218554 I've added a code snippet to my post; let me know if that helps. \$\endgroup\$
    – Johann
    Jul 7, 2021 at 13:20
  • \$\begingroup\$ @user12218554 Actually, it turns out that the suggestion I had about using a for-each loop was ill-conceived; I thought the chars method worked differently that it actually does. However, I have added a suggestion about using a local variable to prevent duplicate charAt calls, and I included the code for this change. \$\endgroup\$
    – Johann
    Jul 7, 2021 at 16:21

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.