编程的小乐趣

计算机编程的小秘密之一是，它实际上很有趣。您会发现一些智力难题，难以解决，并在构建更大项目的途中得以解决。然后，您不必扔掉像星期六完成的Sudoku这样的难题解决方案，而可以将其塞入您的应用程序中，并随身携带各种技巧。

由于各种原因，我正在开发的应用有时需要能够获取一个人口普查区ID（一个15字符串），并将其映射到包含它的投票区的ID（一个9-12字符串）。 。人口普查部门发布此信息，并在其网站上免费提供。我们导入了此信息，并将其存储在您可能想到的最简单的JSON / JavaScript表示中—只是一个以块ID为键，而投票区ID为值的对象。进行映射所需的处理将加载JSON文件，然后仅使用该对象进行从键到值的映射。

这些文件是按州存储的，因此，最糟糕的情况是，德克萨斯州拥有将近一百万个人口普查块，当存储在磁盘上时，这种结构将近30兆字节。在内存中，它可以扩展到50 MB。 JSON（JavaScript对象表示法-一种获取JavaScript对象并将其作为字符串传递或存储在文件中的方法）可能非常罗word，因此有时在导入时它会变小，但在这种情况下，文件大多只是字符串，因此实际上解析并存储到内存后会扩展。

以前，需要这种映射功能的处理过程必须加载许多甚至更大的文件，因此尽管有很多问题，但它并不是最重要的问题。但是通常，其他一些更改和改进突然使我们关心的与此映射表相关的下载和处理成本。

现在再来看一下Texas，那个30 MB的JSON文件在压缩时实际上只有4 MB，这就是它的存储和传输方式。压缩是一种快速直观的方法，可让您直观了解某些数据块的“实际”信息内容。压缩形式可能不是最佳处理形式，但是它确实使您了解数据中有多少冗余。在这种情况下，会有大量的冗余。考虑内容时，这种冗余非常明显。每个投票区大约由65个人口普查区组成，因此每个值（9到12个字符的投票区ID）平均重复65次。区块ID实际上采用结构化的形式，其中前2个字符是州ID（对于按州组织的文件中的所有值来说都是相同的），接下来的3个字符是县ID，然后是人口普查区，人口普查区块组最后是单个块号。

考虑到所有这些冗余，在我看来，我们可能想出了一个更密集的数据结构，可以在这种密集表示形式中直接存储，传输，加载和使用它，而不必将其消耗在内存中。最近，我需要提高速度或减少内存使用量（通常是同一件事），从而确定不必要的JavaScript数据表示形式在哪里膨胀，而改为使用紧凑的二进制表示形式，因此成为我的JavaScript编程迷。也许是我的C / C ++根源。

在这种情况下，我要重点关注两个方面：如何存储值和如何存储键。因为我知道这些值平均重复了65次，所以一个简单的解决方案是保留所有唯一字符串的副本，并存储对唯一字符串的引用，而不是文字字符串（编译器和语言通常会在内部自动对某些字符串进行复制）程序的一部分）。我认为我可以做得更好，因为这些值还具有大量的内部冗余-许多值共享相同的第一部分，然后许多值具有相同的后几个区别字符。一个简单的解决方案是（动态地）将字符串分成两部分，并找到将字符串存储量最小化的拆分。这本质上是通用压缩算法所做的近似（查找公用共享序列，然后紧凑地引用它们）。

对于密钥，当密钥空间中有大量冗余时，trie是一个不错的选择。编写代码主要是关于设计如何将其打包为单个数据块，使用从缓冲区开始的偏移量而不是指针来遍历数据结构。通常，当您开始以棘手的方式使用内存时，需要进行一些测试和调试才能开始工作。

我对最终结果感到非常满意。该得克萨斯文件最终以2.7 MB的紧凑型缓冲区结尾，可以直接作为单个块加载到内存中，而无需进一步转换即可使用。用于存储和传输的压缩到不到1 MB（这表明我的解决方案还有更大的改进空间）。但是我在内存使用方面已经有了20倍的改进，在存储和传输方面也有了显着的改进，所以我就此止步。

这是一个有趣的小问题。它被很好地隔离并且易于描述，因此我不必花大量时间在陈旧的集成以及复杂的测试和部署问题上。我能够使用一生编程中的直觉，并且还需要一些谨慎的摆弄才能正确。然后它实际上起作用并解决了问题。

我要说的是，“紧凑型字典”的一般问题（这是特例）是一个经过充分研究的问题，我从头开始写东西有点内lt。当然有什么我可以抢购的东西吗？搜索没有找到任何东西，所以我有退休的优势。我可以抑制内感，并乐于解决问题。

