Quick sort(快速排序)杂谈 3

在上一篇我们介绍了快排的各种优化，最后得到了一个超越VS的STL std::sort实现的版本，这回我们来讲讲怎么折磨gcc的std::sort。

GCC的实现

这个我直接给个github来源，链接里是gcc8分支的实现源码，我已经通过链接标记出第1896行，那里就是__unguarded_partition函数的实现，就是快排的划分函数，而在后面几个函数就是快排的本体了。为了避免它代码更新导致位置变化，我把相关代码复制过来。

  /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
  template<typename _Iterator, typename _Compare>
    void
    __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
                           _Iterator __c, _Compare __comp)
    {
      if (__comp(__a, __b))
        {
          if (__comp(__b, __c))
            std::iter_swap(__result, __b);
          else if (__comp(__a, __c))
            std::iter_swap(__result, __c);
          else
            std::iter_swap(__result, __a);
        }
      else if (__comp(__a, __c))
        std::iter_swap(__result, __a);
      else if (__comp(__b, __c))
        std::iter_swap(__result, __c);
      else
        std::iter_swap(__result, __b);
    }

  /// This is a helper function...
  template<typename _RandomAccessIterator, typename _Compare>
    _RandomAccessIterator
    __unguarded_partition(_RandomAccessIterator __first,
                          _RandomAccessIterator __last,
                          _RandomAccessIterator __pivot, _Compare __comp)
    {
      while (true)
        {
          while (__comp(__first, __pivot))
            ++__first;
          --__last;
          while (__comp(__pivot, __last))
            --__last;
          if (!(__first < __last))
            return __first;
          std::iter_swap(__first, __last);
          ++__first;
        }
    }

  /// This is a helper function...
  template<typename _RandomAccessIterator, typename _Compare>
    inline _RandomAccessIterator
    __unguarded_partition_pivot(_RandomAccessIterator __first,
                                _RandomAccessIterator __last, _Compare __comp)
    {
      _RandomAccessIterator __mid = __first + (__last - __first) / 2;
      std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
                                  __comp);
      return std::__unguarded_partition(__first + 1, __last, __first, __comp);
    }

  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    __partial_sort(_RandomAccessIterator __first,
                   _RandomAccessIterator __middle,
                   _RandomAccessIterator __last,
                   _Compare __comp)
    {
      std::__heap_select(__first, __middle, __last, __comp);
      std::__sort_heap(__first, __middle, __comp);
    }

  /// This is a helper function for the sort routine.
  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
    void
    __introsort_loop(_RandomAccessIterator __first,
                     _RandomAccessIterator __last,
                     _Size __depth_limit, _Compare __comp)
    {
      while (__last - __first > int(_S_threshold))
        {
          if (__depth_limit == 0)
            {
              std::__partial_sort(__first, __last, __last, __comp);
              return;
            }
          --__depth_limit;
          _RandomAccessIterator __cut =
            std::__unguarded_partition_pivot(__first, __last, __comp);
          std::__introsort_loop(__cut, __last, __depth_limit, __comp);
          __last = __cut;
        }
    }

  // sort

  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
           _Compare __comp)
    {
      if (__first != __last)
        {
          std::__introsort_loop(__first, __last,
                                std::__lg(__last - __first) * 2,
                                __comp);
          std::__final_insertion_sort(__first, __last, __comp);
        }
    }

吐槽一句，连gcc源代码也把tab和空格混合使用我也是醉了，源代码的tab在这里已替换为空格以保证版面一致

这里我们并不需要关注太多东西，在上一篇我们讲到过，快排最大的弱点正在于它的划分元素选择上，所以我们只需要看这个函数

  template<typename _RandomAccessIterator, typename _Compare>
    inline _RandomAccessIterator
    __unguarded_partition_pivot(_RandomAccessIterator __first,
                                _RandomAccessIterator __last, _Compare __comp)
    {
      _RandomAccessIterator __mid = __first + (__last - __first) / 2;
      std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
                                  __comp);
      return std::__unguarded_partition(__first + 1, __last, __first, __comp);
    }

