《算法之美》:指导工作与生活的算法
2022-07-03 21:42:27 0 举报
AI智能生成
登录查看完整内容
form豆瓣-内容简介:我们所有人的生活都受到有限空间和有限时间的限制,因此常常面临一系列难以抉择的问题。在一天或者一生的时光里,哪些事是我们应该做的,哪些是应该放弃的?我们对杂乱无序的容忍底线是什么?新的活动与熟悉并喜爱的活动之间如何平衡,才能取得令人愉快的结果?这些看似是人类特有的难题,其实不然,因为计算机也面临同样的问题,计算机科学家几十年来也一直在努力解决这些问题,而他们找到的解决方案可以给我们很多启发。 通过丰富的跨学科研究,作者指出,计算机算法也可以用来解答人类面临的这些问题。这本书告诉我们如何更有效地利用直觉、什么时候应该把选择权交给命运、无所适从的时候应该如何做出选择,以及如何有效地与他人保持联系。从找配偶到找停车位,从组织管理个人邮箱的收件箱到理解人类记忆的作用原理,这本书把计算机科学的智慧转化为人类生活的策略,引导我们做出明智的选择。
作者其他创作
大纲/内容
“摸清情况再行动准则”,先收集一些数据吧,即所谓“观察期”
源于所谓“秘书问题”的37%法则
表示数量
表示遴选过程持续的时间
37%法则具有灵活性
阀值准则:利用37%法则,通过设定的临界点确定需求对象
见好就收:成功的概率/失败的概率=实施的次数
最优停止理论
比例在35%与40%间,理想结果的可能性近与最高值
阀值与搜索成本呈正比例关系
探索价值降低
利用价值升高
探索:收集信息;利用:利用所拥有的信息
随时间推移
“赢留”是探索与利用的平衡优化,而“输变”则没考虑到剩余时间
赢留输变
重现在、轻未来的概念
几何贴现
贬值
期望值
是一个近似估值,用一个数量使两者达成平衡并求这个数量的最大值
回报率
基廷斯指数
在数据点的上下方添加误差条数,误差条越窄表明越精确
误差条线表明被测数量的真实值的合理范围
上限置信区间
面对不确定性的乐观选择
剩余时间越多时,应多探索
剩余时间越少时,应多利用
试验中的临床试验
探索与利用
互联网中的搜索引擎其次是排序引擎
打扫房间的时间客人的数量没有任何关系
常数时间O(1)
食物传递一圈所需要的时间
线性时间O(n)
与客人相互拥抱的次数
平方时间O(n²)
每增加一个客人都会让工作加倍
指数时间O(2的n次方)
通过洗牌为一副扑克牌排序
阶乘时间O(n!)
讨论问题与程序运行时间的关系
“大O”符号
逐个移动n个量的位置,而且每次移动需要跨越n个位置
冒泡排序
逐个移动n个量,而且在插入之前还需将每个量与n个量进行比较
插入排序
把排序对象分成若干组,每组排序后再逐一合并,复杂度为平方对数时间
合并排序
分组
把排序对象按照排序类别分成若干桶,每桶排序后即完成排序,复杂度达到线性时间
桶排序
排序
复杂的O(n²)
排序对象的比较结果不确定性
噪声
一个算法对不合理数据输入的反应能力和处理能力,也称容错性
健壮性
为了排序对象赋予一个标准的度量,不需要两两比较就可以为一群对象排好次序
竞争取代斗争
排列
比较计数排列
表现出未卜先知 的效果
将闲置时间最长的内容清理掉
最近最少使用(LRU)
前提是知道各种需求的先后顺序,制定数据结构,把完成整个序列的总时间降到最低
最优离线算法
增加联系的次数会使记忆更久,随着时间的推移,能够准确回忆的内容会减少
遗忘曲线
解释了大脑为适应世界而完成的精确调整,目的是为最可能需要的事物腾出存储空间
信息检索耗费的精力可以检验知识的渊博
有没有将最重要的东西放在大脑前台
延迟发生的频率可以看出组织管理是否合理
经验暴政
缓存
更好的减少最大延迟
最早到期日原则
总是先做最快完成的任务
最短加工时间
低优先级任务工作时被中断并触发调度器,产生中等优先级任务
优先级反转
当低优先级任务阻碍了高优先级任务时,此时低优先级任务上升为高优先级任务,继承被阻塞的优先级(原本的高优先级)
优先级继承
当某个任务在另一个任务完成前无法启动时的情况
优先级约束
拖延作为一种解决方案
反应的快慢
反应速度
可以做多少
吞吐量
中断合并
上下文切换
关联转换
全速运行但一事无成
避免进入颠簸状态
时间调度理论
各项任务赋予的权值划分;按照单位时间的重要性高低排序;使用最短加工时间算法
设定一个固定的时间使其中途停止,让时间调度做上下文切换,任务可能更加容易有效
大数据类型
小数据类型
对某一事物有一定的预估
依赖于先验概率(前提)
w为指定事件数;n为样本空间数
计算公式:(w+1)/(n+2)
预测算法:将再持续已经存在的时间;总存在的时间长为已存在时长的2倍
无先验概率信息(前提)
哥白尼原则
相乘法则
分布在不同区域的数值相乘
先验的可能性有很宽广的尺度
幂律分布
平均法则
使用分布的“自然”平均数作为指导
有一定的先验概率
正态分布
相加法则
具有更大且更小不可能结束的事物,持续了存在了一段时间
厄兰分布
先验预测的分布
预测在某个数值内,如果实值超出这个数值就会惊讶
如果没有达到平均水平,就会惊讶
任何事情的状态都有可能结束,因此没有多少意外惊喜
偏离了自己的经验统计
很难保持适当的先验分布
当人们谈论一些感兴趣的事或者互联网、电视机械式的传播信息时
保护好自己的先验
贝叶斯法则
预测未来时所面对的情况
思想模拟正在模拟思想的思想
递归
引诱对手进行无结果的递归可以成为其他游戏有效地策略
陷入无限递归的困境达到均衡的状态
势均力敌,相互僵持的状态
均衡策略
例:囚徒的困境-叛变
对对手所有可能策略的最佳反应,是强有力的策略
占优势策略
低调和率-无论好坏,系统本身就像它被精心管理的那样良好
高调和率,在谨慎地协调下,事情可能会最终变好,但如果没有某种形式的干预,就会陷入灾难
被用做衡量博弈中的合作(解决方案)和竞争(最大利己化)之间的差距
调和率
在正确的环境下,一群行为完全理性、完全正确的行为者
盲目追崇公共信息流,并认为他人行为是有用的导向
信息瀑布
可以成为有效的无限错误信息的牺牲品
博弈论
纳什均衡
访问者说你好
服务器确认你好,并回复你好
访问者确认了这一点
将它们的消息拆分放入一个个称为“数据包”的小碎片中,再将这些碎片合并到数据的公共流中
开始正题
三重握手,表示确认
包交换
发送指令时出现的重复冲突次数越多,退避等待的时间越长
即重发的最大延迟长度呈现一种指数级的递增
指数退避算法
承载量正常时增加数量
承载量饱和时减少一半
和式增加积式减少算法
待承载量恢复正常时再继续增加
超过了预期的承载量
缓存膨胀
每个在某一点之后到达的数据包都被简单的拒绝,并且有效地删除
通过延时以最大限度提高吞吐量
尾部丢弃算法
网络
提供了一个处理重负荷的解决方法
避免网络拥堵
对随机样本进行仔细的检查,可能是一种用以理解太复杂而不能直接理解的东西最有效的方法。通过抽样来估计它的值
抽样
重复观测快速接近确定性
随机算法
对比方案的优劣势
对应方案的更好或更糟
因为通过搜索解决方案,发现有些方案更好,有些更糟,而你的目标是达到最高的山峰
爬山算法
对于某个问题时,不要变成全量的随机性,每次做决定时使用一点儿随机性
如果想继续寻求改进,可能需要暂时恶化解决方案(前提)
梅特罗波利斯算法
局部最大值
一种常见的技术就是引入随机元素
进化和创造力
随机性
可能方案越多,其质量可能会更高
最小生成树
把问题带回现实前先消除一些约束条件,让问题暂时变的更加容易处理,最后再将约束添加到问题中
约束松弛
将离散的或二进制的选择变成连续体,然后再向上或向下延展
持续松弛
把不可能的变成仅仅是惩罚,要学会扭曲规则的艺术
拉格朗日松弛算法
松弛
解决那些最佳答案似乎遥不可及的问题时,最好的办法就是放松
将重心放在我们能够测量的数据而不是真正重要的问题上
产生的原因
表现为一条直线
单因子模型
表现为U型抛物线
双因素模型
表现在图标中的每一个点的串联
九因素模型
具体表现
因素越多,可能与现实数据越贴近,但不一定会得出更好的结果(数据崇拜)
评估模型是否给出合理的数据
如何概括没有见过的数据
使用二级数据来进行验证
交叉验证
检查方法
使优化误差的函数倾向于满足约束的梯度减少的方向
用来约束惩罚模型的复杂性
正则化
把复杂性下行压力放到因素的总权重上,同时设定重要因素的权重降为零,而得到一个更为精炼的模型,保留了子集收缩的优点
套索算法
寻找单一的最重要的因素,而不是直接跳跃到多因素模型
早期停止
解决方法
过度拟合(overfitting)
如果你有很高的不确定性和有限的数据,那么务必提前停止,做最简单的预测
算法之美
从观望阶段到行动阶段的时间选择,前提条件是事件本身存在严格的连续性,有进无退的单向进行。
序是搜索的准备工作时,要权衡一下排序的代价,代价太高就不必要排序了
缓存的好处除了节省成本以外,另一个是:在较小的空间内可以快速的搜索和提取信息
诚实和做自己
0 条评论
回复 删除
下一页