我的第二个示例有些不同。在这种情况下，有趣的是学习新知识然后将其有效利用。

我试图解决三个问题，但结果却令人惊讶。我们应用程序的核心加载并显示投票区形状。投票区是根据基本的人口普查区形状创建的。存储和处理这些形状所需的内存最终会对我们的整体性能产生重大影响。

提高性能的最基本方法是采用人口普查部门提供的高分辨率形状，并通过删除点来简化形状。这对任何地方（在内存使用和处理的每个阶段）都有帮助，因此显而易见的是重点。这些额外的点在计算机屏幕上显示时不会产生视觉差异，也不会产生有效的改变，因为它们不会改变用户与应用程序的交互方式。基本的人口普查形状需要区分一所房子是在一个人口普查区中还是在另一个人口普查区中，但是出于我们的目的，由于在该分辨率下没有其他数据（人口普查和选举），因此近似估算效果很好。

第二个问题是如何将一组形状组合成单个形状，或更笼统地说是“多边形并集”。我们遇到这个问题的核心地方是采用一组投票区形状，并将它们组合成一个国会（或州立法）形状。多边形联合是计算机图形学中一个经过充分研究的问题，但是一般的解决方案既占用内存，又需要大量处理，并且当我们将开源解决方案集成到我们的应用程序中时，这对应用程序的交互性能造成了很大的负担。我必须在它之上构建一个复杂的异步工作切片机制，以防止它一次锁定我们的应用几秒钟。

第三个问题是如何确定两个形状是否连续。这是我们分析重新划分计划的核心。在我们的应用程序中，这发生在“脱机”状态以产生连续性图。它并不需要特别快，但是最初是通过与我们的核心工具集分离的一组工具解决的，因此我们有动力尝试统一这一工具。

有很多简化算法可供选择，但是在我们的案例中，另一个挑战是我们要在表面上绘制一组形状。这些形状覆盖表面，并且在简化时，如果对彼此相邻的两个形状做出不同的简化决策，则会遇到两个相关问题。容易做出不同的决策，因为一个形状可能只有一条连续线，而另一边可能有多个形状接壤该线。保持那些较小形状的完整性意味着保留更多的点，而较大形状可以简化和删除这些点。当您做出不同的简化决策时，最终可能会在绘制相邻形状时在地图上留下孔，或者形状重叠，这会在您用部分不透明度填充形状时导致视觉异常（因为重叠区域被绘制了两次并显得更暗） ）。

当您要组合形状时，间隙也会引起问题（我在上面提到了多边形并集问题），因为最终生成的形状带有很多小的异常孔，这些孔实际上不在实际数据中。这些都使处理更加昂贵，并且引入了视觉和分析异常。

在研究中，我遇到了Mike Bostock编写的TopoJSON库。 Mike在可视化社区中非常有名，他以前在《纽约时报》从事创新工作，并且是重要的开源可视化库d3.js的合著者。调查这是我必须学习新知识的地方。

TopoJSON库对我面临的问题采取了不同的方法。核心见解是，当您拥有一组形状（例如美国各州的轮廓或一个州的投票区）时，这些形状实际上具有划分表面的重要特征-它们不会重叠，并且可以完全覆盖表面您关心的部分表面。您确实有一个拓扑（因此具有包装名称），并且多边形共享此拓扑的线段或弧线。

核心见解是，您实际上没有将这组拓扑圆弧划分为表面，而不是将数据视为一组形状。这最终成为后续处理的关键。太酷了！

这种突破的模式经常发生。您有一些“理论上很难”解决的一般问题，但是通过确定关键的见解，您可以通过降低复杂性和更好的性能的方式来解决另一个更简单的问题。

处理的第一步是获取多边形并将其分割为在多边形相交的点处断开的弧。然后，通过标识共享弧并让它们引用相同弧的所有多边形来消除重复弧。

通过这种表示方式-每个多边形被描述为从共享的弧形集合中绘制的集合-我上面描述的关键挑战变得简单明了。

现在，当您简化时，就可以简化这些共享弧的粒度。这将自动保证共享一条边的两个多边形在边的两边都做出相同的简化决策。该边由共享的简化弧指定。

工会问题变得更加容易。给定一组描述为一组弧的多边形，您只需删除由多个多边形引用的所有弧。剩下的弧形描述了合并形状的边界（在重建最终形状时，存在一些细微之处，可以处理不相交的形状和孔）。

连续性问题在这个表示中也很简单-如果两个形状共享一条弧，则它们是连续的。

