RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 1330636
Accepted
Harry
Harry
Asked:2022-09-21 18:43:49 +0000 UTC2022-09-21 18:43:49 +0000 UTC 2022-09-21 18:43:49 +0000 UTC

什么时候稳定排序更好?

  • 772

受到这个问题的启发。

我的决定

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>

using namespace std;

int main(int argc, char * argv[])
{
    vector<int> v(36000000);
    int k = 0;
    for(int i = 1;    i <= 6000; ++i)
        for(int j = 6001; j <= 12000; ++j)
            v[k++] = i*j;
    sort(v.begin(),v.end());
    long long s = 0;
    for(int i = 0; i < 36000000; ++i) s += v[i];
    cout << s;
}

工作原理与 Python 中最好的差不多,但速度稍慢。在我的机器上,这一切都计为大约 2.04±0.01 秒。好吧,这不可能是 C ++ 不如 Python :) - 我开始尝试以各种方式加速这段代码。

无法优化,一切都依赖于sort. 带着悲伤,我把它换成了stable_sort——看看会发生什么,然后——你瞧!— 时间下降到 1.30±0.03 秒。

似乎一直有人说,在一般情况下,由于更大的复杂性stable_sort(不仅是算法,它等于O(N·log(N) 2)),它的效果更差sort。但是,事实证明,至少并非总是如此?我知道常数可能会有很大的不同:),但是它什么时候小于常数sort?

在 G++ 下进行了检查-差异略有不同,但通常相同:1和2。

没有人对此进行深入研究,无法发表评论,如果两种功能都适合您,什么时候应用更有效?

视觉 C++ 2019,Windows 10

c++
  • 1 1 个回答
  • 10 Views

