硬核观察 #1144 量子计算机正在重演真空管计算机的历史吗？
量子计算机正在重演真空管计算机的历史吗？20 世纪 40 年代初，第一台真空管计算机投入使用，解决了人类无法解决的问题。这些庞大的机器复杂、特殊，而且普遍不可靠。在许多方面，今天的量子系统与早期的真空管计算机有着惊人的相似之处，它们也是难以置信的昂贵、特殊和不直观。如果量子系统能够像多年前的巨人计算机破解德国密码那样破解现代加密技术，将颠覆建立在现代计算技术之上的世界。量子系统的早期采用者将会获得最大收益，因此各国和各个公司都为量子成为真正竞争威胁的可能性投入了大量资金。不过，目前量子计算机能做的事情，没有一件是经典计算机做不到的，真正的创新将出现在我们用量子算法解决量子问题的时候。消息来源：The Register老王点评：从庞大到一个房间放不下的计算机，到如今的计算无处不在，才短短几十年。那么，从现在的量子计算机变成手持量子计算机，需要多少年，会改变多少事情？Meta 开始裁员元宇宙芯片部门Meta 公司计划裁掉其面向元宇宙的 Facebook 敏捷硅团队（FAST）员工，该部门约有 600 名员工。FAST 部门的任务是开发定制芯片，为 Meta 的现实实验室部门生产的增强现实和虚拟现实硬件提供动力。消息来源：路透社老王点评：元宇宙梦碎，不知道 Meta 还会改名回 Facebook 吗？结合上一条，或许元宇宙真正接管世界时，会是在量子计算普遍可用的时候。亚马逊利用秘密算法提高价格，获利 10 亿美元根据美国联邦贸易委员会（FTC）对亚马逊提起的垄断诉讼中被删节的部分内容，亚马逊使用了一种代号为 “尼斯项目” 的算法来测试它能以竞争对手会跟进的方式提高多少价格。该算法帮助亚马逊提高了各购物类别商品的利润，并影响竞争对手提高了价格。如果竞争对手没有将价格提高到亚马逊的水平，该算法就会自动将商品恢复到正常价位。据一位熟悉此事的人士称，亚马逊通过使用该算法获得了超过 10 亿美元的收入。亚马逊在 2019 年停止使用该算法，但原因不明。消息来源：华尔街日报老王点评：“算法是无辜的”，错的是经营商业的人和写算法的人？是吗？
硬核观察 #888 谷歌请回创始人帮助谷歌以打赢 AI 之战
谷歌请回创始人帮助谷歌以打赢 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 方言
韦伯太空望远镜大量使用了 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）是何等天才之举？
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 必须对发行的游戏进行编程，使其能在计算机上流畅运行。为了实现这一飞跃，尤其是为了能让在《毁灭战士》之前 id Software 发行的少数 3D 游戏在电脑上运行，id Software 必须做出革新。在这些游戏中，所有的关卡在设计时都受到了一定限制，以便更容易解决 VSD 问题。例如，在《毁灭战士》之前，id Software 发行了《 德军总部 3D 版 Wolfenstein 3D 版 》，该游戏的每一个关卡都是由与坐标轴平齐的墙壁组成。换言之，在《德军总部 3D 版》的游戏画面里，你看到的只有南北方向或者东西方向的墙壁。在游戏中，墙壁与墙壁之间有着固定的间隔，所有过道的宽度或是一个方格，或是两个方格等等，但绝不会出现 2.5 个方格。如此一来，尽管 id Software 团队只能设计出外观十分相似的关卡，但这也让卡马克为 《德军总部 3D 版》 编写渲染器的工作简单了不少。通过将屏幕上的光线“齐射”入虚拟游戏世界，《德军总部 3D 版》的渲染器解决了 VSD 问题。通常来说，使用光线的渲染器叫做“光线投射”渲染器。这种渲染器的速度一般较慢，因为解决内部的 VSD 问题涉及到在光线和游戏中的物体之间找到第一个交点，这通常需要进行大量的计算。但在 《德军总部 3D 版》，由于所有的墙壁都与网格平齐，所以光线与墙壁相交的位置只能在网格线上。如此一来，渲染器只需逐个检查这些交点即可。如果渲染器先从离玩家视角最近的交点开始检查，接着检查下一个最近的交点，以此类推，最后遇到第一面墙壁时停止检查。这样，VSD 问题便轻而易举地得到了解决。光线从每一个像素点向前投射，与画面物体接触时停止，这一方法是可行的。因为从 CPU 资源来看，投射的成本很低。事实上，由于每面墙壁高度相同，因此针对同列的像素点，投射的光线只需一条。尽管当时还没有专业的图形显卡，《德军总部 3D 版》凭借这一取巧之法得以在配置较低的个人电脑上正常运行起来。然而，这个办法并不适用于《毁灭战士》。因为 id Software 为这款新游戏增添了许多新元素 —— 倾斜的墙面、楼梯以及高低不一的天花板。光线投射的办法自然也就不好用了，于是卡马克编写出了一个新的渲染器。《德军总部 3D 版》的渲染器关注的是图像，将光线投射到屏幕像素表示的列上，而 《毁灭战士》 关注的则是物体。换句话说，《毁灭战士》 的渲染器会记录游戏场景中的所有物体，继而将其投射到屏幕当中；而非记录屏幕上的像素点，判断每个像素点的颜色。对于强调物体的渲染器来说，可以使用 Z 缓冲区来解决 VSD 问题，比较简单。每次将物体投射到屏幕上时，需要对每个用于绘制的像素点进行检查。如果你想绘制出的物体的部分和已经绘制在目标像素点上的物体相比更加靠近玩家，可以将其覆盖。否则，必须保持像素不变。尽管办法很简单，但是 Z 缓冲区对内存的要求较高，而且渲染器可能仍然要花费大量的 CPU 资源来投射玩家永远不会看到的水平几何体。在 20 世纪 90 年代，使用 Z 缓冲区的方法还存在着其他缺陷：IBM 兼容机（PC）搭载的是一种叫 VGA 的显示适配器系统，在这类电脑上，将图像写入帧缓冲区的成本非常之高。因此，在只会以后被覆盖的像素上绘制花费的时间拖慢了渲染器的性能。考虑到将图像写入帧缓冲区的成本非常之高，理想的渲染器需要首先绘制离玩家最近的物体，接着是比较近的物体，以此类推，直到屏幕上每个像素点都写入了信息。这时，渲染器会停止运行，大幅缩短远处不可见物体的渲染时间。这种由近及远对物体进行排序的方法也可以解决 VSD 问题。那么问题又来了：什么才是玩家可以看到的？最初，卡马克打算依靠《毁灭战士》的关卡布局来解决 VSD 问题。首先用渲染器绘制出玩家目前所在房间的墙壁，之后玩家冲进隔壁房间，再绘制出隔壁房间的墙壁。由于每个房间互不遮挡，这一办法也能解决 VSD 问题。而互相遮挡的房间可以分割成若干互不遮挡的“区域”。在 YouTube 上的一个 视频 中，Bisqwit 展示了自己制作出来的使用了相同算法的渲染器。可以看到，如果以超慢的速度运行，便能一睹渲染的具体过程。这一算法同样运用到了《毁灭公爵 3D 版》当中，这款游戏在 《毁灭战士》 推出三年之后发行，当时 CPU 的性能也更加强大了。1993 年，尽管在硬件上已经可以运行游戏了，但是使用这一算法的《毁灭战士》渲染器在复杂的层级结构上依旧表现吃力，尤其是在房间分割出来的各部分相互嵌套的情况下。不巧的是，这类层级结构正是构造环形楼梯等物体的唯一办法。沿着环形楼梯走下去，直到走入已经绘制好的区域，由于这其中涉及多次循环下降运动，导致游戏引擎的运行速度大幅降低。在 id Software 团队意识到《毁灭战士》游戏引擎的速度可能过慢时，公司还面临着其他任务：将《德军总部 3D 版》移植到超级任天堂游戏机（简称“超任”）上。那时，超任的性能比 IBM 兼容机还要差。结果表明，尽管光线投射渲染器非常简单，但是想要在超任上快速运行是不可能的。于是，卡马克着手研究更为高效的算法。事实上，也正是为了顺利将《德军总部》移植到超任，卡马克首次研究了二叉空间分割技术，并将其付诸应用。由于《德军总部 3D 版》的墙壁与坐标轴平齐，所以二叉空间分割技术应用起来也比较简单直接；但是《毁灭战士》的情况则比较复杂。不过，卡马克发现，二叉空间分割树同样可以用来解决《毁灭战士》速度过慢的问题。二叉空间分割 二叉空间分割 binary space partitioning （BSP）会提前将 3D 场景分割为若干部分，使 VSD 问题易于解决。讲到这里，你需要先了解一下为什么分割场景可以奏效：如果你在场景上画条线（对应三维空间里的一个平面），你就可以指出玩家或者摄像机视角在这条线的哪一侧，在这条线另一侧的物体无法遮挡玩家所在一侧的物体。如果多次重复这一操作，该三维场景最终会被分割为多个区域，这并不是对原始场景的改进，只是现在你知道了更多关于场景的不同部分会如何相互阻挡。首次阐述上述三维场景分割的是美国空军的研究员，他们曾尝试向美国空军证明计算机图形已经非常先进，可以应用到飞行模拟器领域。1969 年，他们将研究发现发表在一份题为《计算机生成图像在图形仿真中的应用研究》的报告中。该报告的总结部分指出，计算机图形可用于训练飞行员，但也警告说，其实际应用可能会受制于 VSD 问题：实时图像处理需要解决的一个关键问题就是优先级问题，或称隐藏线问题。在我们平时用眼睛观察外界时，大自然替我们轻易地解决了这一问题：不透明物体上的一个点，掩盖了同一视觉方向上、且距离较远的所有其它物体。但在计算机中，这项任务却非常困难。图像处理需要解决的优先级问题，随着环境复杂程度的增加，计算量会呈指数级增长，随即就会超过绘制物体透视图所需的计算负载。 [2] 他们在报告中提出了一项基于构造“遮挡矩阵”的方案，这一方案据说早些时候曾被应用于 NASA 的项目当中。研究员指出，平面将场景一分为二，可用来解决平面两侧物体之间存在的“任何优先级问题”。通常情况下，可能需要明确将这些平面添加到场景中，但对某些几何体，只需借助你已经拥有的几何体的表面即可。他们举了一个例子，如下图：p 1、p 2 以及 p 3 是三个不同的平面，如果摄像机视角位于其中一个平面的前方，即“正”面，p i 的值就等于 1。这种矩阵展示出基于三个不同平面和摄像机视角位置的三个物体之间的关系 —— 如果物体 a i 遮挡了物体 a j，那么 a ij 在此矩阵中的数值等于 1。研究人员指出，这种矩阵可以应用到硬件中，对每一帧进行重新评估。该矩阵基本上可以用作大型的开关，或者一种预置的 Z 缓冲区。在绘制给定的物体时，如果在物体所在列上得出数值 1，并且所在行已经在绘制中，那么物体被遮挡的部分就不会绘制出来。不过，该矩阵方法的主要缺点在于，为了在场景中表示出 n 个物体，你需要一个尺寸为 n 2 的矩阵。于是，研究人员们继续深入，探究将遮挡矩阵表示为“优先级列表”的可行性，该列表的尺寸是 n，可确定物体绘制的顺序。他们随即发现，诸如上图此类场景根本无法确定顺序（因为它存在循环阻塞的现象）。因此，他们花了很多时间来阐明“合适”与“不合适”场景之间的数学区别。最后，他们得出了一个结论：至少对于“合适的”场景下，优先级列表是可以制作出来的；而对场景设计师来说，避免设计出“不合适”的场景也不是一件难事。但是，他们并没有说明如何生成该列表。可以说，这份 1969 年的研究的首要贡献在于提出了：至少，在 理论上，可以采用平面分割的方法，对场景中的物体进行渲染排序。直到 1980 年，一份题为《基于优先级树结构的可见表面生成》的论文提出了解决该问题的具体算法。在这份论文中，作者 亨利·福克斯 Henry Fuchs 、 泽维·凯德姆 Zvi Kedem 以及 布鲁斯·内勒 Bruce Naylor 介绍了 BSP 树。他们指出，这种新的数据结构“可以替代十年前首次使用，但由于一些问题未得到广泛发展的方案”（即前文 1969 年美国空军相关研究中的方案）。 [3] BSP 树一经生成，即可用于确定场景中物体的优先级顺序。三人在论文中对 BSP 树的工作原理给出了相当可读的解释。但在本文，我将尝试使用更加通俗的语言，介绍给大家。首先，在场景中选定一个多边形，将该多边形所在的平面作为分割平面。同时，该多边形充当树的根节点。场景中剩下的多边形会分散在分割平面的两侧。位于分割表面“前方”或者与分割平面相交后位于“前”半部分的多边形落在了根节点左侧的左子树上；位于分割表面“后方”或者与分割平面相交后位于“后”半部分的多边形落在了右子树上。接着，递归重复这一过程：在左子树和右子树上各选定一个多边形，作为各自空间新的分割平面，继而二分出来更多的子空间和子树。等到全部的多边形均选定之后，二叉空间分割也就结束了。假设你想由后向前将场景中的几何图形进行渲染。（这就是所谓的“ 画家算法 painter's algorithm ”。因为在绘制时，距离摄像机较远的多边形会被距离摄像机较近的多边形所覆盖，借此正确进行渲染任务。）如果想要实现这一算法，必须按顺序遍历 BSP 树，左右子树的渲染顺序由摄像机视角与节点所在分割平面的位置关系决定的。因此，针对树上的每个节点，首先渲染距离分割平面较“远”一侧的所有多边形，接着是位于平面上的多边形，最后是距离平面较“近”一侧的所有多边形 —— “远”与“近”相对于摄像机视角而言。根据前文，距离分割平面较远一侧的多边形无法遮挡近侧的物体，所以这种方法可以解决 VSD 问题。下图表示一个简单的二维场景的 BSP 树的构造与遍历过程。在二维中，分割平面变成了分割线，但就基本原理而言，与复杂的三维场景并无二致。第一步：根分割线落在 D 墙上，将剩下的几何图形分为两组。第二步：继续分割位于 D 墙两侧的空间。C 墙是其中一侧的唯一一堵墙壁，因此无需再分。另一侧，B 墙形成新的分割平面。因为 A 墙与新的分割平面相交，所以必须将其分割为两堵墙。第三步：参照右上方视角，由后向前对墙壁进行排序，对执行画家算法很有帮助。这就是树的顺序遍历过程。福克斯、凯德姆以及内勒多次强调了 BSP 树的优势：它只需构建一次。可能有些难以置信，但实际上无论摄像机视角位于何处，同一棵 BSP 树都可以用来渲染一个场景。只要场景中的多边形没有移动，BSP 树就不会失效。因此，BSP 树在实时渲染任务中非常实用 —— 构建树时的所有艰巨任务都可以在渲染工作开展之前完成。同时，三人也提到了一项需要进一步深入研究的问题：究竟怎样才能构建出一棵 “高质量的” BSP 树？BSP 树的质量取决于用作分割平面的多边形的选择。我在前文跳过了这一问题，不过如果用作分割平面的多边形与其他多边形相交，那么为了让 BSP 算法发挥作用，必须将相交的多边形一分为二，这样两部分就可以分在不同的空间。但是如果这种现象反复出现，BSP 树的构建势必会大幅增加场景中多边形的数量。内勒后来在其 1993 年的论文《构建高质量的分割树》中提及这一问题。卡马克的同事，id Software 的共同创始人 约翰·罗梅洛 John Romero 指出，这篇论文是卡马克在《毁灭战士》中引入 BSP 树时读到的论文之一。 [4] 《毁灭战士》中的 BSP 树别忘了，卡马克首次为《毁灭战士》设计渲染器时，通过让渲染器渲染玩家所在房间之外的临近房间，试图为关卡几何图形建立一套渲染顺序。对此，BSP 树是个不错的选择，因为在玩家进入之前的房间（区域）时，BSP 树能够避免让渲染器重复劳动，从而节省 CPU 资源。实际上，“将 BSP 树引入《毁灭战士》”意味着将 BSP 树生成器引入《毁灭战士》的关卡编辑器中。当完成一个《毁灭战士》的关卡的制作时，BSP 树就会在关卡几何图形的基础上生成。根据程序员 法比安·桑格勒德 Fabien Sanglard 的说法，在原版《毁灭战士》中，一个关卡的 BSP 树生成时间需要 8 秒，全部关卡合计共需 11 分钟 [5] 。之所以生成时间较长，部分原因在于卡马克所用的 BSP 生成算法，该算法尝试使用各种启发式方法找出 “高质量” BSP 树。在运行时，8 秒的延时可能让人无法接受；但是离线等 8 秒，时间并不算长，尤其是考虑到 BSP 树提升了渲染器的性能。为每个关卡生成的 BSP 树将在游戏启动时作为关卡数据载入。卡马克对 1980 年论文中提出的 BSP 树算法进行了改造，因为在《毁灭战士》开始运行时，当前关卡的 BSP 树就会读取到内存中，渲染器通过 BSP 树由前向后绘制物体，而非由后向前进行绘制。福克斯三人在那篇论文中演示了 BSP 树可用于执行由后向前的画家算法，但是画家算法会造成许多重复的绘制任务，对于 IBM 兼容机来说负担较大。因此，《毁灭战士》的渲染器换了个方向，首先绘制距离玩家较近的图形，之后再绘制离玩家较远的。这种反向排序很容易通过 BSP 树来实现，因为你可以在树的每个节点都进行反向遍历。为了避免绘制出来的远处图形遮挡到近处的图形，《毁灭战士》的渲染器使用了一种隐式 Z 缓冲区，这种缓冲区不仅具备普通 Z 缓冲区的优势，而且对内存的要求也较低。这种 Z 缓冲区有两组数组，一组记录水平方向的遮挡关系，另两组记录自屏幕顶部和底部的垂直方向的遮挡关系。《毁灭战士》的渲染器就算不使用实际的 Z 缓冲区也无伤大雅，因为从技术上来看它并不是真正的 3D 游戏。BSP 树数据结构的成本虽然不高，但却能够起作用，其原因在于《毁灭战士》不会发生以下问题：水平方向的遮挡数组能够发挥作用，是因为该游戏中没有倾斜的墙体；垂直方向的遮挡数组能够发挥作用，是因为该游戏不存在有着一上一下两扇窗户的墙体。剩下比较棘手的问题是如何将《毁灭战士》中处于运动中的角色融入到借助 BSP 树绘制的静止的关卡几何图形中。该游戏中的敌人不可能纳入 BSP 树之中，因为他们会移动，而 BSP 树只对静止的几何形状起作用。所以渲染器首先绘制静止的关卡几何图形，同时与另一个内存使用效率较高的数据结构协作，记录屏幕上分割出来用于绘制的区域。之后，渲染器按照由后往前的顺序绘制敌人，并消除被屏幕上的区域遮挡住的敌人。这一过程与使用 BSP 树进行渲染相比，效果稍差一些。但是由于关卡中能看到的敌人的数量少于几何图形的数量，所以速度并不是一个严重的问题。将 BSP 树应用到《毁灭战士》中可谓一大成功。卡马克能够想到 BSP 树是解决 VSD 问题的最佳方案，无疑非常高明。但是这可以称得上是天才之举吗？桑格勒德在其关于《毁灭战士》游戏引擎的书中引用了罗梅洛的话：内勒的论文《构建高质量的分割树》主要讲述使用 BSP 树消除 3D 模型的背面。 [6] 根据罗梅洛所言，卡马克认为这种算法对《毁灭战士》依然有效，所以他放手一试，将 BSP 技术应用到了该游戏中。不过这话说得有些奉承的意味 —— 意在暗示卡马克在别人仍然使用 BSP 树渲染静止的场景时，发现该技术可以用于实时游戏领域。在《Doom 启示录》中也有给卡马克戴高帽的故事。该书作者库什纳认为，卡马克在阅读内勒的论文之后，问了自己，“如果使用 BSP 技术创造一整个虚拟世界，而不仅仅是一张 3D 图像，会怎么样呢？” [7] 。这些“片面之词”忽视了 BSP 树的发展历史。当美国空军研究人员开始意识到场景分割可能会加快渲染任务的时候，他们就对提升 实时 渲染的速度产生了兴趣，毕竟他们当时试图创建一个飞行模拟器。1980 年，同样的案例再次出现在了福克斯等人的论文中，他们探讨了 BSP 树如何应用于飞行模拟器中，帮助飞行员进行训练：飞行员用它来反复练习将飞机降至同一空港。由于空港的地形不会发生改变，BSP 树只需生成一次，即可一劳永逸。很明显，他们考虑的是实时模拟。在论文的引言部分，福克斯等人还谈到实时图形系统必须在至少 1/30 秒内生成一张图像，由此激励了他们的研究。因此，卡马克不是第一个想到在实时图形模拟中应用 BSP 树的人。诚然，设想与付诸实践是两码事。但是即使在实施的过程中，卡马克受到的帮助与指导可比人们想象的要多得多。至少是到这篇文章写成之时，BSP 树的 维基百科词条 页面显示，卡马克参考了 1991 年 陈 Chen 和 戈登 Gordon 的一篇论文，以及 1990 年的一本教材《计算机图形学：原理及实践》。尽管该页面并未提供引用信息，但可信度没什么问题。陈和戈登的论文介绍了运用 BSP 树由前向后的渲染方法，这种方法与《毁灭战士》中用到的方法基本一致，还包括了我称之为“隐式 Z 缓冲区”的数据结构，可用于防止远处的图形在绘制时遮挡近处的图形。《计算机图形学：原理及实践》详细介绍了 BSP 树，以及一些构建并展示 BSP 树的伪代码（非常感谢我大学的图书馆，让我能够一睹这本教材 1990 年的版本）。因为这本书是计算机图形学的经典之作，所以卡马克很可能也有一本。然而，卡马克发现自己遇到一个新问题：如何让第一人称射击游戏在一台 CPU 甚至都无法进行浮点操作的电脑上运行呢？通过调查研究，他证明了 BSP 树的数据结构非常适用于实时电子游戏渲染。尽管 BSP 树早已提出，而且到了卡马克的时代，相关理论已经非常成熟了，但我始终认为，卡马克的做法可谓惊人之壮举。也许，得到人们称誉的应该是整个《毁灭战士》的游戏引擎，它的确非常精致。我在前文也提及过，但是桑格勒德的《 游戏引擎黑皮书：毁灭战士 Game Engine Black Book: DOOM 》 很好地讲解了这款游戏引擎的非凡之处，以及这些优势相互契合之法。要明白，VSD 问题只是卡马克在编写《毁灭战士》游戏引擎时需要解决的诸多问题之一。不得不说，面对不为大多数程序员所知的复杂的数据结构，卡马克能够查阅相关文献，将其付诸实践，仅此一点就足以说明其技术之精湛、匠心之独到。如果你喜欢这篇文章，欢迎关注推特 @TwoBitHistory，也可通过 RSS feed 订阅，获取最新文章（每四周更新一篇）。Michael Abrash, “Michael Abrash’s Graphics Programming Black Book,” James Gregory, accessed November 6, 2019, http://www.jagregory.com/abrash-black-book/#chapter-64-quakes-visible-surface-determination. ↩︎R. Schumacher, B. Brand, M. Gilliland, W. Sharp, “Study for Applying Computer-Generated Images to Visual Simulation,” Air Force Human Resources Laboratory, December 1969, accessed on November 6, 2019, https://apps.dtic.mil/dtic/tr/fulltext/u2/700375.pdf. ↩︎Henry Fuchs, Zvi Kedem, Bruce Naylor, “On Visible Surface Generation By A Priori Tree Structures,” ACM SIGGRAPH Computer Graphics, July 1980. ↩︎Fabien Sanglard, Game Engine Black Book: DOOM (CreateSpace Independent Publishing Platform, 2018), 200. ↩︎Sanglard, 206. ↩︎Sanglard, 200. ↩︎David Kushner, Masters of Doom (Random House Trade Paperbacks, 2004), 142. ↩︎via: https://twobithistory.org/2019/11/06/doom-bsp.html作者：Two-Bit History 选题：lujun9972 译者：aREversez 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
硬核观察 #731 无处不在的 DOOM，这次是拖拉机
无处不在的 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 下运行？
埃隆·马斯克开源推特算法的计划存在缺陷
报道称，在推特确认接受收购请求的几个小时后，埃隆·马斯克就明确表示了他对推特的期望。马斯克在一份新闻稿中罗列了他计划做出的重大改变，包括开源“决定用户在推流中看到什么”的算法。马斯克希望开源推特的算法，是因为他长期以来一直担心该平台有可能进行政治压制。但老实说，即便开源，也不可能达到他的预期效果。专家们担心，这可能反而带来一连串意想不到的问题。虽然马斯克对权威深恶痛绝，但是他对算法开源的野心和世界各地立法者的愿望不谋而合。近年来，许多政府都将这一原则作为打击大科技公司的基石。英国社交媒体监管机构 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 域和应用凭证
微软 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 》提出的问题是：“我们可以反过来吗”——我们可以通过学习计算机科学解决问题的方式来帮助我们做出日常决定吗？本书的十一个章节有很多有趣的内容，但也有一个有趣的主题：人类早已擅长这一点。很多章节以一个算法研究和对问题的数学分析作为开始，接着深入到探讨如何利用这些结果做出更好的决策，然后讨论关于人类真正会做出的决定的研究，之后，考虑到典型生活情境的限制，会发现人类早就在应用我们提出的最佳算法的特殊版本了。这往往会破坏本书的既定目标，值得庆幸的是，它决不会破坏对一般问题的有趣讨论，即计算机科学如何解决它们，以及我们对这些问题的数学和技术形态的了解。我认为这本书的自助效用比作者打算的少一些，但有很多可供思考的东西。（也就是说，值得考虑这种一致性是否太少了，因为人类已经擅长这方面了，更因为我们的算法是根据人类直觉设计的。可能我们的最佳算法只是反映了人类的思想。在某些情况下，我们发现我们的方案和数学上的典范不一样，但是在另一些情况下，它们仍然是我们当下最好的猜想。)这是那种章节列表是书评里重要部分的书。这里讨论的算法领域有最优停止、探索和利用决策（什么时候带着你发现的最好东西走，以及什么时候寻觅更好的东西），以及排序、缓存、调度、贝叶斯定理（一般还有预测）、创建模型时的过拟合、放松（解决容易的问题而不是你的实际问题）、随机算法、一系列网络算法，最后还有游戏理论。其中每一项都有有用的见解和发人深省的讨论——这些有时显得十分理论化的概念令人吃惊地很好地映射到了日常生活。这本书以一段关于“可计算的善意”的讨论结束：鼓励减少你自己和你交往的人所需的计算和复杂性惩罚。如果你有计算机科学背景（就像我一样），其中许多都是熟悉的概念，而且你因为被普及了很多新东西或许会有疑惑。然而，请给这本书一个机会，类比法没你担忧的那么令人紧张。作者既小心又聪明地应用了这些原则。这本书令人惊喜地通过了一个重要的合理性检查：涉及到我知道或反复思考过的主题的章节很少有或没有明显的错误，而且能讲出有用和重要的事情。比如，调度的那一章节毫不令人吃惊地和时间管理有关，通过直接跳到时间管理问题的核心而胜过了半数的时间管理类书籍：如果你要做一个清单上的所有事情，你做这些事情的顺序很少要紧，所以最难的调度问题是决定不做哪些事情而不是做这些事情的顺序。作者在贝叶斯定理这一章节中的观点完全赢得了我的心。本章的许多内容都是关于贝叶斯先验的，以及一个人对过去事件的了解为什么对分析未来的概率很重要。作者接着讨论了著名的棉花糖实验。即给了儿童一个棉花糖以后，儿童被研究者告知如果他们能够克制自己不吃这个棉花糖，等到研究者回来时，会给他们两个棉花糖。克制自己不吃棉花糖（在心理学文献中叫作“延迟满足”）被发现与未来几年更好的生活有关。这个实验多年来一直被引用和滥用于各种各样的宣传，关于选择未来的收益放弃即时的快乐从而拥有成功的生活，以及生活中的失败是因为无法延迟满足。更多的邪恶分析（当然）将这种能力与种族联系在一起，带有可想而知的种族主义结论。我对棉花糖实验有点兴趣。这是一个百分百让我愤怒咆哮的话题。《算法之美》是我读过的唯一提到了棉花糖实验并应用了我认为更有说服力的分析的书。这不是一个关于儿童天赋的实验，这是一个关于他们的贝叶斯先验的实验。什么时候立即吃棉花糖而不是等待奖励是完全合理的？当他们过去的经历告诉他们成年人不可靠，不可信任，会在不可预测的时间内消失并且撒谎的时候。而且，更好的是，作者用我之前没有听说过的后续研究和观察支持了这一分析，观察到的内容是，一些孩子会等待一段时间然后“放弃”。如果他们下意识地使用具有较差先验的贝叶斯模型，这就完全合情合理。这是一本很好的书。它可能在某些地方的尝试有点太勉强（数学上最优停止对于日常生活的适用性比我认为作者想要表现的更加偶然和牵强附会），如果你学过算法，其中一些内容会感到熟悉，但是它的行文思路清晰，简洁，而且编辑得非常好。这本书没有哪一部分对不起它所受到的欢迎，书中的讨论贯穿始终。如果你发现自己“已经知道了这一切”，你可能还会在接下来几页中遇到一个新的概念或一个简洁的解释。有时作者会做一些我从没想到但是回想起来正确的联系，比如将网络协议中的指数退避和司法系统中的选择惩罚联系起来。还有意识到我们的现代通信世界并不是一直联系的，它是不断缓冲的，我们中的许多人正深受缓冲膨胀这一独特现象的苦恼。我认为你并不必须是计算机科学专业或者精通数学才能读这本书。如果你想深入，每章的结尾都有许多数学上的细节，但是正文总是易读而清晰，至少就我所知是这样（作为一个以计算机科学为专业并学到了很多数学知识的人，你至少可以有保留地相信我）。即使你已经钻研了多年的算法，这本书仍然可以提供很多东西。这本书我读得越多越喜欢。如果你喜欢阅读这种对生活的分析，我当然是赞成的。Rating: 9 out of 10Reviewed: 2017-10-22via: https://www.eyrie.org/~eagle/reviews/books/1-62779-037-3.html作者：Brian Christian;Tom Griffiths 译者：GraveAccent 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
用数据科学搭建一个实时推荐引擎
编者注：本文是 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 product ） 和他们共同“喜好”的地点来进行匹配。当我们使用 WHERE id(u1) < id(u2) 作为 Cypher 询问的一部分时，它只是来确定我们在左边和右边没有找到相同的对的一个技巧。通过用户之间的欧几里得距离，我们创建了他们之间的一种关系，叫做 :DISTANCE，并且设置了一个叫做 euclidean 的欧几里得属性。理论上，我们可以也通过用户间的一些关系来存储其他相似度从而获取不同的相似度，因为在确定的环境下某些相似度可能比其他相似度更有用。在 Neo4j 中，的确是对关系属性建模的能力使得完成像这样的事情无比简单。然而，实际上，你不会希望存储每一个可能存在的单一关系，因为你仅仅希望返回离他们“最近”的一些人。因此你可以根据一些临界值来存入前几个，从而你不需要构建完整的连通图。这允许你完成一些像下面这样的实时的数据库查询，因为我们已经预先计算好了“距离”并存储在了关系中，在 Cypher 中，我们能够很快的攫取出数据。在这个查询中，我们依据地点和类别来进行匹配：再次说明，前三行是相同的，除了登录用户以外，我们找出了和他们有 :DISTANCE 关系的用户。这是我们前面查看的关系产生的作用 - 实际上，你只需要存储处于前几位的相似用户 :DISTANCE 关系，因此你不需要在 MATCH 子句中攫取大量用户。相反，我们只攫取和那些用户“喜好”的地方有 :DISTANCE 关系的用户。这允许我们用少许几行内容表达较为复杂的模型。我们也可以攫取 :LIKES 关系并把它放入到变量中，因为后面我们将使用这些权重来评分。在这儿重要的是，我们可以依据“距离”大小将用户按照升序进行排序，因为这是一个距离测度。同时，我们想要找到用户间的最小距离因为距离越小表明他们的相似度最大。通过其他按照欧几里得距离大小排序好的用户，我们得到用户评分最高的三个地点并按照用户的平均评分高低来推荐这些地点。换句话说，我们先找出一个活跃用户，然后依据其他用户“喜好”的地点找出和他最相似的其他用户，接下来按照这些相似用户的平均评分把那些地点排序在结果的集合中。本质上，我们通过把所有评分相加然后除以收集的用户数目来计算出平均分，然后按照平均评分的升序进行排序。其次，我们按照出入口距离排序。假想地，我猜测应该会有交接点，因此你可以按照出入口距离排序然后再返回名字、类别、出入口和航站楼。 集群推荐 （ Cluster Recommendations ） 我们最后要讲的一个例子是集群推荐，在 Cypher 中，这可以被想像成一个作为临时解决方案的离线计算工作流。这可能完全基于在欧洲 GraphConnect 上宣布的新方法，但是有时你必须进行一些 Cypher 2.3 版本所没有的算法逼近。在这儿你可以使用一些统计软件，把数据从 Neo4j 取出然后放入像 Apache Spark、R 或者 Python 这样的软件中。下面是一段把数据从 Neo4j 中取出的 R 代码，运行该程序，如果正确，写下程序返回结果的给 Neo4j，可以是一个属性、节点、关系或者一个新的标签。通过持续把程序运行结果放入到图表中，你可以在一个和我们刚刚看到的查询相似的实时查询中使用它：下面是用 R 来完成这件事的一些示例代码，但是你可以使用任何你最喜欢的软件来做这件事，比如 Python 或 Spark。你需要做的只是登录并连接到图表。在下面的例子中，我基于用户的相似性把他们聚合起来。每个用户作为一个观察点，然后得到他们对每一个目录评分的平均值。假定用户对酒吧类评分的方式和一般的评分方式相似。然后我攫取出喜欢相同类别中的地点的用户名、类别名、“喜好”关系的平均权重，比如平均权重这些信息，从而我可以得到下面这样一个表格：因为我们把每一个用户都作为一个观察点，所以我们必须巧妙的处理每一个类别中的数据，这些数据的每一个特性都是用户对该类中餐厅评分的平均权重。接下来，我们将使用这些数据来确定用户的相似性，然后我将使用 聚类 （ clustering ） 算法来确定在不同集群中的用户。在 R 中这很直接：在这个示例中我们使用 K-均值 （ k-means ） 聚类算法，这将使你很容易攫取集群分配。总之，我通过运行聚类算法然后分别得到每一个用户的集群分配。Bob 和 David 在一个相同的集群中 - 他们在集群二中 - 现在我可以实时查看哪些用户被放在了相同的集群中。接下来我把集群分配写入 CSV 文件中，然后存入图数据库：我们只有用户和集群分配，因此 CSV 文件只有两列。 LOAD CSV 是 Cypher 中的内建语法，它允许你从一些其他文件路径或者 URL 调用 CSV ，并给它一个别名。接下来，我们将匹配图数据库中存在的用户，从 CSV 文件中攫取用户列然后合并到集群中。我们在图表中创建了一个新的标签节点：Cluster ID， 这是由 K-平均聚类算法给出的。接下来我们创建用户和集群间的关系，通过创建这个关系，当我们想要找到在相同集群中的实际推荐用户时，就会很容易进行查询。我们现在有了一个新的集群标签，在相同集群中的用户和那个集群存在关系。新的数据模型看起来像下面这样，它比我们前面探索的其他数据模型要更好：现在让我们考虑下面的查询：通过这个 Cypher 查询，我们在更远处找到了在同一个集群中的相似用户。由于这个原因，我们删除了“距离”关系：在这个查询中，我们取出已经登录的用户，根据用户-集群关系找到他们所在的集群，找到他们附近和他们在相同集群中的用户。我们把这些用户分配到变量 c1 中，然后我们得到其他被我取别名为 neighbor 变量的用户，这些用户和那个相同集群存在着用户-集群关系，最后我们得到这些附近用户“喜好”的地点。再次说明，我把“喜好”放入了变量 r 中，因为我们需要从关系中攫取权重来对结果进行排序。在这个查询中，我们所做的改变是，不使用相似性距离，而是攫取在相同集群中的用户，然后对类别、航站楼以及我们所攫取的登录用户进行声明。我们收集所有的权重：来自附近用户“喜好”地点的“喜好”关系，得到的类别，确定的距离值，然后把它们按升序进行排序并返回结果。在这些例子中，我们可以进行一个相当复杂的处理并且将其放到图数据库中，然后我们就可以使用实时算法结果-聚类算法和集群分配的结果。我们更喜欢的工作流程是更新这些集群分配，更新频率适合你自己就可以，比如每晚一次或每小时一次。当然，你可以根据直觉来决定多久更新一次这些集群分配是可接受的。via: https://neo4j.com/blog/real-time-recommendation-engine-data-science/作者：Nicole White 译者：ucasFL 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
每个程序员都应该收藏的算法复杂度速查表
算法复杂度这件事这篇文章覆盖了计算机科学里面常见算法的时间和空间的 大 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 复杂度图表推荐阅读Cracking the Coding Interview: 150 Programming Questions and SolutionsIntroduction to Algorithms, 3rd EditionData Structures and Algorithms in Java (2nd Edition)High Performance JavaScript (Build Faster Web Application Interfaces)贡献者Eric Rowell, creator of Concrete.js, an HTML5 Canvas FrameworkQuentin PlepleMichael AbedNick DizazzoAdam ForsythDavid DorfmanJay EngineerJennifer HamonJosh DavisNodir TurakulovBart MasseyVinnie MagroMiguel AmigotDrew BaileyAneel NazarethRahul ChowdhuryRobert Burkesteven41292Brandon AmosMike DavisCasper Van GheluweJoel FriedlyOlegRenfred HarperPiper ChesterEric Lefevre-ArdantJonathan McElroySi PhammcverryMax HoffmannAlejandro RamirezDamon DavisonAlvin WanAlan BriolatDrew HannayAndrew RasmussenDennis TsangBahador Saket