PrakharJain's blog

Is the performance of Arrays.sort quadratic here?
By PrakharJain, history, 7 years ago, In English

In the problem Div 2 C of the recent Codeforces round #415, I got TLE on test 69. I was unable to figure out the reason as the loop was running for just n times. So, I changed my array to arraylist, and used Collections.sort() instead of the Arrays.sort(). To my surprise, it passed without any other changes! What could be the reason here? Check my last 2 submissions for this : TLE Submission and Accepted submission

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 4   Vote: I like it +2 Vote: I do not like it

Collections.sort() uses Timsort while Arrays.sort() uses Quicksort.

// Collections.sort()
public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

// Arrays.sort()
public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

Note: Arrays.sort() uses Timsort on Object[].

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

I tried to hack one solution that uses Java 8's Arrays.sort() in my room on that problem, using dalex's generator code from http://codeforces.me/blog/entry/4827, but it still ran in time. The generator advertises that it works on Java 7 though. Is there any difference between Java 7's and Java 8's Arrays.sort()? Is dalex's code obsolete somehow?

Note: the said solution got TLE in systest.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    The code is 5 years old. There are other quicksort killers out there. Arrays.sort() is still using Quicksort for sorting arrays of primitives.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There are other quicksort killers out there.

      Could you suggest any that are targeted to Java 8? A google search failed to come up with any.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        After some research, I am not sure that it's possible to beat the current version of Quicksort. It still performs worse than Timsort but it will probably pass if the time limit is not that strict (i.e. for more than 200.000 elements, 2sec might not be enough).

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Declaring the array this way

Integer x[] = new Integer[n]; will solve the problem of time complexity .

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This is an awful solution (at least for competitive programming). You are not sorting primitives but objects; autoboxing/unboxing will probably kill you in a time-sensitive problem.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, didn`t understand what you are trying to say. Can you please elaborate it properly?

      As far as I know, I asked this doubt quite some time back and a few Java programmers told me to follow this policy.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Integer[] is not the same as int[]. One is an array of primitives and the other one is of objects. Java has a mechanism of converting from Integer to int and vice-versa (autoboxin/unboxing) and it is not cheap. Everything will be much faster on primitives and not their wrapper classes.

        This is a solution to avoid sorting using Quicksort on arrays of primitives. But it is a bad one.

        A good solution would be to write your one sorting function for arrays of primitives or to use Collections.sort on some list-like class (i.e.ArrayList) and to be prepared for a potential TLE.

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So you suggest using arraylist to solve this problem? I think that approach also has some downsides since the elements aren't together in memory, and it still has the same problem of wrapping and unwrapping Integer objects. As far as I know there are three workaround to the problem:

      -use Integer[] arr instead of int[] arr.

      -use ArrayList

      -use int[] arr, but do a random shuffle on the elements before sorting.

      Personaly, I don't think using Integer[] instead of int[] is such a big problem.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Please read what I said!.

        I said that the best approach would be writing your own function. If you are not willing to do that, you can easily use ArrayList or Integer[]' without knowing that it will pass the TL.

        If you really believe that using Integer[] instead of int[] is a solution to avoid strict time limits then I suggest you start doing that!

        → Reply