蚊章汇 - 算法
type: channel
link: https://linuxcn.bwsl.wang/tag/%E7%AE%97%E6%B3%95/
items: 硬核观察 #1144 量子计算机正在重演真空管计算机的历史吗？
items: 硬核观察 #888 谷歌请回创始人帮助谷歌以打赢 AI 之战
items: 硬核观察 #734 韦伯太空望远镜大量使用了 20 年前的一种 JavaScript 方言
items: 在《毁灭战士》中应用二叉空间分割（BSP）是何等天才之举？
items: 硬核观察 #731 无处不在的 DOOM，这次是拖拉机
items: 埃隆·马斯克开源推特算法的计划存在缺陷
items: 硬核观察 #403 微软 Exchange 曝出安全漏洞，可获取全球 Windows 域和应用凭证
items: 书评：《算法之美（ Algorithms to Live By ）》
items: 用数据科学搭建一个实时推荐引擎
items: 每个程序员都应该收藏的算法复杂度速查表

硬核观察 #1144 量子计算机正在重演真空管计算机的历史吗？
type: item
date: 2023-10-04T23:17:57+08:00
description: 量子计算机正在重演真空管计算机的历史吗？20 世纪 40 年代初，第一台真空管计算机投入使用，解决了人类无法解决的问题。这些庞大的机器复杂、特殊，而且普遍不可靠。在许多方面，今天的量子系统与早期的真空管计算机有着惊人的相似之处，它们也是难以置信的昂贵、特殊和不直观。如果量子系统能够像多年前的巨人计算机破解德国密码那样破解现代加密技术，将颠覆建立在现代计算技术之上的世界。量子系统的早期采用者将会获得最大收益，因此各国和各个公司都为量子成为真正竞争威胁的可能性投入了大量资金。不过，目前量子计算机能做的事情，没有一件是经典计算机做不到的，真正的创新将出现在我们用量子算法解决量子问题的时候。消息来源：The Register老王点评：从庞大到一个房间放不下的计算机，到如今的计算无处不在，才短短几十年。那么，从现在的量子计算机变成手持量子计算机，需要多少年，会改变多少事情？Meta 开始裁员元宇宙芯片部门Meta 公司计划裁掉其面向元宇宙的 Facebook 敏捷硅团队（FAST）员工，该部门约有 600 名员工。FAST 部门的任务是开发定制芯片，为 Meta 的现实实验室部门生产的增强现实和虚拟现实硬件提供动力。消息来源：路透社老王点评：元宇宙梦碎，不知道 Meta 还会改名回 Facebook 吗？结合上一条，或许元宇宙真正接管世界时，会是在量子计算普遍可用的时候。亚马逊利用秘密算法提高价格，获利 10 亿美元根据美国联邦贸易委员会（FTC）对亚马逊提起的垄断诉讼中被删节的部分内容，亚马逊使用了一种代号为 “尼斯项目” 的算法来测试它能以竞争对手会跟进的方式提高多少价格。该算法帮助亚马逊提高了各购物类别商品的利润，并影响竞争对手提高了价格。如果竞争对手没有将价格提高到亚马逊的水平，该算法就会自动将商品恢复到正常价位。据一位熟悉此事的人士称，亚马逊通过使用该算法获得了超过 10 亿美元的收入。亚马逊在 2019 年停止使用该算法，但原因不明。消息来源：华尔街日报老王点评：“算法是无辜的”，错的是经营商业的人和写算法的人？是吗？

