专栏首页编程一生一条项目中常用的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

  得到的结果令我很自责

(数据安全,对于我们项目的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,搜索引擎也还是要做的。只是一个怎样分配时间的问题。

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 面试官说:你真的不是不优秀只是不合适

        静儿四年前面试一家公司,当时没有意识到自己的工作年限已经很长了。面试官的工作年限似乎比我短。他问了我很多java的三方类库的用法。我当时那段时间主要在...

    静儿
  • 懂了!国际算法体系对称算法DES原理

    加密领域主要有国际算法和国密算法两种体系。国密算法是国家密码局认定的国产密码算法。国际算法是由美国安全局发布的算法。由于国密算法安全性高等一系列原因。国内的银行...

    静儿
  • 2017人生总结(MECE分析法)

    静儿
  • 7.6.1 内部排序算法的比较

    1、简单选择排序、直接插入排序和冒泡排序的平均情况下的时间复杂度都为O(n^2),并且实现过程比较简单,但直接插入排序和冒泡排序在最好的情况下时间复杂度可以达到...

    week
  • 算法之旅 | 冒泡排序法

    HTML5学堂-码匠:本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单,容易上手,稳定性也比较高, 算是一种较好理解的算法,也是面试官高频提问的算法之一...

    HTML5学堂
  • Linux 工作常用命令笔记(持续更新)

    sort命令是在Linux里非常有用,它将文件进行排序,并将排序结果标准输出。sort命令既可以从特定的文件,也可以从stdin中获取输入。 语法:

    莫斯
  • 深入解析快速排序算法的原理及其Go语言版实现

    快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分。具体来说,它对给定数组中的元素...

    李海彬
  • 排序-真的了解快速排序了吗,请解答下题

    我们分析上面的示例,其实比较的就是下一个区间起始值是否在上一个区间的范围内,依次比较,直到匹配失败,就把这个已经匹配过的最小值和最大值放入一个新的区间。

    阿伟
  • 科普一下程序运行时内存分配

    代码段(code segment/text segment )通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定,并且内存区域通...

    大话swift
  • 从世界上第一块集成电路开始

      20世纪50年代,晶体管已得到了一定的发展。技术的发展,人们已经可以用硅做出了分立的电阻、电容、二极管、和三极管。但工程师们很快又遇到了新的麻烦。为了...

    网络交换FPGA

扫码关注云+社区

领取腾讯云代金券