performance of int Array vs Integer Array

Question

Today when I submitted a solution to codeforces, I used int[] array and my submission got TLE(Time limit exceeded) & after changing it to Integer[] array surprisingly it got AC. I didn't get how the performance is improved.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static class Task {
        public void solve(InputReader in, PrintWriter out) throws Exception {
            int n = in.nextInt();
            Integer[] a = new Integer[n];
            for (int i = 0; i < n; i++) a[i] = in.nextInt();
            Arrays.sort(a);
            long count = 0;
            for (int i = 0; i < n; i++) count += Math.abs(i + 1 - a[i]);
            out.println(count);
        }
    }

    public static void main(String[] args) throws Exception{
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task task = new Task();
        task.solve(in, out);
        out.close();
    }


    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

@sotirios-delimanolis could you explain where the autoboxing happens? If the array is of type `int[]`, there should be no auto(un)boxing. — Turing85, Nov 01 '16 at 17:38
@NaveenKakani auto(un)boxing does not apply here, or at least not in a positive way. From what I see, auto(un)boxing should make your code slower, not fast. P.S.: [link to Oracle's tutorial on autoboxing](https://docs.oracle.com/javase/tutorial/java/data/autoboxing.html). — Turing85, Nov 01 '16 at 17:42
@NaveenKakani the only thing you changed was the type of the array `a` in `solve(...)` from `int[]` to `Integer[]` and your program got faster? — Turing85, Nov 01 '16 at 17:47
@Turing85 Yes. you can look at my codeforces submissions http://codeforces.com/submissions/naveenkakani problem 285C — Naveen Kakani, Nov 01 '16 at 17:49
@NaveenKakani yes, if Java auto(un)boxes variables, there is a runtime overhead. — Turing85, Nov 01 '16 at 17:53
Tnx @Touring85 got it. But, first i thought it as an IO problem lol :D now I'm very clear. — Naveen Kakani, Nov 01 '16 at 17:55
Did some testing with your code. The performance is not lost within `Arrays.sort(...)`, sorting an `int[]` this way is about 3x faster than sorting an `Integer[]`. — Turing85, Nov 01 '16 at 18:30
@naveen , I don't think your code performance has been improved due to auto-boxing because when I execute my code , I got t1=0 and t2=0; — Shree Prakash, Nov 01 '16 at 18:48
(Note that you don't even need to store inputs not exceeding one: just accumulate and count them.) — greybeard, Nov 01 '16 at 19:24

kraskevich · Accepted Answer · 2016-11-01T19:19:24.980

The reason for it is quite simple: the time complexity of the solution with Integer is better.

Sounds strange, doesn't it?

Arrays.sort uses a dual pivot quick sort for primitives, which works in O(N^2) time in the worst case. The test case your solution fails is a specially constructed anti-quick sort test.

However, the version for objects uses merge sort, which runs in O(N * log N) time for any possible input.

Note that it's not a part of the Java language specification (it doesn't say how the sort method should be implemented), but it works like this in most of the real implementations (for example, it is the case for openjdk-8)

P.S. Things like this happen more or less frequently in competitive programming, so I'll recommend to either sort arrays of objects or to use collections.

performance of int Array vs Integer Array

1 Answers1