Is the performance of Arrays.sort quadratic here?

Блог пользователя PrakharJain

Автор PrakharJain, история, 9 лет назад, По-английски

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

PrakharJain
9 лет назад
12

Комментарии (12)

Написать комментарий?

AlexandruValeanu

9 лет назад, скрыть # |

← Rev. 4 →

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[].

→ Ответить

fushar

9 лет назад, скрыть # |

← Rev. 2 →

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://mirror.codeforces.com/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.

→ Ответить

AlexandruValeanu

9 лет назад, скрыть # ^ |

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

→ Ответить

drajingo

9 лет назад, скрыть # ^ |

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.

→ Ответить

AlexandruValeanu

9 лет назад, скрыть # ^ |

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).

→ Ответить

dalex

9 лет назад, скрыть # ^ |

→ Ответить

OneClickAC

9 лет назад, скрыть # |

Declaring the array this way

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

→ Ответить

AlexandruValeanu

9 лет назад, скрыть # ^ |

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.

→ Ответить

OneClickAC

9 лет назад, скрыть # ^ |

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.

→ Ответить

AlexandruValeanu

9 лет назад, скрыть # ^ |

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.

→ Ответить

Dekacc

9 лет назад, скрыть # ^ |

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.

→ Ответить

AlexandruValeanu

9 лет назад, скрыть # ^ |

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!

→ Ответить