这个函数从__first + 1, __mid, __last - 1三个数里面，取一个中位数交换到__first的位置，知道这个就能想办法生成对抗数据了。为了让它运行缓慢，那么只要让它这个函数每次都选到第二小的元素放最左边，这样每次调用__unguarded_partition的结果，就是把划分点划分到了__first + 2的位置上，即每次只划分两个元素，这就是它的最坏情况。

构造这个东西需要一些技巧，我们要模拟std::sort的过程，但为了复杂性降低，我们令最右边元素值最大，那么中位数必定在__first + 1与__mid中选出，这样在partition过程中就能保证不会动到最后的元素，只会在这两个之间换来换去。然后我们只模拟出交换的结果，而不必去遍历，否则你生成的复杂度就$O(n^2)$了。

另外，还要注意的一点是，它使用的是intro sort来实现，也就是说深度到一定程度后，会转化为堆排序，而堆排序的最坏情况是乱序数组，我们不必一直这么做，否则堆排序时间并不是最长的，我们只要弄深度150的就够用了。我们来看看生成的数据在8000000长度下，使用mingw64-gcc8编译参数-O3的实测结果

第4、5列是随机打乱的数据，作为对比组，而evil列就是生成的对抗数据，我把heap sort及前一篇的intro_sort实现放上来做比较，可以看出在这组数据下，std::sort必然地比堆排序还要慢，是乱序数据的3.5倍左右，当然这个时间完全取决于堆排序的时间。

附上生成代码

struct save_index
{
    int val;
    int index;

    save_index(int i = 0, int v = -1)
        : val(v)
        , index(i)
    {}
    void swap(save_pos& p)
    {
        int t = p.val;
        p.val = val;
        val = t;
    }
    bool operator < (const save_index& p) const
    {
        return index < p.index;
    }
};

void qsort_sim_gcc(save_index * beg, save_index * end, int max_round)
{
    int cur_num = 0;
    if ((end-1)->val == -1)
    {
        (end - 1)->val = (end - beg) * 2;
    }
    while (beg + 1 < end && --max_round > 0)
    {
        save_index *l = beg + 1, *r = end - 1, *m = beg + (end - beg) / 2;

        if (l->val == -1)
            l->val = ++cur_num;
        if (r->val == -1)
            r->val = ++cur_num;
        if (m->val == -1)
            m->val = ++cur_num;

        if (l->val > m->val)
        {
            if (m->val > r->val)
                std::swap(*beg, *m);
            else if (l->val > r->val)
                std::swap(*beg, *r);
            else
                std::swap(*beg, *l);
        }
        else
        {
            if (m->val < r->val)
                std::swap(*beg, *m);
            else if (l->val > r->val)
                std::swap(*beg, *l);
            else
                std::swap(*beg, *r);
        }
        if (l->val < beg->val && l->val != -1)
            ;
        else if (m->val < beg->val && m->val != -1)
            std::swap(*l, *m);
        beg += 2;
    }
}

void anti_qsort_gen_gcc(std::vector<save_index>& vec, size_t len, int max_round)
{
    for (size_t i = 0; i < len; ++i)
    {
        vec.push_back(save_index((int)i));
    }
    qsort_sim_gcc(&*vec.begin(), &*vec.begin() + len, max_round);
    int cnt = 0;
    for (size_t i = 0; i < len; ++i)
    {
        if (vec[i].val == -1)
            ++cnt;
    }
    std::vector<int> val_list(cnt);
    for (int i = 0; i < cnt; ++i)
    {
        val_list[i] = i + len - cnt;
    }
    // 以下 random_shuffle 实现需要自己实现，如果你用的是mingw
    // 不能使用std::random_shuffle，注意
    random_shuffle(val_list.begin(), val_list.end());
    for (int i = 0, j = 0; i < len; ++i)
    {
        if (vec[i].val == -1)
        {
            vec[i].val = val_list[j++];
        }
    }
    std::sort(vec.begin(), vec.end());
}

void anti_qsort_gen_gcc(sort_element_t arr[], size_t len)
{
    std::vector<save_index> vec;
    anti_qsort_gen_gcc(vec, len, 150);
    for (size_t i = 0; i < len; ++i)
    {
        arr[i] = vec[i].val;
    }
}

代码中注释的random_shuffle问题参见这篇文章

最后总结，老实加个rand比啥都强，至少大大增加构造evil数据的难度，也大大降低遇到最坏情况的可能。