前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >小王职场记STL(2)std:sort解析

小王职场记STL(2)std:sort解析

作者头像
早起的鸟儿有虫吃
发布于 2023-03-28 01:16:47
发布于 2023-03-28 01:16:47
66500
代码可运行
举报
文章被收录于专栏:算法之美算法之美
运行总次数:0
代码可运行

上篇文章回顾:

小王职场记 谈谈你的STL理解(1)


std:sort代码解析 开始

看一段代码会有什么问题。

当数据元素相同时候 stl sort会概率造成core dump(如果你测试,不一定会重现 ,猜一下需要什么条件?)

一、问题 std::sort()在排序的时候,会导致程序core掉。

二、解决办法 条款21 永远让比较函数对相等的值返回false

比较函数的理解

三、原因分析std:sort 分析 完整版请看: 文档注释:https://github.com/wangcy6/weekly/blob/master/stl.md

版本

gcc 使用 4.8.4 版本,

STL源码 在 Linux 系统的位置是:/usr/include/c++/4.8.4/bits (79个文件)

目录:

小王职场记 谈谈你的STL理解(1)

函数对象模块

  • 定义: 重载了“operaotr()”操作符的普通类对象 , 这个对象具备了具有函数行为 调用类(), 相当于调用类.成员函数()
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制

// 大于template <class _Tp>struct greater : public binary_function<_Tp,_Tp,bool>
{  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x > __y; }
};//这个函数对象没有数据成员、没有虚函数、没有显示声明的构造函数和析构函数,且对operator()的实现是内联的。用作STL比较器的函数对象一般都很小greater<int> greaterobj;
greaterobj(3, 5)//等价于greaterobj.operator(3,5) 效果等价于函数调用function(3, 5);

算法部分

代码:

stl_algo.h

std:compare:

Effective STL: Item 21:永远让比较函数对相同元素返回false

std:sort(5行代码)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
template <class _RandomAccessIter>inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
 __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
 __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
                _LessThanComparable);  if (__first != __last) { //只有一个记录 ,不需要排序
   __introsort_loop(__first, __last,
                    __VALUE_TYPE(__first),
                    __lg(__last - __first) * 2);//快速排序,整体有序
   __final_insertion_sort(__first, __last); //剩下未排序的数据,直接插入排序 }
}template <class _RandomAccessIter, class _Tp, class _Size>void __introsort_loop(_RandomAccessIter __first,
                     _RandomAccessIter __last, _Tp*,
                     _Size __depth_limit)
{  while (__last - __first > __stl_threshold) { ///长度大于16才进行一次快排分割
   if (__depth_limit == 0)
   {
     partial_sort(__first, __last, __last); //堆排序
     return;
   }
   --__depth_limit;
   _RandomAccessIter __cut =
     __unguarded_partition(__first, __last,
                           _Tp(__median(*__first,
                                        *(__first + (__last - __first)/2),
                                        *(__last - 1))));////找三个位置的中位数作为快排依据
   __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit); //排后一部分
   __last = __cut; //排前一部分
 }
}

std:sort描述

维基百科 内省排序

内省排序(英语:Introsort)是由David Musser在1997年设计的排序算法。 提出了Introspective Sorting(内省式排序)

  • 这个排序算法首先从快速排序开始,当递归深度超过一定深度(深度为排序元素数量的对数值)后转为堆排序。
  • 2000年6月,SGI的C++标准模板库的stl_algo.h中的不稳定排序算法采用了Musser的内省排序算法。在此实现中,切换到插入排序的数据量阈值为16个。

主要因素: if 递归深度 多大 then 改为堆排序 有不稳定排序改成稳定排序 if 数据少于16个 then 改为 插入排序,降低递归堆栈消耗

上面提到的三种算法各自的优点的综合:

  • 在数据量很大时采用正常的快速排序,此时效率为O(logN)。
  • 一旦分段后的数据量小于某个阈值,就改用插入排序,因为此时这个分段是基本有序的,这时效率可达O(N)。
  • 在递归过程中,如果递归层次过深,使用堆排序来处理 复杂度