硬核观察 #888 谷歌请回创始人帮助谷歌以打赢 AI 之战
type: item
date: 2023-01-21T22:33:22+08:00
description: 谷歌请回创始人帮助谷歌以打赢 AI 之战上个月，谷歌的创始人拉里·佩奇和谢尔盖·布林与该公司高管举行了几次会议，以应对 ChatGPT 对该公司的搜索业务的挑战。对谷歌来说，ChatGPT 看起来似乎可以提供一种在互联网上搜索信息的新方法。这两位创始人自从 2019 年离开谷歌的日常工作后，就没有在该公司呆过多少时间，他们审查了谷歌的人工智能产品战略，批准了将更多聊天机器人功能纳入谷歌搜索引擎的计划并提出了想法。消息来源：《纽约时报》老王点评：当年靠着搜索变成了一家独大，如今却有可能被 AI 掀翻。苹果开源了 40 年的 Lisa 操作系统作为苹果 Lisa 电脑发布四十周年庆典的一部分，苹果通过计算机历史博物馆公开了 Lisa OS 3.1 操作系统的源代码，它采用了苹果学术许可证协议，包括 26MB 源代码，超过 1300 个源文件。苹果 Lisa 发布于 1983 年 1 月 19 日，其名字来自于乔布斯的女儿。它是一款基于鼠标 GUI 的商用计算机，但由于太过昂贵而在商业上失败，苹果于 1985 年终止了该项目。但它为之后的 Macintosh 奠定了基础。消息来源：计算机历史博物馆老王点评：欢迎苹果公司将古老的操作系统“文物”放入博物馆。美科技公司反对对科技算法提起诉讼在美国最高法院关于 YouTube 算法的一个关键案件中，众多企业、互联网用户、学者甚至人权专家为大科技公司的责任盾牌辩护，他们认为，如果将人工智能驱动的推荐引擎排除在联邦法律保护之外，会对开放的互联网造成全面的改变。他们表示美国联邦法律《通信礼仪法》第 230 条对网络的基本功能至关重要，该法条被用来保护所有网站使其免受第三方内容的诉讼。他们认为，允许对科技行业算法提起诉讼的裁决，可能会甚至导致未来对非算法形式的推荐提起诉讼，并可能对个别互联网用户提起有针对性的诉讼。消息来源：CNN老王点评：算法有罪吗？有意的算法作恶应该被惩处吗？无意的算法错误应该被惩罚吗？黑盒式的 AI 决策的责任该由谁承担？这个信息时代打破了很多既有认知。回音受到批评后，CNET 暂停 了用 AI 辅助（#883） 撰写文章，并辩称，“我们不是秘密的做，而是悄悄的做。”

硬核观察 #734 韦伯太空望远镜大量使用了 20 年前的一种 JavaScript 方言
type: item
date: 2022-08-21T03:07:00+08:00
description: 韦伯太空望远镜大量使用了 20 年前的一种 JavaScript 方言根据韦伯太空望远镜的综合科学仪器模块手册，它有一堆预先写好的 JavaScript 脚本来完成特定的任务，地面上的科学家可以告诉它运行这些任务。当然，这些脚本不是运行在一个浏览器里面，而是用一个叫做“脚本处理器”的程序解释，然后它将根据脚本的要求，与其他的应用程序和系统联系。这些脚本所使用的语言是一种 JavaScript 版本 Nombas ScriptEase 5.00e，但开发它的公司已不存在，这种语言最后的版本发布于 2003 年。虽然韦伯太空望远镜是在 2021 年底发射的，但这个项目从上世纪八十年代就开始了，而建设在 2004 年开始时的。消息来源：The Verge老王点评：居然选择了这么古老而不严谨的脚本，这十年间就难道没有一点点改进的想法吗？VFX 参考平台建议动画行业升级到 RHEL 9VFX 参考平台旨在帮助规范数字内容创作领域的软件平台，以发布年度软件建议清单而闻名，如每个操作系统上的编译器版本，特定年份的 Qt/Python/Numpy 组件，以及基于行业反馈和与各种内容创作者和工作室互动的各种其他软件版本。他们发布了一份报告，供视觉效果和动画工作室在选择下一个 Linux 平台时考虑。他们发现很多工作室仍然依赖 CentOS 7，他们建议这些工作室不迟于 2024 年转移到新的操作系统，首选是红帽的 RHEL 9，或者 Rocky Linux、AlmaLinux 等下游分支。他们也建议可以考虑 Ubuntu Linux。消息来源：Phoronix老王点评：即便不想付费购买 RHEL 9，Rocky Linux 等也可以考虑。其实，根据我的研究， CentOS Stream 也是可以的。Meta 用算法“随机”解雇 60 名劳务派遣人员此前 Meta 与埃森哲签订了近 5 亿美元的合同，由隶属于后者的劳务派遣人员到 Meta 位于奥斯汀的办公室工作，主要开展内容审核和商业诚信等业务。Meta 通过视频电话会议告知被裁的员工，除了明确是“随机”选择之外，没有给出裁员的具体原因。去年 8 月份，游戏行业支付处理公司 Xsolla 也使用算法裁掉了 150 名员工。消息来源：纽约邮报老王点评：很多底层员工，在他们看起来，其实就是一个数字，可以掷骰子决定。

