计算机科学第三难题将通用图映射到层次结构“树映射”问题无处不在根据一个归属于 菲尔·卡尔顿 的 经典笑话计算机科学只有两个难题命名和缓存失效。这两个问题之所以难是因为没有算法可以解决它们好的命名源于同理心和理解力而缓存失效则需要系统思维和仔细分析。本文将介绍另一个这样的问题它普遍且隐蔽但很少被注意到将通用图映射到层次结构上。我将其称为“树映射”。空间、树与网络人类大脑在进化过程中变得非常善于处理物理空间。我们能在陌生城市中凭直觉找到方向还能准确画出几十年前去过地方的地图。自然地我们希望在生活的方方面面都利用这种能力。物理空间有个显著特征就是其层次化、局部化的结构。我们把每一块空间看成独立个体且仅与相邻空间相互作用这让我们能以层次化视角看待世界其中物体形成可作为整体理解的集合粒子构成原子原子构成分子分子构成物体以此类推直至星系和超星系团。层次结构对我们来说很自然成了主要的组织工具。我们把事物和想法分类放进有标签的盒子再把这些盒子放入更大的盒子。这种方法适用于同一时间只能处于一个位置的物理对象。然而想法和信息却难以用分类法来处理。它们形成了错综复杂的“网络”突破了严格的界限。树 让层次结构形式化是计算机科学中使用最广泛的结构之一。树与空间密切相关因为它们是通用的空间组织者B 树用于组织数据库中的有序键空间k - d 树 用于在图形中划分多维空间抽象语法树用于在编译器中组织线性标记序列。⊕ 解析是一个空间组织问题因为它需要为标记序列标记其句法角色。尽管树有很多用途但它们无法直接对网络进行建模。所以“树映射”是一个需要以某种方式将网络嵌入树中从而扭曲网络结构的问题。下面来看几个例子。文件系统数字世界让我们能够超越现实世界排序的最基本规则与其让每个事物都有固定的位置不如让事物能同时被分配到多个位置。—— 大卫·温伯格《万物皆混杂》想象你收到牙医的账单你会怎么归档它呢是放在常见的“存档”文件夹中还是更具体的“医疗”文件夹里亦或是放在“XXXX 年税务”项目文件夹中以备将来报税使用还是将其复制并同时选择所有选项呢在 Dropbox 和 Google Drive 时代这个问题似乎无关紧要。然而维多利亚时代的绅士在整理信件时可能也会思考与我们整理虚拟文件时相同的问题。我们最先进的分布式系统的用户界面设计继承了物理世界的大部分限制。操作系统也面临同样的困境文件应该按所属应用程序还是按类型组织呢Windows 和 macOS 传统上倾向于前者将应用程序打包成大多自包含的捆绑包。而大多数 Linux 系统则采用后者因此当你安装一个软件包时其各个部分会分散在整个文件系统中库文件放在 /usr/lib文档放在 /usr/man配置文件放在 /etc/ 等等。这种选择存在权衡拆分软件包简化了工具使用man 命令只需在少数几个位置查找并实现了重用但却使软件管理变得复杂。在 Linux 上打包和安装现代应用程序的痛苦促使了受 macOS 启发的捆绑包格式的发展如 Snap 和 Flatpak。如果你曾尝试组织一个非平凡的代码仓库可能也会遇到同样的问题。现代项目的组件可能使用不同的语言实现例如前端使用 TypeScript后端使用 Rust。你可以按组件组织文件/acme/payments/index.ts 和 /acme/payments/main.rs也可以按语言组织acme/ts/payments.ts 和 /acme/rs/payments.rs。⊕ 组织代码仓库的两种常见方式按组件左或按实现语言右。按组件组织对人类来说更容易因为它 反映了组织结构但大多数工具不支持这种设置因此不得不采用以技术为中心的方法。谷歌和其他一些工程组织迎难而上按项目组织他们的仓库/search、/shopping、/maps并开发了大量与语言无关的构建工具。谷歌的 Blaze 是最早的此类工具之一它启发了 Pants、Buck 和 Please后来以 Bazel 的形式开源。然而这些困境大多是我们自己造成的。数字文件系统没有理由必须是装满文件夹的架子的仿制品。有几个项目曾尝试开发类似网络的文件系统例如 BeFS 和 WinFS但都对现状没有产生重大影响。不过随着标签和链接通过网络服务进入大众视野文件系统可能会跟随这一趋势逐渐演变成网络。写作作家的目标是用短语树将想法网络编码成一串文字。—— 史蒂芬·平克《写作风格的意识》书籍是层次结构的典型代表它们有章节章节包含段落段落由句子组成句子由单词构成单词由字母组成所有内容都整齐地划分在编号的页面中。然而我们在这些页面上表达的想法绝非线性或层次化的。许多故事看似线性讲故事的人按事件发生的顺序描述事件章节边界标志着场景变化和时间跳跃。但每个故事背后都隐藏着一个想法网络。将这个网络拆解成一串文字在另一个人的脑海中重建这个网络是每个作家的首要挑战。写作很简单。你所要做的就是盯着一张白纸直到额头滴出血来。—— 吉恩·福勒在小说中“网络”涉及角色之间的关系以及读者与角色之间应形成的情感联系。优秀的小说会利用这种媒介的局限性以最能让读者困惑和投入的顺序呈现事件。其最终目标是让读者体验到将各个点连接起来、拼凑出完整网络的乐趣。然而当底层网络变得密集且抽象时作家的工作就变得艰巨读者的阅读也会变得困难。数学教科书就是一个很好的例子。数学可能看起来像一座乐高积木塔基础是简单的概念复杂性逐渐向上增加。实际上从欧几里得的 《几何原本》 开始每一个连贯的数学呈现都遵循这种模式。然而基础概念的选择往往是任意的。随着你了解数学概念与其他一切的关系它们的形态会发生变化并变得更加微妙我记得在完成 实分析 课程几个月后醒来意识到自己终于 理解 了极限这要归功于当时正在学习的 常微分方程 课程。甚至我对自然数的理解似乎也会随着阅读的每一本教科书而改变。想法的选择和呈现顺序会影响读者的体验因此没有两本数学书的目录是相同的。下次当你面对一份空白的设计文档不知道从何开始时请善待自己。你正在解决一个难题。建筑人造城市的组成单元总是被组织成树状结构。—— 克里斯托弗·亚历山大《城市不是树》⊕ 莱维敦左公共领域来源维基百科和锡耶纳右版权归 维亚切斯拉夫·阿尔根伯格 所有遵循 CC BY 4.0 许可的全景图。在 1965 年的论文 《城市不是树》 中建筑师兼数学家克里斯托弗·亚历山大观察到了设计城市和自然发展城市之间的区别他将莱维敦和昌迪加尔归为设计城市将锡耶纳和京都归为自然发展城市。他认为人造城市感觉压抑缺乏赋予自然城市生机和舒适感的神秘元素。克里斯托弗·亚历山大认为这种差异在于城市设计背后的数学结构。人造城市被组织成树状结构它们由孤立的社区组成每个社区都有一个住宅区、一所学校和一个购物中心还有一些分区化的特殊区域如文化中心和工业区。而自然发展的城市具有 半格 结构这使得更丰富的互动得以出现。在自然城市中生活各方面的界限是模糊的。工作、休闲和娱乐相互交融、相互影响。城市设计是一个树映射问题需要将人类关系的半格嵌入特定的地形中。由于不存在规范的映射所以克里斯托弗·亚历山大无法为自然城市提供通用蓝图也就不足为奇了。你现在无疑想知道一个是半格但不是树的城市是什么样子。我必须承认我还无法向你展示规划图或草图。仅仅展示重叠是不够的 —— 这种重叠必须是恰当的重叠。—— 克里斯托弗·亚历山大《城市不是树》换句话说自然城市在将人类生活的网络布局在街区和建筑的层次结构中时保留了更深层次的联系。没有算法能告诉你这些联系是什么。生物学生物分类学 是对生物进行分类的领域。它始于形态分类学该分类学基于容易观察到的特征例如动物是否有脊椎或是否用乳汁喂养后代。这种方法容易出错因为有用的特征往往在生命之树的遥远分支中 独立进化。例如头足类动物的眼睛 与脊椎动物的眼睛惊人地相似尽管它们的共同祖先可能类似于一只带有感光点的盲虫。如果 相机式眼睛 定义了一个生物群体那么其成员将是一个奇怪的组合。历史上有许多实际的错误分类。直到 20 世纪中叶真菌才被赋予独立的界在此之前它们被归类为植物。鳄鱼和鸟类曾经属于兄弟类 _爬行纲_ 和 _鸟纲_ 尽管鳄鱼与鸟类的关系比与其他爬行动物的关系更密切。形态分类学是树映射的另一个例子因为特征集合形成 概念它们的包含关系形成比树更通用的图格。豪尔赫·路易斯·博尔赫斯在他的论文 《约翰·威尔金斯的分析语言》 中嘲笑了这种分类法他引用了一本虚构的中国古代百科全书《仁慈知识的天国宝库》动物被分为(a) 属于皇帝的(b) 制成木乃伊的(c) 经过训练的(d) 小猪(e) 塞壬(f) 神话中的(g) 流浪狗(h) 包含在这个分类中的(i) 疯狂颤抖的(j) 无数的(k) 用非常细的骆驼毛笔画的(l) 等等(m) 刚刚打破花瓶的(n) 从远处看像苍蝇的—— 豪尔赫·路易斯·博尔赫斯《约翰·威尔金斯的分析语言》分支分类学 是一种现代系统它根据生物的共同祖先和遗传学对生物进行分类。尽管由于 水平基因转移这种映射并不完美但它比传统分类更准确、更有启发性因为它保留了现有的联系而不是强加人为的联系。总结现在你已经了解了这个问题以后就会很容易在各处发现它。它隐藏在数据库建模挑战中我在说你呢MongoDB使面向对象的类层次结构陷入困境也是 Rust 借用检查器难以处理的根源对象所有权图是树但对象交互是网络。它还决定了你 node_modules 目录的大小和食谱的布局。处理树映射问题的主要策略是要有意识。我们本能地倾向于使用层次结构而且常常没有意识到自己在做选择。我们必须停下来问自己正在被扁平化的是什么网络哪些链接被牺牲了最重要的是目标媒介一开始就必须是树吗相关文章像费曼一样调试像法拉第一样测试 2022 - 04 - 01好的命名形成伽罗瓦连接 2024 - 04 - 01如果作曲家是黑客 2023 - 04 - 01编译即交流 2025 - 10 - 13基于标签的日志记录 2025 - 08 - 19
计算机科学第三难题：“树映射”问题在文件、写作、建筑、生物分类中无处不在！
计算机科学第三难题将通用图映射到层次结构“树映射”问题无处不在根据一个归属于 菲尔·卡尔顿 的 经典笑话计算机科学只有两个难题命名和缓存失效。这两个问题之所以难是因为没有算法可以解决它们好的命名源于同理心和理解力而缓存失效则需要系统思维和仔细分析。本文将介绍另一个这样的问题它普遍且隐蔽但很少被注意到将通用图映射到层次结构上。我将其称为“树映射”。空间、树与网络人类大脑在进化过程中变得非常善于处理物理空间。我们能在陌生城市中凭直觉找到方向还能准确画出几十年前去过地方的地图。自然地我们希望在生活的方方面面都利用这种能力。物理空间有个显著特征就是其层次化、局部化的结构。我们把每一块空间看成独立个体且仅与相邻空间相互作用这让我们能以层次化视角看待世界其中物体形成可作为整体理解的集合粒子构成原子原子构成分子分子构成物体以此类推直至星系和超星系团。层次结构对我们来说很自然成了主要的组织工具。我们把事物和想法分类放进有标签的盒子再把这些盒子放入更大的盒子。这种方法适用于同一时间只能处于一个位置的物理对象。然而想法和信息却难以用分类法来处理。它们形成了错综复杂的“网络”突破了严格的界限。树 让层次结构形式化是计算机科学中使用最广泛的结构之一。树与空间密切相关因为它们是通用的空间组织者B 树用于组织数据库中的有序键空间k - d 树 用于在图形中划分多维空间抽象语法树用于在编译器中组织线性标记序列。⊕ 解析是一个空间组织问题因为它需要为标记序列标记其句法角色。尽管树有很多用途但它们无法直接对网络进行建模。所以“树映射”是一个需要以某种方式将网络嵌入树中从而扭曲网络结构的问题。下面来看几个例子。文件系统数字世界让我们能够超越现实世界排序的最基本规则与其让每个事物都有固定的位置不如让事物能同时被分配到多个位置。—— 大卫·温伯格《万物皆混杂》想象你收到牙医的账单你会怎么归档它呢是放在常见的“存档”文件夹中还是更具体的“医疗”文件夹里亦或是放在“XXXX 年税务”项目文件夹中以备将来报税使用还是将其复制并同时选择所有选项呢在 Dropbox 和 Google Drive 时代这个问题似乎无关紧要。然而维多利亚时代的绅士在整理信件时可能也会思考与我们整理虚拟文件时相同的问题。我们最先进的分布式系统的用户界面设计继承了物理世界的大部分限制。操作系统也面临同样的困境文件应该按所属应用程序还是按类型组织呢Windows 和 macOS 传统上倾向于前者将应用程序打包成大多自包含的捆绑包。而大多数 Linux 系统则采用后者因此当你安装一个软件包时其各个部分会分散在整个文件系统中库文件放在 /usr/lib文档放在 /usr/man配置文件放在 /etc/ 等等。这种选择存在权衡拆分软件包简化了工具使用man 命令只需在少数几个位置查找并实现了重用但却使软件管理变得复杂。在 Linux 上打包和安装现代应用程序的痛苦促使了受 macOS 启发的捆绑包格式的发展如 Snap 和 Flatpak。如果你曾尝试组织一个非平凡的代码仓库可能也会遇到同样的问题。现代项目的组件可能使用不同的语言实现例如前端使用 TypeScript后端使用 Rust。你可以按组件组织文件/acme/payments/index.ts 和 /acme/payments/main.rs也可以按语言组织acme/ts/payments.ts 和 /acme/rs/payments.rs。⊕ 组织代码仓库的两种常见方式按组件左或按实现语言右。按组件组织对人类来说更容易因为它 反映了组织结构但大多数工具不支持这种设置因此不得不采用以技术为中心的方法。谷歌和其他一些工程组织迎难而上按项目组织他们的仓库/search、/shopping、/maps并开发了大量与语言无关的构建工具。谷歌的 Blaze 是最早的此类工具之一它启发了 Pants、Buck 和 Please后来以 Bazel 的形式开源。然而这些困境大多是我们自己造成的。数字文件系统没有理由必须是装满文件夹的架子的仿制品。有几个项目曾尝试开发类似网络的文件系统例如 BeFS 和 WinFS但都对现状没有产生重大影响。不过随着标签和链接通过网络服务进入大众视野文件系统可能会跟随这一趋势逐渐演变成网络。写作作家的目标是用短语树将想法网络编码成一串文字。—— 史蒂芬·平克《写作风格的意识》书籍是层次结构的典型代表它们有章节章节包含段落段落由句子组成句子由单词构成单词由字母组成所有内容都整齐地划分在编号的页面中。然而我们在这些页面上表达的想法绝非线性或层次化的。许多故事看似线性讲故事的人按事件发生的顺序描述事件章节边界标志着场景变化和时间跳跃。但每个故事背后都隐藏着一个想法网络。将这个网络拆解成一串文字在另一个人的脑海中重建这个网络是每个作家的首要挑战。写作很简单。你所要做的就是盯着一张白纸直到额头滴出血来。—— 吉恩·福勒在小说中“网络”涉及角色之间的关系以及读者与角色之间应形成的情感联系。优秀的小说会利用这种媒介的局限性以最能让读者困惑和投入的顺序呈现事件。其最终目标是让读者体验到将各个点连接起来、拼凑出完整网络的乐趣。然而当底层网络变得密集且抽象时作家的工作就变得艰巨读者的阅读也会变得困难。数学教科书就是一个很好的例子。数学可能看起来像一座乐高积木塔基础是简单的概念复杂性逐渐向上增加。实际上从欧几里得的 《几何原本》 开始每一个连贯的数学呈现都遵循这种模式。然而基础概念的选择往往是任意的。随着你了解数学概念与其他一切的关系它们的形态会发生变化并变得更加微妙我记得在完成 实分析 课程几个月后醒来意识到自己终于 理解 了极限这要归功于当时正在学习的 常微分方程 课程。甚至我对自然数的理解似乎也会随着阅读的每一本教科书而改变。想法的选择和呈现顺序会影响读者的体验因此没有两本数学书的目录是相同的。下次当你面对一份空白的设计文档不知道从何开始时请善待自己。你正在解决一个难题。建筑人造城市的组成单元总是被组织成树状结构。—— 克里斯托弗·亚历山大《城市不是树》⊕ 莱维敦左公共领域来源维基百科和锡耶纳右版权归 维亚切斯拉夫·阿尔根伯格 所有遵循 CC BY 4.0 许可的全景图。在 1965 年的论文 《城市不是树》 中建筑师兼数学家克里斯托弗·亚历山大观察到了设计城市和自然发展城市之间的区别他将莱维敦和昌迪加尔归为设计城市将锡耶纳和京都归为自然发展城市。他认为人造城市感觉压抑缺乏赋予自然城市生机和舒适感的神秘元素。克里斯托弗·亚历山大认为这种差异在于城市设计背后的数学结构。人造城市被组织成树状结构它们由孤立的社区组成每个社区都有一个住宅区、一所学校和一个购物中心还有一些分区化的特殊区域如文化中心和工业区。而自然发展的城市具有 半格 结构这使得更丰富的互动得以出现。在自然城市中生活各方面的界限是模糊的。工作、休闲和娱乐相互交融、相互影响。城市设计是一个树映射问题需要将人类关系的半格嵌入特定的地形中。由于不存在规范的映射所以克里斯托弗·亚历山大无法为自然城市提供通用蓝图也就不足为奇了。你现在无疑想知道一个是半格但不是树的城市是什么样子。我必须承认我还无法向你展示规划图或草图。仅仅展示重叠是不够的 —— 这种重叠必须是恰当的重叠。—— 克里斯托弗·亚历山大《城市不是树》换句话说自然城市在将人类生活的网络布局在街区和建筑的层次结构中时保留了更深层次的联系。没有算法能告诉你这些联系是什么。生物学生物分类学 是对生物进行分类的领域。它始于形态分类学该分类学基于容易观察到的特征例如动物是否有脊椎或是否用乳汁喂养后代。这种方法容易出错因为有用的特征往往在生命之树的遥远分支中 独立进化。例如头足类动物的眼睛 与脊椎动物的眼睛惊人地相似尽管它们的共同祖先可能类似于一只带有感光点的盲虫。如果 相机式眼睛 定义了一个生物群体那么其成员将是一个奇怪的组合。历史上有许多实际的错误分类。直到 20 世纪中叶真菌才被赋予独立的界在此之前它们被归类为植物。鳄鱼和鸟类曾经属于兄弟类 _爬行纲_ 和 _鸟纲_ 尽管鳄鱼与鸟类的关系比与其他爬行动物的关系更密切。形态分类学是树映射的另一个例子因为特征集合形成 概念它们的包含关系形成比树更通用的图格。豪尔赫·路易斯·博尔赫斯在他的论文 《约翰·威尔金斯的分析语言》 中嘲笑了这种分类法他引用了一本虚构的中国古代百科全书《仁慈知识的天国宝库》动物被分为(a) 属于皇帝的(b) 制成木乃伊的(c) 经过训练的(d) 小猪(e) 塞壬(f) 神话中的(g) 流浪狗(h) 包含在这个分类中的(i) 疯狂颤抖的(j) 无数的(k) 用非常细的骆驼毛笔画的(l) 等等(m) 刚刚打破花瓶的(n) 从远处看像苍蝇的—— 豪尔赫·路易斯·博尔赫斯《约翰·威尔金斯的分析语言》分支分类学 是一种现代系统它根据生物的共同祖先和遗传学对生物进行分类。尽管由于 水平基因转移这种映射并不完美但它比传统分类更准确、更有启发性因为它保留了现有的联系而不是强加人为的联系。总结现在你已经了解了这个问题以后就会很容易在各处发现它。它隐藏在数据库建模挑战中我在说你呢MongoDB使面向对象的类层次结构陷入困境也是 Rust 借用检查器难以处理的根源对象所有权图是树但对象交互是网络。它还决定了你 node_modules 目录的大小和食谱的布局。处理树映射问题的主要策略是要有意识。我们本能地倾向于使用层次结构而且常常没有意识到自己在做选择。我们必须停下来问自己正在被扁平化的是什么网络哪些链接被牺牲了最重要的是目标媒介一开始就必须是树吗相关文章像费曼一样调试像法拉第一样测试 2022 - 04 - 01好的命名形成伽罗瓦连接 2024 - 04 - 01如果作曲家是黑客 2023 - 04 - 01编译即交流 2025 - 10 - 13基于标签的日志记录 2025 - 08 - 19