参考

  1. http://feihu.me/blog/2014/sgi-std-sort/
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-01-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Offer多多 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
数据可视化(18)-Seaborn系列 | 线性回归图regplot()
案例代码已上传:Github https://github.com/Vambooo/SeabornCN
数据分析可视化
2019/10/02
5.5K0
数据可视化(18)-Seaborn系列 | 线性回归图regplot()
数据可视化(15)-Seaborn系列 | 双变量关系图jointplot()
在默认情况下双变量关系图是散点图与直方图组合的联合直方图,可以通过设置kind来改变联合直方图。
数据分析可视化
2019/10/02
5.7K0
数据可视化(15)-Seaborn系列 | 双变量关系图jointplot()
数据可视化(16)-Seaborn系列 | 变量关系组图pairplot()
案例代码已上传:Github https://github.com/Vambooo/SeabornCN
数据分析可视化
2019/10/02
2.7K0
数据可视化(16)-Seaborn系列 | 变量关系组图pairplot()
☀️苏州程序大白一文从基础手把手教你Python数据可视化大佬☀️《❤️记得收藏❤️》
下载类库Numpy, SciPy, matplotlib, pandas 和 seaborn。可以参考本文
苏州程序大白
2021/10/12
1K0
seaborn常用的10种数据分析图表
seaborn内置了十几个示例数据集,通过load_dataset函数可以调用。
派大星的数据屋
2022/04/03
6920
seaborn常用的10种数据分析图表
数据可视化(19)-Seaborn系列 | 热力图heatmap()
案例代码已上传:Github https://github.com/Vambooo/SeabornCN
数据分析可视化
2019/10/02
3.8K0
数据可视化(19)-Seaborn系列 | 热力图heatmap()
数据可视化(6)-Seaborn系列 | 直方图distplot()
该API可以绘制分别直方图和核密度估计图,也可以绘制直方图和核密度估计图的合成图 通过设置默认情况下,是绘制合成图,设置情况图下:
数据分析可视化
2019/09/24
15.2K0
数据可视化(6)-Seaborn系列 | 直方图distplot()
Python数据分析之Seaborn(变量分析绘图)
[Style functions]http://seaborn.pydata.org/tutorial/aesthetics.html#aesthetics-tutorial
AI异构
2020/07/29
1.1K0
Python数据分析之Seaborn(变量分析绘图)
数据可视化第二版-03部分-11章-相关
本系列博客为基于《数据可视化第二版》一书的教学资源博客。本文主要是第11章,相关可视化的案例相关。
用户2225445
2023/10/16
2190
数据可视化第二版-03部分-11章-相关
seaborn可视化入门
【小提琴图】其实是【箱线图】与【核密度图】的结合,【箱线图】展示了分位数的位置,【小提琴图】则展示了任意位置的密度,通过【小提琴图】可以知道哪些位置的密度较高。 小提琴图的内部是箱线图(有的图中位数会用白点表示,但归根结底都是箱线图的变化);外部包裹的就是核密度图,某区域图形面积越大,某个值附近分布的概率越大。 通过箱线图,可以查看有关数据的基本分布信息,例如中位数,平均值,四分位数,以及最大值和最小值,但不会显示数据在整个范围内的分布。如果数据的分布有多个峰值(也就是数据分布极其不均匀),那么箱线图就无法展现这一信息,这时候小提琴图的优势就展现出来了!
用户2225445
2022/11/12
9940
seaborn可视化入门
关于数据的可视化-直方图和二维频次直方图
一维直方图主要用hist来展示,二维的关系可以用散点图、多hist叠加、hist2d或seaborn来展现,seaborn的主要数据类型是pandas,因此需要转换,又复习了一下Numpy转pandas。
python与大数据分析
2022/03/11
1.3K0
关于数据的可视化-直方图和二维频次直方图
数据可视化(9)-Seaborn系列 | 分簇散点图swarmplot()
该函数类似于stripplot(),但该函数可以对点进行一些调整,使得数据点不重叠。
数据分析可视化
2019/10/02
4.2K0
数据可视化(9)-Seaborn系列 | 分簇散点图swarmplot()
数据可视化(17)-Seaborn系列 | 回归模型图lmplot()
案例代码已上传:Github https://github.com/Vambooo/SeabornCN
数据分析可视化
2019/10/02
1.6K0
数据可视化(17)-Seaborn系列 | 回归模型图lmplot()
数据可视化(10)-Seaborn系列 | 盒形图boxplot()
案例代码已上传:Github https://github.com/Vambooo/SeabornCN
数据分析可视化
2019/10/02
3K0
数据可视化(10)-Seaborn系列 | 盒形图boxplot()
Python可视化 | Seaborn教你一行代码生成数据可视化
处理一组数据时,通常要做的第一件事就是了解变量的分布。本文会介绍seaborn中用于可视化单变量的一些函数。
郭好奇同学
2021/11/24
1.4K0
Python可视化 | Seaborn教你一行代码生成数据可视化
Seaborn从零开始学习教程(三)
当处理一个数据集的时候,我们经常会想要先看看特征变量是如何分布的。这会让我们对数据特征有个很好的初始认识,同时也会影响后续数据分析以及特征工程的方法。本篇将会介绍如何使用 seaborn 的一些工具来检测单变量和双变量分布情况。
Python数据科学
2018/08/06
2K0
Seaborn从零开始学习教程(三)
008.python科学计算库seaborn(上)
版权声明:本文为博主原创文章,允许转载,请标明出处。 https://blog.csdn.net/qwdafedv/article/details/82852133
qubianzhong
2018/10/10
7150
Python数据处理从零开始----第四章(可视化)(14)使用seaborn绘制热图
seaborn.heatmapHeat maps显示数字表格数据,其中单元格根据包含的值着色。 热图非常适合使这种数据的趋势更加明显,特别是在订购数据并且存在聚类时。
用户1359560
2019/02/26
2.7K0
基于 Python 的数据可视化
来源:bea_tree 英文:kaggle 链接:blog.csdn.net/bea_tree/article/details/50757338 原文采用了kaggle上iris花的数据,数据来源从上面的网址上找噢 如果没有seaborn库 安装方法如下 http://www.ithao123.cn/content-10393533.html 正式开始了~~~ # 首先载入pandas import pandas as pd # 我们将载入seaborn,但是因为载入时会有警告出现,因此先载入w
小莹莹
2018/04/23
1.4K0
基于 Python 的数据可视化
各种各样的图
有时候,我们想画某一种图,就到处找代码,现学现卖。这里,笔者就做一个收集,使用python的matplotlib加上seaborn来美化的各种各样的图。
钱塘小甲子
2019/01/28
6570
推荐阅读
相关推荐
数据可视化(18)-Seaborn系列 | 线性回归图regplot()
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验