在《毁灭战士》中应用二叉空间分割（BSP）是何等天才之举？
type: item
date: 2022-08-20T00:15:49+08:00
description: 1993 年，游戏开发公司 id Software 发行了一款第一人称射击游戏 《 毁灭战士 DOOM 》，游戏一经发行迅速爆火。在今天看来，《毁灭战士》可谓有史以来最具影响力的游戏之一。《毁灭战士》发行之后的第十年（2003 年），记者 大卫·库什纳 David Kushner 出版了一本关于 id Software 的书，书名为《 Doom 启示录 Masters of Doom 》，后被奉为记录毁灭战士创作史的典范读物。几年前我曾读过这本书，如今内容已记得不太真切了，但是书中有一个关于 id Software 首席程序员 约翰·卡马克 John Carmack 的故事，我印象特别深刻。这里只对故事做粗略描述（具体情节请往下阅读）。实际上，早在《毁灭战士》开发前期，卡马克就发现自己为这款游戏编写的 3D 渲染器在渲染某些关卡时慢得像爬一样。对于《毁灭战士》这一对动感和速度有着相当高要求的射击游戏来说，这是一个非常严重的问题。意识到了这一问题的严重性，卡马克需要一个更加有效的渲染算法，于是他开始阅读相关论文。最后，他实现了一种叫做“ 二叉空间分割 binary space partitioning （BSP）”的技术，极大地提升了《毁灭战士》游戏引擎的运行速度，而这项技术此前从未用于电子游戏当中。一直以来，我对这个故事的印象十分深刻。卡马克将学术前沿研究运用于电子游戏之中，我觉得这正是他之所以成为传奇人物的原因。无论从哪个角度来看，卡马克都应该是电子游戏行业中人尽皆知的典型的天才程序员，只不过上面这个故事是我最先能够想到的理由。显而易见，“二叉空间分割”这个术语听起来就是难度相当高的课题，能够自行阅读论文并将其付诸实施实属不易，所以这个故事给我留下了深刻的印象。我一直认为卡马克的做法十分具有创见性，不过由于我既不懂二叉空间分割到底是怎样的一项技术，也不晓得这项技术在当时究竟有多么革新，所以我也并不确定自己的观点是否正确。如果按照从 霍默·辛普森 Homer Simpson （LCTT 译注：《辛普森一家人》中的那个老爹）到 阿尔伯特·爱因斯坦 Albert Einstein 的顺序为天才列出一套级别体系，那么卡马克将二叉空间分割技术运用于《毁灭战士》的做法究竟属于什么级别的天才之举呢？同时，我也在想，二叉空间分割这个概念最初是从哪儿来的，又是怎样吸引到卡马克的？因此，本篇文章不仅仅会讲述约翰·卡马克和《毁灭战士》的故事，也会探讨二叉空间分割树（BSP 树）数据结构的发展历史。有意思的是，BSP 树和计算机科学领域其他许多技术一样，最初都起源于军事研究领域。没错，《毁灭战士》的第一关卡 E1M1 就受到了美国空军的启发。VSD 难题BSP 树是计算机图形领域最具挑战性难题的解决方案之一。举个例子，为了渲染出三维场景，渲染器必须能够区分在一个特定角度下的可见物体和不可见物体。如果渲染时间比较充足，这一要求也算不上大问题；但是就理想情况来说，实时游戏引擎在 1 秒内至少需要完成 30 次区分任务。这一问题有时被称为 可见面检测 visible surface determination （VSD）问题。后来与卡马克合作开发《 雷神之锤 Quake 》（id Software 继《毁灭战士》之后开发的游戏）的程序员 迈克尔·亚伯拉什 Michael Abrash ，在自己的著作《 图形程序开发人员指南 Graphics Programming Black Book 》 中写道：我想探讨一下在我看来 3D 中最棘手的一个问题：可见面检测问题（在每个像素点上绘制合适的表面）以及与之密切相关的隐面消除问题（迅速去除不可见的多边形，用于加快可见表面检测速度）。简略起见，我将在下文采用缩写 VSD 来表示可见面检测和隐面消除。为什么我会认为 VSD 是 3D 中最棘手的问题呢？尽管纹理映射等光栅化问题更让人感兴趣而且也更重要，但是相对而言，它们是范围相对有限的任务。随着 3D 加速器的出现，它们逐渐被转移到硬件中。同时，它们只随着屏幕分辨率的增加而增加，而分辨率的增加是相对温和的。相反，VSD 却像是一个无底洞，目前应对方案也有很多。但实际上，在采用简单的方法处理 VSD 时，其性能会直接受到场景复杂程度的影响，而场景的复杂程度通常会以平方级或立方级的形式增大。所以在渲染过程中，VSD 很快就会成为制约因素。 [1] 亚伯拉什是在上个世纪九十年代末写的关于 VSD 问题的这些困难，这是在《毁灭战士》之后数年，这款游戏证明了普通人盼望着能用自家电脑玩很吃图形配置的游戏。九十年代早期，id Software 成立后发行了一些游戏。尽管当时的计算机还只是用来处理文字与表格或者执行其他任务，未尝想过要在上面运行游戏，id Software 必须对发行…

