### brdy's blog

By brdy, history, 9 months ago, ,

Hello,

I was doing this problem and was getting TLE on the last two test cases.

On a whim, I decided to replace my sort() functions with stable_sort(), and the solution passed.

According to this benchmark, stable_sort uses less iterations overall in g++ 5.3.0 and clang++ 3.7.0 than sort on average.

In the problem I sorted a vector<pair<int, pair<int,int>>>, which would take up to three comparisons each time. I considered this a possibility for the lower constant factor of stable_sort for this problem, but was not able to replicate the results.

You can try to submit my solution and it should AC. But if you replace "stable_sort" with "sort" it will TLE.

Does anyone know which types of cases stable_sort can outperform sort?

Edit: Programs are compiled with gcc/g++ 4.8.2 using the "-O2" optimization flag and "-lm" to access the math library, and also "-std=c++0x" to enable support for C++11.

•
• +9
•

 » 9 months ago, # | ← Rev. 2 →   +13 If you mean the column Iterations (next to Time(ns) and CPU(ns), then you are misinterpreting the benchmark completely. The column says, how often the benchmark was repeated. Not how many cycles / iterations the algorithm uses. In all tests std::sort was faster than std::stable_sort.
•  » » 9 months ago, # ^ |   0 Thanks. Do you know any specific case where this is not true? (where stable_sort is faster)
•  » » » 9 months ago, # ^ |   0 std::sort generally is an Introsort, that first does Quicksort, but might fall back to heapsort (to guarantee worst case O(nlogn) vs O(n^2) of Quicksort). When that fallback happens, it can probably be overall slower than Mergesort (std::stable_sort) from the beginning. Read this for more information on Introsort. Heapsort and Mergesort have a higher constant factor than Quicksort.
•  » » » 9 months ago, # ^ |   0 No. And I also suspect, that in your code std::sort is not slower than std::stable_sort. I haven't read the problem statement, but from what I can see in you solution is that the complexity is O(n*m). This will dominate every sort that you do. So maybe it was just a coincidence, e.g. time limit of 1 sec, and the first time you submitted it run in 1.01 sec, and the second time it run in 0.99 sec.
•  » » » » 9 months ago, # ^ | ← Rev. 3 →   +6 I checked it (twice), and indeed the stable_sort version runs in ~1.95s, so pretty close to TL. But for test 8, stable_sort took 1.15s vs sort 1.35s, seems significant. For test 9, stable_sort 1.6s and sort TLE...
•  » » » » » 9 months ago, # ^ |   0 Really strange...
•  » » » » » 9 months ago, # ^ |   0 Time limits are usually set with reserve. There is probably better solution. Sorting n*m can be avoided as there no more than n+m unique values. You can sort list of lengths and when you take length iterate over all the edges in that row/column.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 I've run it multiple times and the stable_sort solution always manages to squeeze right under the time limit.Also the complexity is nmlog(nm)
 » 9 months ago, # |   0 Auto comment: topic has been updated by brdy (previous revision, new revision, compare).
 » 9 months ago, # |   0 Generally, stable_sort implementations make much less comparisons as opposed to sort. It's also possible that stable_sort does less memory moves, but I'm not sure here.