我发现与众不同的另一件事是，所有这些功能（以及我已跳过的其他功能）都是在几百行代码中实现的。一件非常整齐的工作。我更熟悉Microsoft Office这样的代码库，在其中您可能只有100几千行代码来处理复制/粘贴（公平地说，这确实是一个语义复杂的问题-让我告诉您有关HTML复制和粘贴的信息表一段时间）。

我有机会更深入地研究这段代码，因为事情并非完全“可行”。我个人发现，如果我不去尝试修复错误或以某种方式扩展它，则很难阅读和理解一段代码。如果我不尝试实现一些明确的目标，我只是没有足够的毅力去给予它所需的关注。

在这种情况下，我们需要先解决一些问题，然后才能在应用程序中使用它，因此我对工作非常满意，并且对解决我在此过程中遇到的问题也感到更加满意。

简化的挑战基本上是在多边形的粒度上进行简化的相反过程。对于共享一条边的两个多边形，可以做出相同的简化决策，但是对于同一多边形的不同边，可以做出不一致的决策。结果将是一个交叉的多边形。这通常仅发生在狭窄的扭曲形状上，例如绘制为覆盖河流或溪流路径的人口普查区。不幸的是，这些自相交多边形的结果恰好是我最初要避免的视觉和处理异常！

这使我有机会更深入地研究TopoJSON内的简化工作。该库将简化视为两个步骤。第一步是可配置的过程，该过程可计算每个点的权重，最常见的方法是计算该点及其相邻点形成的三角形的面积。您可以将三角形的面积视为衡量该点在显示线的真实路径时的重要性。第二阶段是指定一些权重限制并删除落在该权重限制以下的点（但始终保留标记多边形相交点的关键点）。

我采用的方法是一种迭代方法。我知道，如果我保留所有要点，显然我将拥有一组格式良好的形状。因此，我将进行简化过程，确定格式不正确的形状，并逐步人工增加这些退化多边形所引用的圆弧上的点的“权重”。这既可行又合理有效，因为权重被明确公开为简化过程第一阶段的输出。起初，我不确定这是否会带来足够的简化，但实际上，最终效果很好。图书馆暴露了这个中间阶段，而不是将整个过程视为一个黑匣子，这一事实使得这一点很简单。

开发过程有些曲折。我要加工成千上万种覆盖美国的形状，最后有数百种会给我带来麻烦。这些形状是什么？因此，我将沿着波士顿港到达一个地点，那里是一个大体矩形的手指，细长的手指遮住了码头。或由地理学家精心绘制的科罗拉多州的一组形状，以覆盖狭窄的蜿蜒溪流。对于明尼苏达州，该州使用的形状远远超出您的预期，并在其所有水域上仔细绘制。万湖之乡。在处理具有自触孔的多边形时（请参见图八），我必须使用TopoJSON合并算法来解决一般错误。为什么在整个美国只发生几十次？然后，我看到一组孔-一串珍珠-小心地在河中央的一系列岛屿周围绘制。

第二个问题是用于点和线序列的TopoJSON表示与用于地理处理的其他JavaScript包和格式一致（本质上，一个点由两个元素数组表示，而一个线序列表示为点数组），但是可怕的内存效率低下。 AC程序员认为数组可能是最简单，最紧凑的数据结构，但是JavaScript会将数组视为通用对象或哈希表的一种特殊形式，只是使用特殊字符串键，其形式为“ 0”，“ 1”等结果是，简单的点/线序列表示使用了大量的内存，实际上占据了我们的内存使用量。尽管事实如此，尽管TopoJSON仅通过一次在共享边上编码点，就比多边形组织的格式赢得了将近50％的巨大胜利，这是事实。

我以前曾想过一个压缩的表示形式，该表示形式实际上将一组复杂形状的所有点存储在一个二进制缓冲区中，这使我的内存使用率提高了两个数量级（我喜欢JavaScript，但这让我震惊了，天真的代表是）。我一直在寻找是否可以对TopoJSON包应用相同的改进。

这是小巧的包装（按代码行）的总体尺寸以及其简洁的设计所起到的作用。我能够将打包格式与另外几十行代码集成在一起（而现有代码只需在几个地方进行更改）。甚至更好的是，我需要使用TopoJSON库进行的核心处理，合并可以直接从打包表示形式进行。先前的方法保留了多边形的包装，但是需要解开坐标才能将其传递到我们用于多边形联合的库中。

最终集成完成后，完成的工作将我们的应用程序的内存使用量减少了100兆字节，并且从根本上消除了交互式应用程序中计算和内存密集度最高的问题。在此过程中，我学习了一种有趣的技术，并探索了美国地理的一些奇特之处。真有趣！