硬核观察 #731 无处不在的 DOOM，这次是拖拉机
type: item
date: 2022-08-18T03:05:55+08:00
description: 无处不在的 DOOM，这次是拖拉机在最近的 Def Con 安全会议上，安全研究人员演示了在约翰迪尔 4240 拖拉机的显示屏上运行 DOOM 游戏。研究人员花了数个月时间，来越狱该拖拉机所使用的 Linux 系统。在拖拉机上运行的 DOOM 游戏也经过了特别修改，场景被设置在玉米田里，玩家操纵拖拉机去消灭敌人。这一尝试不仅仅是好玩，其展示的获取 root 访问权限的方法，可能有助于农民绕过这类拖拉机的限制，自行维修拖拉机，这算是对“维护权”的一种努力。消息来源：Wired老王点评：方法已经有了，现在就缺一台可以玩 DOOM 的拖拉机了，知道这拖拉机多少钱嘛。中国主要互联网公司向网信办备案算法网信办上周公布了境内互联网信息服务算法备案清单，中国主要互联网公司向网信办披露了其使用的算法细节。清单包含了 30 个备案算法，其中包括网易新闻的推送算法和信息搜索算法，360 的搜索信息检索算法，微博热搜算法，美团配送调度决策算法，百度信息检索算法，抖音个性化推荐算法，淘宝推荐算法，微信看一看个性化推送算法，等等。消息来源：Solidot老王点评：被算法操纵下的世界，公开不公开，都无法逃避算法的操纵。微软为 Ubuntu 22.04 LTS 提供原生 .NET 6 支持微软和 Canonical 共同宣布了在 Ubuntu 22.04 LTS 主机和容器环境中可原生运行 .NET 应用。微软的 .NET 6 现在可以在 Ubuntu 22.04 LTS 上通过简单的命令安装使用。.NET 开发平台是微软对开源项目最早的贡献之一。Canonical 为 .NET 6 LTS 和 ASP.NET 运行时发布了新的、符合 OCI 标准的超小型设备镜像，无需 Shell 或软件包管理器。消息来源：Ubuntu老王点评：来自官方的 .NET 原生支持终于出现了，不知道有多少 .NET 程序会在 Linux 下运行？

埃隆·马斯克开源推特算法的计划存在缺陷
type: item
date: 2022-05-04T07:59:40+08:00
description: 报道称，在推特确认接受收购请求的几个小时后，埃隆·马斯克就明确表示了他对推特的期望。马斯克在一份新闻稿中罗列了他计划做出的重大改变，包括开源“决定用户在推流中看到什么”的算法。马斯克希望开源推特的算法，是因为他长期以来一直担心该平台有可能进行政治压制。但老实说，即便开源，也不可能达到他的预期效果。专家们担心，这可能反而带来一连串意想不到的问题。虽然马斯克对权威深恶痛绝，但是他对算法开源的野心和世界各地立法者的愿望不谋而合。近年来，许多政府都将这一原则作为打击大科技公司的基石。英国社交媒体监管机构 Ofcom 的首席执行官 Melanie Dawes 曾表示，社交媒体公司应当解释其代码的运作方式。此外，欧盟新近通过的《 数字服务法案 Digital Services Act （DSA）》于 4 月 23 日获得批准，该法案将责成平台提供更多的公开性。2022 年 2 月，美国的民主党参议员提交了《 算法问责法案 Algorithmic Accountability Act （AAA）》的立法申请。这些法案的目标是加强算法的透明度和监督，包括我们在社交媒体上的“ 时间轴 timeline ”和“ 新闻流 news feed ”以及我们生活的其他方面。允许竞争者看到并修改推特的算法，可能意味着有人会偷取源代码，并提供一个改名的版本。互联网的许多部分都运行在开源软件上，其中最著名的就是 OpenSSL，这是一个被大量在线使用的安全工具包，而它在 2014 年被黑客攻击了。还有一些已经创建的开源社交网络。Mastodon 是一个微博网络，为回应对 Twitter 主导地位的担忧而创建。它允许用户检查其代码，这些代码可在 GitHub 软件仓库中找到。然而，阅读一个算法背后的代码，并不总能告诉你它的工作方式，而且对于大部分普通人来说，它也提供不了足够的关于公司组织架构以及开发流程的信息。Jonathan Gray 是伦敦国王学院/关键基础设施研究的高级讲师，他说：“这有点像只用遗传物质来理解古代生物。是的，它能告诉我们的信息比任何方式都多，但如果说我们因此了解它们的生活方式，那就太夸张了。”推特同样也不是由单一算法控制的。Catherine Flick 是英国德蒙福特大学/研究计算和社会责任的研究员，她说：“其中一些会决定人们在他们的“时间轴”上看到什么趋势、内容或者推荐关注的人。调节用户“时间轴”上显示哪些信息的算法，将会是人们最感兴趣的。然而，即使如此，如果缺少训练数据，单纯开源算法也没多大用处。”Cobbe 认为，开源推特算法的危害大于好处。因为计算机代码并没有透露算法是如何开发或评估的：有哪些元素或考虑、在这个过程中的优先级是什么等等。所以开源可能不会使推特的透明度发生重大变化。反而，它可能会带来严重的安全隐患。via: https://www.opensourceforu.com/2022/04/elon-musks-plan-to-open-source-the-twitter-algorithm-has-flaws/作者：Laveesh Kocher 选题：lkxed 译者：lkxed 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出

