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

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

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
  • Проголосовать: не нравится

»
6 лет назад, # |
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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks. Do you know any specific case where this is not true? (where stable_sort is faster)

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
        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...

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Really strange...

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
        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)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by brdy (previous revision, new revision, compare).

»
6 лет назад, # |
  Проголосовать: нравится 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.