3
\$\begingroup\$

Motivation: I was solving an array based i/o problem and encountered Time Limit Errors, it was later found that the code for java ran roughly 10x slower than the python implementation.

Question: I would like to know which part of my code failed in the latter implementation (in Java) given that the algorithmic complexity for both the codes is the same. And what should I use in order to avoid it.


The problem is from https://www.hackerearth.com/practice/codemonk/ and a direct link doesn't exist.

Given problem abstract: If an indexed array arr is given, print the contents of the array whose index is shifted by a constant.

Example:

let arr=1,2,3,4
then arr shift 3 towards right means
2,3,4,1

Input format:

  • first line: number of test cases
  • for each test case:
    • first line contains n,k where n represents number of elements and k represents the shifting
    • the second line contains the elements of the array

Here is my fast python code

from sys import stdin
t= int(input())
for i in range(t):
    n,k=list(map(int,input().split()))
    a=list(map(int,stdin.readline().split()))
    for i in range(n):
        print(a[(i-k)%n],end=" ")
    print("\n")

Here are the results:

result.

Now, I wrote another solution in Java

//imports for BufferedReader
import java.io.BufferedReader;
import java.io.InputStreamReader;

//import for Scanner and other utility classes
import java.util.*;

class TestClass {
    public static void main(String args[] ) throws Exception {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        Scanner s = new Scanner(System.in);
        int t = Integer.parseInt(input.readLine());
        while(t-->0){
            String[] nk = input.readLine().split(" ");
            int n = Integer.parseInt(nk[0]);
            int k = Integer.parseInt(nk[1]);
            String [] arr = input.readLine().split(" ");
            for(int i = 0; i < n ; i++){
                System.out.printf("%s ",arr[(i-k%arr.length+arr.length)%(arr.length)]);
            }
            System.out.printf("%n");
       }
    }
}

And here are the results:

results.

\$\endgroup\$
5
  • \$\begingroup\$ The standard comment/answer for performance questions: get yourself a decent profiler to find out what method call consumes the majority of time. I wouldn't be surprised to see some Scanner methods making the hot spots. \$\endgroup\$ Jun 14, 2021 at 21:32
  • \$\begingroup\$ How Scanner s is used at all here? \$\endgroup\$
    – vnp
    Jun 14, 2021 at 21:40
  • \$\begingroup\$ i-k%arr.length+arr.length is vulnerable to integer overflow. That may explain timeouts. \$\endgroup\$
    – vnp
    Jun 14, 2021 at 21:44
  • \$\begingroup\$ @vnp Oh, that is unnecessary here, although removing it didnt make a difference \$\endgroup\$ Jun 15, 2021 at 3:39
  • \$\begingroup\$ @vnp pretty sure it isn't an overflow ...The time required for the failed test case is 3 seconds (tested on tio.run)...I cannot share the link, it is too long. \$\endgroup\$ Jun 15, 2021 at 3:45

1 Answer 1

6
\$\begingroup\$

Python Code

  • PEP-8 recommends
    • a space around binary operators like =.
    • a space after commas (n, k = …)
    • using the throw away variable (_) for loops which do not need the loop index for anything (for _ in range(t):)
  • the list(…) is unnecessary in the assignment to n,k
  • the map(int, …) is unnecessary for the a array, as you are simply parroting the values back out.
  • there is no need to use stdin.readline(), you could simply use input() like the previous lines.
  • one-letter variables should not be used unless it is very clear what that variable name means. n and k are from the problem statement, so are ok. t, on the other hand, is very obfuscating.

Improved (readability & speed) code:

num_tests = int(input())
for _ in range(num_tests):
    n, k = map(int, input().split())
    arr = input().split()
    for i in range(n):
        print(arr[(i-k) % n], end=' ')
    print("\n")

Java Code

  • Scanner s is unused.
  • t is an obfuscating variable name
  • try-with-resources should be used to ensure the BufferedReader and InputStreamReader are properly closed.
  • n should be the array length, why use arr.length?

Performance issues:

  • Double module operation: (i-k%arr.length+arr.length)%(arr.length). -k%arr.length+arr.length is a constant. You could move that computation out of the loop. Or, if k is always in 0 <= k <= n, simply use (i-k+n)%n.
  • printf("%s ") may be slowing your program down by creating a brand new string combining the arr element and a space. Using System.out.print(arr[(i-k+n)%n]); System.out.print(' '); may be faster.

And the number 1 performance issue …

String[] String::split(String regex)

… you are using the Regular Expression engine to split the string into words!

\$\endgroup\$
5
  • \$\begingroup\$ I'll try these out, by the way, what method should I use instead of split? i was looking at the Reader class when I found that split is the updated method \$\endgroup\$ Jun 15, 2021 at 4:50
  • \$\begingroup\$ Now, after updating I fail only 1 test case...thanks! \$\endgroup\$ Jun 15, 2021 at 5:06
  • 1
    \$\begingroup\$ Also using printf("%n") to output A newline instead of println() is a bit wasteful. Before we had the split(Strign) method we had to use StringTokenizer for splitting strings. \$\endgroup\$ Jun 15, 2021 at 7:45
  • \$\begingroup\$ StringUtils.split(str, ' ') would be a great option, if you can use the Apache commons libraries. Failing that, you might have to roll your own ... or rethink the problem and come up with a different solution that doesn't require splitting the input into n tokens. \$\endgroup\$
    – AJNeufeld
    Jun 15, 2021 at 13:54
  • \$\begingroup\$ StringUtils is unfortunately not supported on the platform . . . given that it's because of the regex based input splitting, I think I should linear search and find partitions...then use substrings \$\endgroup\$ Jun 16, 2021 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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