硬核观察 #403 微软 Exchange 曝出安全漏洞，可获取全球 Windows 域和应用凭证
type: item
date: 2021-09-23T20:38:24+08:00
description: 微软 Exchange 曝出安全漏洞，可获取全球 Windows 域和应用凭证该漏洞存在于 Exchange 电子邮件服务器的 Autodiscover 协议中，允许电子邮件客户自动发现电子邮件服务器，提供凭证，然后接收适当的配置。为了获得这些自动配置，电子邮件客户通常会探测一系列预先确定的 URL，这些 URL 中采用客户域名和 autodiscover 等关键字组合而成。然而问题就在这里，在找不到这些预制域名时，Exchange 客户端会寻找 autodiscover.com、autodiscover.com.cn 等域名。也就是说，谁拥有这些域名，就会收到所有这些失败的请求，其中包含有用户的凭证。研究人员注册了一些这种域名，搭建了蜜罐，四个多月里收到了数百个请求和成千上万的凭证，其中还包括一些来自中国上市公司的凭证。微软滥用默认域名已经不是第一次了。当年 corp.com 域名就是最臭名昭著的一个，最后微软花了 160 万美元才把这个域名买下来。树莓派基金会获 4500 万美元融资，估值 5 亿非营利机构树莓派基金会于昨日宣布，其已完成新一轮 4500 万美元的融资。本轮融资由一家私人慈善基金会领投，融资后估值为 5 亿美元左右。树莓派打算将这笔资金用于扩展丰富的 Pi 微处理器产品线，另外计划在面向广大消费者群体的“自建 PC”和面向工业应用的物联网领域加大营销投入。目前树莓派的年设备出货量超过 700 万台，且树莓派基金会正在向 100 多个市场区域投放超过 4200 台由 Pi 驱动的 PC 。这是最成功的单板机了，你要是没有一块吃灰的树莓派，你都不好意思说自己是个计算机爱好者。MIT 新研究表明 43% 的算法改进速度超过摩尔定律MIT 的两位研究人员对来自 57 本教科书，超过 1137 篇研究论文的数据进行了分析，统计了从 1940 年到现在的各种算法的改进，他们发现，在 110 个算法家族上，对中等规模（n=1000）的问题来说，只有 18% 的算法改进率快于硬件；当规模达到百万、亿、甚至万亿级别时，算法的改进速度就超过了硬件性能；甚至有 14% 的算法家族的改进率超过 1000%，远超硬件改进所带来的性能提升。硬件的更新毕竟需要更多时间和投入，还是人类大脑做成的改进毕竟快。

