对于前向迭代器(如list)使用sort是一个编译错误

2019-11-01 11:02 来源:未知

  小时候家里定了《读者》的月刊,里面记录一个故事:说有有个偏僻的乡村一日突然来了一个美女,她携着万贯家财子女在当地安家落户,成了当地的乡绅。她让她的子女世世代代的保守这个秘密,直到这个秘密不会再对家族带来灾难。她就是陈圆圆。当年吴三桂领清兵入关,冲冠一怒为红颜,改写了中国的历史,自己却能全身而退的那个人。

脑洞大开--一条项目中常用的linux命令引发的经典算法题,大开linux

  小时候家里定了《读者》的月刊,里面记录一个故事:说有有个偏僻的乡村一日突然来了一个美女,她携着万贯家财子女在当地安家落户,成了当地的乡绅。她让她的子女世世代代的保守这个秘密,直到这个秘密不会再对家族带来灾难。她就是陈圆圆。当年吴三桂领清兵入关,冲冠一怒为红颜,改写了中国的历史,自己却能全身而退的那个人。

  周五例行公事的查看一下离线数据推送项目的数据和log。将log用awk分段之后,我想知道实时数据前10个被重复发送的数据ID都被重复发送了几次,从而找到进一步优化的入手点,天知道我对这个项目已经进行了多少次优化了。于是linux命令就是

 cat transmission.log |grep 'IncrementAlbumService.java:146'|awk '{print $6}'|awk -F ',' '{print $1}'| sort |uniq -c| sort -nr |head

  得到的结果令我很自责

永利平台娱乐 1(数据安全,对于我们项目的ID规则部分不显示)

