数据结构与算法之美学些12_2

1. 笔记

归并排序使用的就是分治思想。分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。

分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想,递归是一种编程技巧。

递归代码的编写技巧:分析得出递推公式,然后找到终止条件,最后将递推公式翻译成递归代码。

归并排序是一个稳定的排序算法。

第二,归并排序的时间复杂度是多少?
归并排序的执行效率与要排序的原始数组的有序程度无关,所以其时间复杂度是非常稳定的,不管是最好情况、最坏情况,还是平均情况,时间复杂度都是O(nlogn)。

第三,归并排序的空间复杂度是多少?
空间复杂度是O(n)。

快速排序的原理
快速排序并不是一个稳定的排序算法。

内容小结
归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分治的思想,代码都通过递归来实现,过程非常相似。理解归并排序的重点是理解递推公式和merge()合并函数。同理,理解快排的重点也是理解递推公式,还有partition()分区函数。

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法,这也使它存在致命的缺点,即归并排序不是原地排序算法,空间复杂度比较高,是O(n)。正因为此,它也没有快排应用广泛。

快速排序算法虽然最坏情况下的时间复杂度是O(n2),但是平均情况下时间复杂度都是O(nlogn)。不仅如此,快速排序算法时间复杂度退化到O(n2)的概率非常小,我们可以通过合理地选择pivot来避免这种情况。

2. 疑惑

展示分区操作的那个图不是很理解

3. 思考题

现在你有10个接口访问日志文件,每个日志文件大小约300MB,每个文件里的日志都是按照时间戳从小到大排序的。你希望将这10个较小的日志文件,合并为1个日志文件,合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有1GB,你有什么好的解决思路,能“快速”地将这10个日志文件合并吗?

我感觉评论中的高手说的很对。我就简单的记录一下。

先构建十条io流,分别指向十个文件,每条io流读取对应文件的第一条数据,然后比较时间戳,选择出时间戳最小的那条数据,将其写入一个新的文件,然后指向该时间戳的io流读取下一行数据,然后继续刚才的操作,比较选出最小的时间戳数据,写入新文件,io流读取下一行数据,以此类推,完成文件的合并, 这种处理方式,日志文件有n个数据就要比较n次,每次比较选出一条数据来写入,时间复杂度是O(n),空间复杂度是O(1),几乎不占用内存,这是我想出的认为最好的操作了。

4. 实际场景

消息系统的全局有序性的实现。

2019-04-23 一读

HQ Trivia 的员工发动政变要换掉 ceo,结果失败了
阅读原文
这是一则旧闻。两年前火了一把的有奖直播答题 app HQ Trivia 最近不火了;公司俩创始人,一个去年嗑药而死,一个是现在的 ceo;ceo刚刚平息了一场内部叛乱,局面控制下来了。

30 岁的 Game Boy 获得重生
阅读原文
Game Boy 于 1989 年 4 月份推出,最近刚过完 30 岁生日。有不少人改装/改进 Game Boy,比如加个摄像头,打印机,接上电吉他等。
写一个 Game Boy 或80/90年代的游戏机的模拟器,对于掌握计算机基础知识是很有帮助的。本科的时候有个同学在我们大二那年写了个任天堂红白机的模拟器。

睡眠质量比任何编程语言任何软件开发方法论都要重要
阅读原文
开发高质量的软件?先保证睡眠质量。这比什么编程语言,tdd,敏捷开发,什么最佳实践等都要重要。流水线工人都知道疲劳操作是很容易出事故的;那写软件呢?
如果软件只是用来分享你家的猫的照片,或者用来骗投资人的钱,那无所谓;如果软件是用来搞无人驾驶,医疗,建筑,航天等重要的事情,一定要严肃对待。

The Psychology of Startup Growth
阅读原文
很多人幻想“上线第一天,用户百万”,或者某个鸡贼伎俩可以瞬间增加几百万用户,这是不科学的。growth 是个过程,通常是漫长的过程,每个growth小伎俩只能增加一点,但尝试几千几万个以后,雪球就滚起来了。
Facebook 用了一年才达到一百万个用户。