书评：《算法之美（ Algorithms to Live By ）》
type: item
date: 2018-10-01T19:27:50+08:00
description: 又一次为了工作图书俱乐部而读书。除了其它我亲自推荐的书，这是我至今最喜爱的书。作为计算机科学基础之一的研究领域是算法：我们如何高效地用计算机程序解决问题？这基本上属于数学领域，但是这很少关于理想的或理论上的解决方案，而是更在于最高效地利用有限的资源获得一个充分（如果不能完美）的答案。其中许多问题要么是日常的生活问题，要么与人们密切相关。毕竟，计算机科学的目的是为了用计算机解决实际问题。《 算法之美 Algorithms to Live By 》提出的问题是：“我们可以反过来吗”——我们可以通过学习计算机科学解决问题的方式来帮助我们做出日常决定吗？本书的十一个章节有很多有趣的内容，但也有一个有趣的主题：人类早已擅长这一点。很多章节以一个算法研究和对问题的数学分析作为开始，接着深入到探讨如何利用这些结果做出更好的决策，然后讨论关于人类真正会做出的决定的研究，之后，考虑到典型生活情境的限制，会发现人类早就在应用我们提出的最佳算法的特殊版本了。这往往会破坏本书的既定目标，值得庆幸的是，它决不会破坏对一般问题的有趣讨论，即计算机科学如何解决它们，以及我们对这些问题的数学和技术形态的了解。我认为这本书的自助效用比作者打算的少一些，但有很多可供思考的东西。（也就是说，值得考虑这种一致性是否太少了，因为人类已经擅长这方面了，更因为我们的算法是根据人类直觉设计的。可能我们的最佳算法只是反映了人类的思想。在某些情况下，我们发现我们的方案和数学上的典范不一样，但是在另一些情况下，它们仍然是我们当下最好的猜想。)这是那种章节列表是书评里重要部分的书。这里讨论的算法领域有最优停止、探索和利用决策（什么时候带着你发现的最好东西走，以及什么时候寻觅更好的东西），以及排序、缓存、调度、贝叶斯定理（一般还有预测）、创建模型时的过拟合、放松（解决容易的问题而不是你的实际问题）、随机算法、一系列网络算法，最后还有游戏理论。其中每一项都有有用的见解和发人深省的讨论——这些有时显得十分理论化的概念令人吃惊地很好地映射到了日常生活。这本书以一段关于“可计算的善意”的讨论结束：鼓励减少你自己和你交往的人所需的计算和复杂性惩罚。如果你有计算机科学背景（就像我一样），其中许多都是熟悉的概念，而且你因为被普及了很多新东西或许会有疑惑。然而，请给这本书一个机会，类比法没你担忧的那么令人紧张。作者既小心又聪明地应用了这些原则。这本书令人惊喜地通过了一个重要的合理性检查：涉及到我知道或反复思考过的主题的章节很少有或没有明显的错误，而且能讲出有用和重要的事情。比如，调度的那一章节毫不令人吃惊地和时间管理有关，通过直接跳到时间管理问题的核心而胜过了半数的时间管理类书籍：如果你要做一个清单上的所有事情，你做这些事情的顺序很少要紧，所以最难的调度问题是决定不做哪些事情而不是做这些事情的顺序。作者在贝叶斯定理这一章节中的观点完全赢得了我的心。本章的许多内容都是关于贝叶斯先验的，以及一个人对过去事件的了解为什么对分析未来的概率很重要。作者接着讨论了著名的棉花糖实验。即给了儿童一个棉花糖以后，儿童被研究者告知如果他们能够克制自己不吃这个棉花糖，等到研究者回来时，会给他们两个棉花糖。克制自己不吃棉花糖（在心理学文献中叫作“延迟满足”）被发现与未来几年更好的生活有关。这个实验多年来一直被引用和滥用于各种各样的宣传，关于选择未来的收益放弃即时的快乐从而拥有成功的生活，以及生活中的失败是因为无法延迟满足。更多的邪恶分析（当然）将这种能力与种族联系在一起，带有可想而知的种族主义结论。我对棉花糖实验有点兴趣。这是一个百分百让我愤怒咆哮的话题。《算法之美》是我读过的唯一提到了棉花糖实验并应用了我认为更有说服力的分析的书。这不是一个关于儿童天赋的实验，这是一个关于他们的贝叶斯先验的实验。什么时候立即吃棉花糖而不是等待奖励是完全合理的？当他们过去的经历告诉他们成年人不可靠，不可信任，会在不可预测的时间内消失并且撒谎的时候。而且，更好的是，作者用我之前没有听说过的后续研究和观察支持了这一分析，观察到的内容是，一些孩子会等待一段时间然后“放弃”。如果他们下意识地使用具有较差先验的贝叶斯模型，这就完全合情合理。这是一本很好的书。它可能在某些地方的尝试有点太勉强（数学上最优停止对于日常生活的适用性比我认为作者想要表现的更加偶然和牵强附会），如果你学过算法，其中一些内容会感到熟悉，但是它的行文思路清晰，简洁，而且编辑得非常好。这本书没有哪一部分对不起它所受到的欢迎，书中的讨论贯穿始终。如果你发现自己“已经知道了这一切”，你可能还会在接下来几页中遇到一个新的概念或一个简洁的解释。有时作者会做一些我从没想到但是回想起来正确的联系，比如将网络协议中的指数退避和司法系统中的选择惩罚联系起来。还有意识到我们的现代通信世界并不是一直联系…