虽然这和他们的操作有关,我本来就是该检测到数据变更就发送出去,但是对于这么大的重发率。不管从更新服务的接口上,还是离线服务上,能够优化的点还是有的。姑娘我的思路一向与那些出场要用吹风机,人工喷壶制造画面感的男神大佬思路不同。除了这个结果,我还在想另外一个经典算法问题:说是有一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前十个词。

  这个算法问题使用上面的linux命令就是sort|uniq -c |sort -nr | head。时间复杂度为下面几项中最大的一个:

  1>先是做一次排序,

    直接插入排序:不断将元素插入到有序表中去,最坏时间复杂度是O(n2)

    shell排序:缩小增量的插入排序,不稳定,有赖于增量因子序列的选取,最坏时间复杂度是O(n2)

    简单选择排序:在要排序的数中选择最小或最大与第一个未排序位置交换,最坏时间复杂度是O(n2)

    二元选择排序:每趟简单选择排序确定两个元素,可减少一半的循环。

    堆排序:树形选择排序,大根堆,小根堆。最坏时间复杂度是O(N*logN)

    冒泡排序:每次相邻的两个数比较,交换,最坏时间复杂度是O(n2)

    快速排序:选择基准元素,每次将待排序元素分割,最坏时间复杂度是O(n2)

    归并排序:将两个有序表合成一个新的有序表,最坏时间复杂度是O(N*logN)

    桶排序:以空间换时间的算法,复杂度接近O(n)  

    基数排序:按照个十百千的位数进行分配收集,时间复杂度是O(dn)

   2>uniq 时间复杂度为O(n)

   3>sort时间服务度同1>

   4>已经排好序了时间复杂度就是O(1)

  采用的算法也和文件的大小有关系,如果文件太大,数据太多,就需要将文件拆分,分别排序后做多路归并。所以这里说了文字数量。

  不用linux命令,经典的解决方法是先用字典树统计词频,再用大根堆。先介绍一下字典树,也叫tire树。因为搜索引擎常用这个来做文本词频统计,分词算法也用这个作为基本数据结构,所以知道一些。它的优点是:最大限度的减少无谓的字符串比较,查询效率高于哈希表。核心思想是以空间换时间,利用公共前缀来降低查询时间的开销。所以一说统计啥啥,首先想到的就是字典树。如果在统计词频时维护一个前十位的最大词频数组之类的,在循环处理中比较,时间复杂度要翻10倍。所以还是先统计,再取top10时间效率上更为合适。

  其实我不咋懂算法,只是会用。我之前一个同事看了我写的一篇文章微信问我:“feed流是很有技术含量的工作吗?” 他这个问题让我想起《仙剑》里李逍遥在餐馆里非要装高富帅,说要点最名贵的菜:“青菜炒牛肉”,众人哄笑,灵儿问李逍遥:“逍遥哥哥,青菜炒牛肉是很名贵的菜吗?”。虽然同事是在真心的问我意见,因为他在京东,正在考虑要不要去陌陌,我却感觉自己像那个没见过世面的李逍遥。feed流这个业务逻辑怎么都能做,有没有技术含量取决于怎么去做。我写过一篇专利,介绍feed流的一种拼装方法,流程没走完,这之前我就先不公开计算方法了。但是努力去想的话,优化点还是很多的。前年我还比较喜欢玩朋友圈的时候,经常会发现自己删除的朋友圈又出现了,或者自己的或者别人的朋友圈突然最近的数据全没了,只有很老的数据,比如一年前两年前的数据,一天之后自动恢复。都是策略的问题。微信朋友圈的问题挺多的。鉴于我们有个人见人爱花见花开的产品mm是微信架构师家属,我就不过多吐槽了。

  虽说今天是周日,可以脑洞大开一下,也得有个主题。前面的例子有个经典的top K问题。因为搜索引擎会经常需要统计最热门的查询串,top K问题是基础。TopK问题用小根堆。维护一个K大小的小根堆,遍历要比较的元素,分别与跟元素做对比,如果小于根元素,说明肯定进不了前K,淘汰掉。如果大于根元素,就淘汰根元素。再调整树为最小堆,继续比较。

  最小堆的是一棵完全二叉树,每个非叶子节点的值都不大于其子节点的值。如果破坏了这个规律,就要从第一个非叶子节点开始向根节点这种自下往上的顺序进行调整。

  下周决定面一下hulu,还没面,应该是面不过。两年前原同事给推荐过亚马逊,结果没让我去面试,安慰自己一下就是估计那时候他们其实是不招人的。从来没去过这种外企面试,不知道是啥套路。如果现在开始准备的话,估计过了十一差不多能过。我想我自己去面试肯定很不占优势。不是完全会不好,会很不稳定。看过我文章朋友大概会觉得我文章写的很乱,很杂。生活中我也确实是这样。知识面很广,很异想天开,无所顾忌,这一方面为我的创造力奠定基础,另一方面不利于我临场发挥。大脑像是一个电脑。我的并行程序很多,内存不够大,数据又多。内存分页导致不断和磁盘swap。面试这种有时效的动作很容易导致超时返回。我有那么多技术发明专利,现在让我想,我一个都想不起来自己发明了啥。刚刚坐公交车,因为人很少,司机师傅问我哪里下车,意思是没有人下车的地方就不停了。我想了很久才想起来。我的大脑更多运行在异步非阻塞模式,其实面试这种事情同步阻塞反而会好一些。然而任何事情都有解决的办法,找不到方法就是能力不够了,没什么不服的。然而面试是要考察综合能力的,比如团队合作,谈吐能力等等。相信我们部门的人都不会对“晓静很聪明“这句话有异议。也相信部门或者工作上有合作的同事都不会觉得我是个很难沟通或者很难相处的人。但是在面试中我却很可能会忘了要怎么说话。但是如果因为这个问题我没通过一个面试的话,我没有怨言。因为面试官就是将来的同事和领导,如果不够合拍的话,将来去了自己的能力也不一定能发挥出来。如果面试不好还觉得自己能力是够的,那很有可能是自己格局不够高,没见过真正优秀的人是什么样子。然而我就是那种铁定要碰壁的事还要做的人。如果一件事我决定放弃了,原因肯定是不值得做。

  喜欢工作,我的目标是60岁时还能有一份有创造性的工作。所以怕国内互联网公司会让我40岁就退休。还有一件最重要的事:我想做自己的搜索引擎中间件,国内的互联网公司以用为主,怕是我很难有精力来做这件事情。当然,去不了hulu,搜索引擎也还是要做的。只是一个怎样分配时间的问题。

  我其实是喜欢去碰壁的,大概是自己还不想那么快长大吧。如果天天表现的很成熟优雅的样子,就需要隐藏一些自己不擅长的,或者有可能出错的事儿。结果每天日子也会很开心,但是可能一辈子也就这样了。历史上有很多著名的人物,原本都是纨绔子弟,后家道中落才逆袭成为伟人的。书里,人生的转折有遇到贵人,和遇到挫折两种。年轻时心态开放,遇到贵人打开思路就可以顿悟了。而随着经历的增多,人会更加有选择的接收周围的信息,这时候大概需要遇到很大的挫折才能重新思考人生。如果能看到更好的未来,我愿独孤一掷,破釜沉舟。大起大落总好过一年如一日,要活就活的精彩~~

小时候家里定了《读者》的月刊,里面记录一个故事:说有有个偏僻的乡...

 

  周五例行公事的查看一下离线数据推送项目的数据和log。将log用awk分段之后,我想知道实时数据前10个被重复发送的数据ID都被重复发送了几次,从而找到进一步优化的入手点,天知道我对这个项目已经进行了多少次优化了。于是linux命令就是

STL中有多种排序算法,各有各的适用范围,下面听我一一道来:

 cat transmission.log |grep 'IncrementAlbumService.java:146'|awk '{print $6}'|awk -F ',' '{print $1}'| sort |uniq -c| sort -nr |head