Carta 101
阅读原文
2015年分享过这篇文章,那时候这家公司还叫做 eShare,后来改名 Carta;最近又重读了一遍,强烈推荐。公司不是家庭,而是职业运动队;每个员工必须早上8点半同时上班。
文中推荐的视频也强烈推荐一把:https://www.youtube.com/watch?v=ReSlJ5cq5D0 这是 Twilio 创始人 ceo 的演讲。要用软件的思维来解决问题;尽管很多人自称在“科技圈”工作,但思维还停留在19世纪体力劳动为主的时代。

Python 引用其他目录的文件

将你的文件加入Python路径方法有很多种,以下我认为比较好的一种方式。
创建一个.pth文件,将目录列举出来,像这样:

1
2
# myapplication.pth
/Users/xiaowang/PycharmProjects/hohode/src/util

这个.pth文件需要放在某个Python的site-packages目录,通常位于/usr/local/lib/python3.3/site-packages 或者 ~/.local/lib/python3.3/sitepackages。比如我的文件路径为/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages/myapplication.pth目录。
当解释器启动时,.pth文件里列举出来的存在于文件系统的目录将被添加到sys.path。
查看sys.path

1
2
3
4
5
6
7
8
9
10
Peace:site-packages hohode$ python3
Python 3.7.0 (v3.7.0:1bf9cc5093, Jun 26 2018, 23:26:24)
[Clang 6.0 (clang-600.0.57)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.path
['', '/Library/Frameworks/Python.framework/Versions/3.7/lib/python37.zip', '/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7', '/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/lib-dynload', '/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages', '/Users/xiaowang/PycharmProjects/hohode/src/util']
>>> import wcommon
>>> wcommon.getLocalIp()
'222.21.126.112'

安装一个.pth文件可能需要管理员权限,如果它被添加到系统级的Python解释器。
from https://python3-cookbook.readthedocs.io/zh_CN/latest/c10/p09_add_directories_to_sys_path.html

2019-04-21 一读

Startup idea checklist
阅读原文
每个人都能凭空想出一堆的自认为很厉害的创业 idea。但哪个 idea 真的值得去做?可以把每个 idea 拿出来,回答文中的每个问题;回答完后,你还觉得你的 idea 很厉害吗?

在办公聊天软件里别说 “hello”
阅读原文
办公环境里,即时通讯其实并不即时,一般是异步的;发消息过来,可能过段时间才回。为了提高沟通效率,最好省去问候语,第一句话直接把问题、事情讲清楚,对方看到了就能直接回复。

Production ready code is much more than error handling
阅读原文
当代的软件大多数“线上服务”,必须24小时都能用的。production ready 不只是代码要写得好,要有一系列配套的流程、工具、实践来保证线上服务不挂掉、或者挂掉了后能尽快找出问题、尽快修复。

Great developers are raised, not hired
阅读原文
与其抱怨“很难招到明星级别的工程师”,不如在公司里创造好的环境,让自家的工程师成长为明星级别的工程师。
“如果培养成明星级别的工程师了,最后却被别的公司挖走了怎么办?” 所以你喜欢养着一群永远不成长、混饭吃、假装在工作的平庸工程师?

Windows 操作系统是用什么语言写的
阅读原文
微软的工程师的 Quora 回答:kernel 几乎是 C,越往上层 C++ 就多了起来。超过400万个源文件,超过 500GB。

2019-04-09 一读

为何科技公司这么喜欢招经济学家
阅读原文
经济学 PhD 的训练很适合当代互联网公司:数据驱动、发掘事物的因果关系、双边市场等。

Apple Plus - brand versus subscription
阅读原文
Apple 推出一系列 service,其品牌从逼格高、高冷,转向注重隐私、对家庭友好,试图成为科技圈中的迪士尼。所以没有广告,没有 Game of Thrones 这种儿童不宜的神剧。

Why Setting Ambitious Goals Backfires
阅读原文
公司里实行OKR机制、指定目标,最好的结果是完成70%,完成太多标明你野心不大,完成太少标明你太弱了。但制定这种明知道完不成的目标,往往会驱使员工追逐短期利益、压力太大、容易沮丧。

我们为何从 Heroku 迁移到 Google Kubernetes Engine
阅读原文
这笔账算得不错:公司最初几年用 Heroku,虽然不便宜,但也比招若干个全职员工做运维要便宜许多。

RethinkDB: why we failed
阅读原文
RethinkDB从2009年开始做,到2017年宣告创业失败,是MongoDB的竞争产品。RethinkDB技术做得不错,打磨了三年才正式推出,却远远输给了技术不咋地、但营销很牛逼的MongoDB(已上市)。

2019-04-06 一读

个人隐私是穷人多交的税
阅读原文
低收入群体工作环境多有各种监控,雇主通过各种手段收集他们的个人信息;同时他们对信息安全/互联网个人隐私的知识比较匮乏,一不留神就把自己所有资料都贡献出去了。
贡献出大量个人信息的坏处:被各种机构用来拒绝你的依据;被各种广告精准定位。

Application logging best practices
阅读原文
别 log 太多信息,也别 log 太少;log 要有结构化;要用对 log 的等级,info 级的 log 千万不能把熟睡中的 oncall 的工程师吵醒;别因为 log 而影响了整体性能。

Google 频繁地放弃产品,对其品牌是巨大的损害
阅读原文
Google 规模庞大,做了很多产品,也放弃了很多产品。该不该投入时间精力去使用 Google 的新产品?或许用到明年就下线了?反方观点:Google 做得对,互联网思维,快速迭代,果断放弃没人用的产品,把人力资源分配到更有价值的产品上。

From Show HN to Series D
阅读原文
Segment 创始人 cto 讲述他们的创业故事。6年半以前创业几乎失败,死马当活马医地在 Hacker News 分享了一个 400 行的开源 js 文件,现如今融了 D 轮,估值 $15 亿。
在 Hacker News 上分享了项目,最后做大的例子还有不少。最有名的当属 Dropbox (2007年4月4日)与 Redis(2009年2月25日)了。

Jack Dorsey:只用 iPhone,管理两家上市公司
阅读原文
Jack Dorsey 唯一的计算设备是 iPhone,不管是家里还是工作,都没有 PC。作为两家上市公司的 CEO,好像也没有什么使用 PC 的地方。计算设备的主要作用就是发邮件,简单记事本,刷 Twitter。

2019-04-05 一读

艺多不压身对于创业者是个谬论,学的多不一定更好
阅读原文
JotForm创始人的文章,关于爱学习的人怎么面对信息过载。讲的是“学得多不一定更好”,读完感觉醍醐灌顶。对于成年人来说,艺多不压身,但什么都学,什么都做却分心也花精力。对于创业者来说,花太多时间去阅读,研究,学习,仿佛成了新的“高效拖延症”。过度学习让人感觉良好,不如多实践,出活。
感谢 Vicki Zhou 的投稿。

How to Make Wealth
阅读原文
这是 Paul Graham 在黑客与画家一书中的文章,写于创办 YC 之前、把公司卖给 Yahoo 财富自由之后,那个阶段正是他哲学家+创业/人生导师的人设成型的初期。
程序员如何致富?湾区初级程序员在公司上班,今年每天实际写代码时间仅有1、2小时,但年薪至少十几万刀起跳;公司付得起十几万,意味着一个初级程序员创造的价值至少也是十几万一年。如果初级程序员辞职了,不用开会、不用搞办公室政治、工作效率提高30倍,是不是一年就能至少赚300多万?这个逻辑如何?阅读原文。

Return On Luck
阅读原文
出生在1950年代、有钱白人家庭、中学就接触电脑编程、理科学得很好、就读藤校的美国人肯定不止 Bill Gates 一人,为啥他取得巨大成功了?
微软一开始是成立于新墨西哥州的 Albuquerque 做 Altair 电脑上的 Basic 解释器的小公司。如果你是风投,你会投资1975年的微软吗?Altair 一共生产了几台电脑?全世界有多少人需要用 Basic 解释器?市场能有多大?为什么公司在盛产外星人的新墨西哥州?
每个人的运气都是一种资本,不同的人拥有相同分量的运气,最终不同人取得的回报大小也不同。

公司每个员工相同薪水
阅读原文
二十个员工,远程办公,不同地区、不同职能,薪水都相同。这么做的好处与坏处?

寓言故事:两个程序员
阅读原文
从前有俩程序员分别在两家公司实现相同的系统。一人悠哉地写了精简的程序,实现所有需求提前完工,管理层觉得活太简单,颇为不爽;另一人虚张声势拉扯多人团队做超复杂的系统,实现多数需求,管理层以为活太复杂却能按时完工,实属不易,给予重赏。

JAVA面试题

为什么很多编程语言中数组都从0开始编号:

从 1 开始编号,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。

数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能做到极致。所以为了减少一次减法操作,数组选择了从 0 开始编号,而不是从 1 开始。

说数组起始编号非 0 开始不可。所以我觉得最主要的原因可能是历史原因。

C 语言设计者用 0 开始计数数组下标,之后的 Java、JavaScript 等高级语言都效仿了 C 语言,或者说,为了在一定程度上减少 C 语言程序员学习 Java 的学习成本,因此继续沿用了从 0 开始计数的习惯。实际上,很多语言中数组也并不是从 0 开始计数的,比如 Matlab。甚至还有一些语言支持负数下标,比如 Python。

JVM标记清除算法:

大多数主流虚拟机采用可达性分析算法来判断对象是否存活,在标记阶段,会遍历所有 GC ROOTS,将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后,清理工作才会开始。

不足:1.效率问题。标记和清理效率都不高,但是当知道只有少量垃圾产生时会很高效。2.空间问题。会产生不连续的内存空间碎片。

数据结构与算法之美学习12

排序(下):如何用快排思想在O(n)内查找第K大元素

归并排序

第一,归并排序可以是稳定的排序算法。
第二,归并排序的时间复杂度是 O(nlogn)
第三,归并排序的空间复杂度任何情况下都是 O(nlogn),它有一个致命的“弱点”,那就是归并排序不是原地排序算法。最大空间复杂度是 O(n)。

快速排序

快速排序不是原地排序算法
快速排序并不是一个稳定的排序算法。
快排的时间复杂度在大部分情况下的时间复杂度都可以做到 O(nlogn),只有在极端情况下,才会退化到 O(n2)。

内容小结

归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分治的思想,代码都通过递归来实现,过程非常相似。理解归并排序的重点是理解递推公式和 merge() 合并函数。同理,理解快排的重点也是理解递推公式,还有 partition() 分区函数。

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法,这也使它存在致命的缺点,即归并排序不是原地排序算法,空间复杂度比较高,是 O(n)。正因为此,它也没有快排应用广泛。

快速排序算法虽然最坏情况下的时间复杂度是 O(n2),但是平均情况下时间复杂度都是 O(nlogn)。不仅如此,快速排序算法时间复杂度退化到 O(n2) 的概率非常小,我们可以通过合理地选择 pivot 来避免这种情况。

突破网站复制粘贴的限制

第一步,复制以下代码

1
javascript:(function() { function R(a){ona = "on"+a; if(window.addEventListener) window.addEventListener(a, function (e) { for(var n=e.originalTarget; n; n=n.parentNode) n[ona]=null; }, true); window[ona]=null; document[ona]=null; if(document.body) document.body[ona]=null; } R("contextmenu"); R("click"); R("mousedown"); R("mouseup"); R("selectstart");})()

第二步:以chrome谷歌浏览器为例

  • 打开chrome的书签,点开书签管理器,右键添加网页。
  • 名称这里写上点我破解网页复制,网址上粘贴楼上的代码。确定就可以了。
  • 遇到不能复制的网页,点一下这条书签,OK可以复制了!

https://www.jianshu.com/p/a93fca575716
https://gist.github.com/Rand01ph/8dfa9a0ea396e560ac0f97373c863631