用数据科学搭建一个实时推荐引擎
type: item
date: 2016-12-15T00:57:56+08:00
description: 编者注：本文是 2016 年 4 月 Nicole Whilte 在欧洲 GraphConnect 时所作。这儿我们快速回顾一下她所涉及的内容：图数据库推荐基础社会化推荐相似性推荐集群推荐今天我们将要讨论的内容是数据科学和 图推荐 （ graph recommendations ） ：我在 Neo4j 任职已经两年了，但实际上我已经使用 Neo4j 和 Cypher 工作三年了。当我首次发现这个特别的 图数据库 （ graph database ） 的时候，我还是一个研究生，那时候我在奥斯丁的德克萨斯大学攻读关于社交网络的统计学硕士学位。实时推荐引擎是 Neo4j 中最广泛的用途之一，也是使它如此强大并且容易使用的原因之一。为了探索这个东西，我将通过使用示例数据集来阐述如何将统计学方法并入这些引擎中。第一个很简单 - 将 Cypher 用于社交推荐。接下来，我们将看一看相似性推荐，这涉及到可被计算的相似性度量，最后探索的是集群推荐。图数据库推荐基础下面的数据集包含所有达拉斯 Fort Worth 国际机场的餐饮场所，达拉斯 Fort Worth 国际机场是美国主要的机场枢纽之一：我们把节点标记成黄色并按照出入口和航站楼给它们的位置建模。同时我们也按照食物和饮料的主类别将地点分类，其中一些包括墨西哥食物、三明治、酒吧和烤肉。让我们做一个简单的推荐。我们想要在机场的某一确定地点找到一种特定食物，大括号中的内容表示是的用户输入，它将进入我们的假想应用程序中。这个英文句子表示成 Cypher 查询：这将提取出该类别中用户所请求的所有地点、航站楼和出入口。然后我们可以计算出用户所在位置到出入口的准确距离，并以升序返回结果。再次说明，这个非常简单的 Cypher 推荐仅仅依据的是用户在机场中的位置。 社交推荐 （ Social Recommendations ） 让我们来看一下社交推荐。在我们的假想应用程序中，用户可以登录并且可以用和 Facebook 类似的方式标记自己“喜好”的地点，也可以在某地签到。考虑位于我们所研究的第一个模型之上的数据模型，现在让我们在下面的分类中找到用户的朋友喜好的航站楼里面离出入口最近的餐饮场所：MATCH 子句和我们第一次 Cypher 查询的 MATCH 子句相似，只是现在我们依据喜好和朋友来匹配：前三行是完全一样的，但是现在要考虑的是那些登录的用户，我们想要通过 :FRIENDS_WITH 这一关系来找到他们的朋友。仅需通过在 Cypher 中增加一些行内容，我们现在已经把社交层面考虑到了我们的推荐引擎中。再次说明，我们仅仅显示了用户明确请求的类别，并且这些类别中的地点与用户进入的地方是相同的航站楼。当然，我们希望按照登录并做出请求的用户来滤过这些目录，然后返回地点的名字、位置以及所在目录。我们也要显示出有多少朋友已经“喜好”那个地点以及那个地点到出入口的确切距离，然后在 RETURN 子句中同时返回所有这些内容。 相似性推荐 （ Similarity Recommendations ） 现在，让我们看一看相似性推荐引擎：和前面的数据模型相似，用户可以标记“喜好”的地点，但是这一次他们可以用 1 到 10 的整数给地点评分。这是通过前期在 Neo4j 中增加一些属性到关系中建模实现的。这将允许我们找到其他相似的用户，比如以上面的 Greta 和 Alice 为例，我们已经查询了他们共同喜好的地点，并且对于每一个地点，我们可以看到他们所设定的权重。大概地，我们可以通过他们的评分来确定他们之间的相似性大小。现在我们有两个向量：现在让我们按照 欧几里得距离 （ Euclidean distance ） 的定义来计算这两个向量之间的距离：我们把所有的数字带入公式中计算，然后得到下面的相似度，这就是两个用户之间的“距离”：你可以很容易地在 Cypher 中计算两个特定用户的“距离”，特别是如果他们仅仅同时“喜好”一个很小的地点子集。再次说明，这儿我们依据两个用户 Alice 和 Greta 来进行匹配，并尝试去找到他们同时“喜好”的地点：他们都有对最后找到的地点的 :LIKES 关系，然后我们可以在 Cypher 中很容易的计算出他们之间的欧几里得距离，计算方法为他们对各个地点评分差的平方求和再开平方根。在两个特定用户的例子中上面这个方法或许能够工作。但是，在实时情况下，当你想要通过和实时数据库中的其他用户比较，从而由一架飞机上的一个用户推断相似用户时，这个方法就不一定能够工作。不用说，至少它不能够很好的工作。为了找到解决这个问题的好方法，我们可以预先计算好距离并存入实际关系中：当遇到一个很大的数据集时，我们需要成批处理这件事，在这个很小的示例数据集中，我们可以按照所有用户的 迪卡尔乘积 （ Cartesian …