I、完全排序

  得到的结果令我很自责

  1. sort()

永利平台娱乐 2(数据安全,对于我们项目的ID规则部分不显示)

首先要隆重推出的当然是最最常用的sort了,sort有两种形式,第一种形式有两个迭代器参数,构成一个前开后闭的区间,按照元素的 less 关系排序;第二种形式多加一个指定排序准则的谓词。sort基本是最通用的排序函数,它使用快速排序算法,并且在递归过程中,当元素数目小于一个阈值(一般是16,我的试验是24)时,转成直接插入排序。伟大的数学家Knuth已经证明,在平均意义上,快速排序是最快的了;当然,最坏复杂性比较差。sort要求随机迭代器,因此对于很多编译器来说,对于前向迭代器(如list)使用sort是一个编译错误。

虽然这和他们的操作有关,我本来就是该检测到数据变更就发送出去,但是对于这么大的重发率。不管从更新服务的接口上,还是离线服务上,能够优化的点还是有的。姑娘我的思路一向与那些出场要用吹风机,人工喷壶制造画面感的男神大佬思路不同。除了这个结果,我还在想另外一个经典算法问题:说是有一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前十个词。

#include <vector> 
#include <algorithm> 
#include <functional> 
#include <cstdlib> 

using namespace std; 

void func1() 
{ 
    vector<int> ar; 
    //向数组里面插入一些随机数 
    generate_n(back_inserter(ar), 100, rand); 
    //按从小到大排序 
    sort(ar.begin(), ar.end()); 
} 

/*
list<int> l1;
fill_n(back_inserter(l1), 200, 1000);
*/

  这个算法问题使用上面的linux命令就是sort|uniq -c |sort -nr | head。时间复杂度为下面几项中最大的一个:

如何从大到小逆排序,这个其实有很多种方式实现。

  1>先是做一次排序,

 1 void func2() 
 2 { 
 3     vector<int> ar; 
 4     //向数组里面插入一些随机数 
 5     generate_n(back_inserter(ar), 100, rand); 
 6   
 7     //方法1:使用函数作为谓词 
 8     sort(ar.begin(), ar.end(), GreateThan); 
 9     //方法2:使用仿函数作为谓词 
10     //注意下面两种方法都需要有个括号,实际上是要产生一个临时对象 
11     sort(ar.begin(), ar.end(), CompareInt()); 
12     //方法3:使用预定义的Adapter, 定义在 <functional> 中 
13     sort(ar.begin(), ar.end(), greater<int>()); 
14     //方法4:正常排序,然后翻转过来 
15     sort(ar.begin(), ar.end()); 
16     reverse(ar.begin(), ar.end()); 
17     //方法5:使用逆迭代器 
18     sort(ar.rbegin(), ar.rend()); 
19 } 

    直接插入排序:不断将元素插入到有序表中去,最坏时间复杂度是O(n2)

永利平台娱乐,1.stable_sort

    shell排序:缩小增量的插入排序,不稳定,有赖于增量因子序列的选取,最坏时间复杂度是O(n2)

sort优点一大堆,一个缺点就是它不是一种稳定的排序。什么是排序的稳定性?就是如果出现两个元素相等时,要求排序之后他们之间保持原来的次序(比如我们先按学号排序,然后按成绩排序,这时就希望成绩相同的还是按照学号的次序排)。很可惜,快速排序算法就不是稳定的,要追求这个,只好用stable_sort了。

    简单选择排序:在要排序的数中选择最小或最大与第一个未排序位置交换,最坏时间复杂度是O(n2)

在各种排序算法中,合并排序是稳定的,但一般的合并排序需要额外的O(N)的存储空间,而这个条件不是一定能够满足的(可能是比较奢侈的)。所以在stable_sort内部,首先判断是否有足够的额外空间(如vector中的capcity()部分),有的话就使用普通合并函数,总的时间复杂性和快速排序一个数量级,都是O(N*logN)。如果没有额外空间,使用了一个merge_without_buffer的关键函数进行就地合并(如何实现是比较有技巧的,完全可以专门谈一谈),这个合并过程不需要额外的存储空间(递归的堆栈除外),但时间复杂度变成O(N*logN),这种情况下,总的stable_sort时间复杂度是O(N*logN*logN)。

    二元选择排序:每趟简单选择排序确定两个元素,可减少一半的循环。

总之,stable_sort稍微慢一点儿,但能够保证稳定,使用方法和sort一样。但很多时候可以不用这种方式和这个函数,比如上面的例子,完全可以在排序比较准则中写入成绩和学号两个条件就OK了。

    堆排序:树形选择排序,大根堆,小根堆。最坏时间复杂度是O(N*logN)

2.sort_heap

TAG标签:
版权声明:本文由永利平台娱乐发布于IT交流,转载请注明出处:对于前向迭代器(如list)使用sort是一个编译错误