mitan's blog

java.util.Arrays.sort() significantly faster for Object array than for primitive array. (Integer vs int)
By mitan, 10 years ago, In English

Hi,

I implemented a solution to 439B where the most time consuming step was using Arrays.sort. On test case 29 it times out at 1000 ms if I sort using an int[]. However, I pass, and use at most 280 ms on test case 29 if I sort using an Integer[]. Can someone explain why java.util.Arrays.sort(), on Codeforces, is more than 3x faster when using Integer[] rather than int[] in this case? The size of the array is 100,000 and the integers inside the array are from 1 to 100,000.

Thanks

My code is here:

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();    // number of subjects
    long x = sc.nextLong();    // initial per-chapter learning power of a subject
    
    Integer[] cps = new Integer[n];  // number of chapters per subject
    for (int i = 0; i < n; ++i) {
      cps[i] = sc.nextInt();
    }

    Arrays.sort(cps);  // Times out when cps is an int[].  Must be Integer[].
    
    long totalTime = 0;
    for (int i = 0; i < n; ++i) {
      totalTime += cps[i] * x;
      if (x != 1) {
        --x;
      }
    }
    
    System.out.println(totalTime);
  }
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

That is because there is anti quick-sort test case and Java uses quick-sort for primitives

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Java uses merge-sort for Object arrays and quick-sort for primitive arrays.
For merge-sort time complexity is O(n*logn) for all cases but an anti quick-sort input's time complexity may be O(n*n) and will result in TLE.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

This is 17months already and I learnt this the hard way.

In the second problem of the Educational Round that just passed, Many Java solutions did not pass. It turns out there was an anti quick sort test case number 20.

My solution passed the moment i used Object Integer. :)

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

ANTI-QUICK SORT TEST CASE

#include <iostream>
#include <cstdlib>
using namespace std;
int a1[300000];
int a2[300000];
int main(int argc, char** argv) {
	int maxn = atoi(argv[1]);
	int n = 50;
	for (int i = 0; i < n; i++) a1[i] = 1;
	int mx = 2;
	int* a = a1;
	int* b = a2;
	while (n + 4 + 40 <= maxn) {
		bool last = (n + 8 + 40 > maxn);
		int len = n + 4 + (last ? 40 : 0);
		int sev = (len >> 3) + (len >> 6) + 1;
		int e[5];
		e[2] = (len &mdash; 1) >> 1;
		e[1] = e[2] &mdash; sev;
		e[0] = e[1] &mdash; sev;
		e[3] = e[2] + sev;
		e[4] = e[3] + sev;
		if (last) {
			for (int i = 0; i < 40; i++) b[i] = mx;
		}
		for (int i = last ? 40 : 0, j = 0, ee = 1; i < len; i++) {
			if (i == e[ee]) {
				b[i] = mx;
				ee++;
			} else {
				b[i] = a[j++];
			}
		}
		int* t = a; a = b; b = t;
		n = len; mx++;
	}
	cout << n << " " << n << endl;
	for (int i = 0; i < n &mdash; 1; i++) cout << a[i] << " "; cout << a[n &mdash; 1] << endl;
	for (int i = 0; i < n &mdash; 1; i++) cout << a[i] << " "; cout << a[n &mdash; 1] << endl;
}
→ Reply