每个程序员都应该收藏的算法复杂度速查表
type: item
date: 2016-06-20T20:36:00+08:00
description: 算法复杂度这件事这篇文章覆盖了计算机科学里面常见算法的时间和空间的 大 O （ Big-O ） 复杂度。我之前在参加面试前，经常需要花费很多时间从互联网上查找各种搜索和排序算法的优劣，以便我在面试时不会被问住。最近这几年，我面试了几家硅谷的初创企业和一些更大一些的公司，如 Yahoo、eBay、LinkedIn 和 Google，每次我都需要准备这个，我就在问自己，“为什么没有人创建一个漂亮的大 O 速查表呢？”所以，为了节省大家的时间，我就创建了这个，希望你喜欢！--- Eric 图例 绝佳不错一般不佳糟糕数据结构操作数据结构时间复杂度空间复杂度 平均最差最差 访问搜索插入删除访问搜索插入删除 ArrayO(1)O(n)O(n)O(n)O(1)O(n)O(n)O(n)O(n)Stack)O(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)Singly-Linked ListO(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)Doubly-Linked ListO(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)Skip ListO(log(n))O(log(n))O(log(n))O(log(n))O(n)O(n)O(n)O(n)O(n log(n))Hash Table-O(1)O(1)O(1)-O(n)O(n)O(n)O(n)Binary Search TreeO(log(n))O(log(n))O(log(n))O(log(n))O(n)O(n)O(n)O(n)O(n)Cartesian Tree-O(log(n))O(log(n))O(log(n))-O(n)O(n)O(n)O(n)B-TreeO(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)Red-Black TreeO(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)Splay Tree-O(log(n))O(log(n))O(log(n))-O(log(n))O(log(n))O(log(n))O(n)AVL TreeO(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)数组排序算法算法时间复杂度空间复杂度 最佳平均最差最差QuicksortO(n log(n))O(n log(n))O(n^2)O(log(n))MergesortO(n log(n))O(n log(n))O(n log(n))O(n)TimsortO(n)O(n log(n))O(n log(n))O(n)HeapsortO(n log(n))O(n log(n))O(n log(n))O(1)Bubble SortO(n)O(n^2)O(n^2)O(1)Insertion SortO(n)O(n^2)O(n^2)O(1)Selection SortO(n^2)O(n^2)O(n^2)O(1)Shell SortO(n)O((nlog(n))^2)O((nlog(n))^2)O(1)Bucket SortO(n+k)O(n+k)O(n^2)O(n)Radix SortO(nk)O(nk)O(nk)O(n+k)图操作节点 / 边界管理存储增加顶点增加边界移除顶点移除边界查询Adjacency listO(V+E)O(1)O(1)O(V+E)O(E)O(V)Incidence listO(V+E)O(1)O(1)O(E)O(E)O(E)Adjacency matrixO(V^2)O(V^2)O(1)O(V^2)O(1)O(1)Incidence matrixO(V⋅E)O(V⋅E)O(V⋅E)O(V⋅E)O(V⋅E)O(E)堆操作类型时间复杂度 Heapify查找最大值分离最大值提升键插入删除合并Linked List (sorted)-O(1)O(1)O(n)O(n)O(1)O(m+n)Linked List (unsorted)-O(n)O(n)O(1)O(1)O(1)O(1)Binary HeapO(n)O(1)O(log(n))O(log(n))O(log(n))O(log(n))O(m+n)Binomial Heap-O(1)O(log(n))O(log(n))O(1)O(log(n))O(log(n))Fibonacci Heap-O(1)O(log(n))O(1)O(1)O(log(n))O(1)大 O 复杂度图表推荐阅读Cr…