1 个回答

  • Voted
  1. Best Answer
    Zergatul
    2022-09-21T23:22:21Z2022-09-21T23:22:21Z

    所有最好的排序算法都有复杂性O(N * log(N))。Python 变得更快,因为它使用了 TimSort,并且当数组由排序的部分组成时,它的运行速度非常快。在上面的双循环中得到的正是这个数组。

    std::sort通常在大型数组上使用 QuickSort。这种排序没有利用数组部分已经排序的事实,在第一次迭代时它会破坏数组的结构。

    std::stable_sort通常使用 MergeSort,它O(n)比 QuickSort 需要更多的内存。正是由于额外的内存,默认使用了不稳定的排序。

    也许在 MergeSort 的 C++ 实现中,有一个优化可以检查子数组是否已经排序。在这种情况下,InsertionSort 可能不适用于小型子数组(检查子数组是否已经排序需要时间O(n),而 InsertionSort 需要O(n^2)时间)。

    如果子数组大小小于某个长度,则所有 3 种排序(TimSort、QuickSort、MergeSort)在内部使用插入排序。

    用于比较的基准,sort由stable_sort@wololo 提供,并由我稍作修改:

    #include <iostream>
    #include <algorithm>
    #include <ctime>
    #include <cstdlib>
    #include <cstddef>
    #include <limits>
    #include <vector>
    
    using std::cin;
    using std::cout;
    using std::endl;
    
    int rand(int bits)
    {
        int result = 0;
        while (bits)
        {
            int add = bits >= 15 ? 15 : bits;
            result = (result << add) | (rand() & ((1 << add) - 1));
            bits -= add;
        }
        return result;
    }
    
    int main()
    {
        typedef std::vector<int> vect_type;
        const unsigned long vect_size = 50000000;
        static_assert(std::numeric_limits<vect_type::size_type>::max() >= vect_size);
    
        std::vector<int> vect(vect_size), vect_stable(vect_size);
    
        for (int bits = 1; bits <= 31; bits++)
        {
            cout << "bits: " << bits << endl;
    
            for (vect_type::size_type i = 0; i < vect_size; ++i)
            {
                volatile int rand_val = rand(bits);
                vect[i] = rand_val;
                vect_stable[i] = rand_val;
            }
    
            {
                std::clock_t begin = std::clock();
                std::sort(vect.begin(), vect.end());
                std::clock_t end = std::clock();
    
                cout << "sort: " << double(end - begin) / CLOCKS_PER_SEC << endl;
            }
            {
                std::clock_t begin = std::clock();
                std::stable_sort(vect_stable.begin(), vect_stable.end());
                std::clock_t end = std::clock();
    
                cout << "stable_sort: " << double(end - begin) / CLOCKS_PER_SEC << endl;
            }
    
            cout << (vect == vect_stable) << endl;
        }
    }
    

    该函数int rand(int bits)生成一个随机数的bits位长。出于某种原因,数字的长度会影响排序的速度。这是我得到的(Visual C++ 2019,Windows 10):

    ╔══════╦═══════╦═════════════╗
    ║ bits ║ sort  ║ stable_sort ║
    ╠══════╬═══════╬═════════════╣
    ║    1 ║ 0.228 ║ 1.14        ║
    ║    2 ║ 0.381 ║ 1.419       ║
    ║    3 ║ 0.503 ║ 1.489       ║
    ║    4 ║ 0.634 ║ 1.618       ║
    ║    5 ║ 0.807 ║ 1.765       ║
    ║    6 ║ 0.96  ║ 1.902       ║
    ║    7 ║ 1.15  ║ 2.043       ║
    ║    8 ║ 1.319 ║ 2.193       ║
    ║    9 ║ 1.483 ║ 2.317       ║
    ║   10 ║ 1.67  ║ 2.452       ║
    ║   11 ║ 1.847 ║ 2.59        ║
    ║   12 ║ 2.022 ║ 2.74        ║
    ║   13 ║ 2.211 ║ 2.88        ║
    ║   14 ║ 2.398 ║ 2.997       ║
    ║   15 ║ 2.573 ║ 3.152       ║
    ║   16 ║ 2.756 ║ 3.279       ║
    ║   17 ║ 2.942 ║ 3.412       ║
    ║   18 ║ 3.13  ║ 3.556       ║
    ║   19 ║ 3.339 ║ 3.681       ║
    ║   20 ║ 3.567 ║ 3.794       ║
    ║   21 ║ 3.765 ║ 3.9         ║
    ║   22 ║ 4.045 ║ 4.092       ║
    ║   23 ║ 4.262 ║ 4.066       ║
    ║   24 ║ 4.332 ║ 4.097       ║
    ║   25 ║ 4.373 ║ 4.105       ║
    ║   26 ║ 4.408 ║ 4.122       ║
    ║   27 ║ 4.416 ║ 4.119       ║
    ║   28 ║ 4.405 ║ 4.121       ║
    ║   29 ║ 4.407 ║ 4.109       ║
    ║   30 ║ 4.421 ║ 4.12        ║
    ║   31 ║ 4.411 ║ 4.122       ║
    ╚══════╩═══════╩═════════════╝
    

    在此处输入图像描述

    • 8

相关问题

  • 编译器和模板处理

  • 指针。找到最小数量

  • C++,关于枚举类对象初始化的问题

  • 函数中的二维数组

  • 无法使用默认构造函数创建类对象

  • C++ 和循环依赖

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    表格填充不起作用

    • 2 个回答
  • Marko Smith

    提示 50/50,有两个,其中一个是正确的

    • 1 个回答
  • Marko Smith

    在 PyQt5 中停止进程

    • 1 个回答
  • Marko Smith

    我的脚本不工作

    • 1 个回答
  • Marko Smith

    在文本文件中写入和读取列表

    • 2 个回答
  • Marko Smith

    如何像屏幕截图中那样并排排列这些块?

    • 1 个回答
  • Marko Smith

    确定文本文件中每一行的字符数

    • 2 个回答
  • Marko Smith

    将接口对象传递给 JAVA 构造函数

    • 1 个回答
  • Marko Smith

    正确更新数据库中的数据

    • 1 个回答
  • Marko Smith

    Python解析不是css

    • 1 个回答
  • Martin Hope
    Alexandr_TT 2020年新年大赛! 2020-12-20 18:20:21 +0000 UTC
  • Martin Hope
    Alexandr_TT 圣诞树动画 2020-12-23 00:38:08 +0000 UTC
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5