Table of Contents
Algorithm
Sum of Two Integers: https://leetcode.com/problems/sum-of-two-integers/
https://dreamume.medium.com/leetcode-371-sum-of-two-integers-6e5184c0a915
Review
Lossy Acoustic Propagation
https://ccrma.stanford.edu/~jos/pasp/Lossy_Acoustic_Propagation.html
波浪在球形扩散中的减弱在之前的章节中已描述，不是源振幅在旅行波浪中的衰弱。在空气中，由于空气的吸收总是有一个明显的额外损失。空气吸收随着频率变化，对高频通常比低频减弱得更快。在摆线中的波浪广播是一个模拟吸收损失，如同物理世界中每个其他类型波浪的广播。为模拟这样的广播损失，我们可使用一个延迟线系列带一个散的过滤。实践中，在每个频率想要的减弱变成过滤的想要的大小频率响应，且过滤设计软件（典型的如matlab）被用来计算过滤系数来估计在某些优化方法上想要的频率反应。相反馈可能为线性的，最小的或未限制的当粘滞过滤散处理不考虑为有害的。典型的一个频率依赖权重在估计误差对应音频感应重要度（例如，权重1 / f是一个简单的例子增加在低频上的精确度）。一些过滤设计方法在8.6章节总结
指数级衰退旅行波浪
设 $ g(r, \omega) $记为衰弱因子，其跟一个平面波浪在距离r以频率 $ \omega $ rad/sec的广播相关。对一个理想的平面波浪，没有扩散损失（减弱为1 / r）。在统一的条件下，减弱的总量（dB）跟传输距离成比例；即，减弱因子对两个连续段落的广播路径是有相乘关系的
$ g(r_ {1} + r_ {2}, \omega) = g(r_ {1}, \omega) g(r_ {2}, \omega) $
这个属性意味着g是距离r的指数函数
频率独立空气吸收通过一个声学模拟减弱很容易有模型
$ z^{-1} \to gz^{-1} $
在模拟延迟线的传输函数中，g记为减弱在一个采样周期（T秒）的广播相关。这样，对模拟吸收对应一个M采样延迟，微分等式变成
$ y(n) = g^{M} x(n - M) $
频率依赖空气吸收过滤
更一般地，频率依赖空气吸收可被模型如下
$ z^{-1} \to G(z) z^{-1} $
G(z)记为在广播媒介中每采样地过滤。因为空气吸收不能增大任意频率的波浪，我们有 $ | G(e^{j \omega T}) | \le 1 $。一个对平台波浪模拟的有损延迟线描述如下
$ Y(z) = G^{M}(z)z^{-M}X(z) $
在频率域，且
$ y(n) = \underbrace{g * g * \cdots * g *}_ {M \text { times }}(n-M) $
在时间域，* 记为搅动，且g(n)是每采样损失过滤G(z)的脉冲响应。G(z)的影响在系统的极上在之后讨论
对球形波浪，由于球形扩散的损失为形如
$ Y(z) \propto \frac{G^{M}(z) z^{-M}}{r} X(z) $
r是从X到Y的距离。我们看到球形扩散损失因子在广播距离r上是抛物线形式的，空气吸收是r的指数
消散旅行波浪
除了频率依赖减弱，LTI过滤可提供一个频率依赖延迟。这可被用来模拟消散波浪广播
总结
到现在，我们考虑线性、时间不变(LTI)媒介旅行波浪模拟。主要的例子考虑空气中的波浪广播，但摆线的波浪行为类似。我们看到在一个LTI媒介旅行平台波浪的点到点广播可被只使用一个延迟线和一个LTI过滤简单模拟。延迟线模拟广播延迟，而过滤进一步模拟一个独立减弱因子在每个频率上通过它的振幅响应（例如，模拟空气吸收），且一个频率依赖广播速度使用它的相反应（模拟消散）。如果有额外的球形扩散损失，振幅可被进一步减弱为1 / r，r是到源的距离。对更多平面波浪和球形波浪的声学细节，见附录B
这样我们已考虑只有旅行波浪沿一个方向传播。下一个最简单的例子是1D声学系统，比如摆线和声学管，其旅行波浪可在两个方向上广播。这样的系统使用一对延迟线模拟被称为一个数字化波浪指导
Tips
10x程序员工作法 - 以终为始
一开始讲了个设计登录功能的例子，有些同事手很快，马上就开干了，结果做出来的跟客户想要的不是一个东西。用这个例子说明人一般是喜欢按部就班地做事情，缺乏以结果为目标的思维习惯
这里提到了以终为始的思维方式，作者提出了直觉做事是很基础直观的，但还不够好，需要有更高介的思维方式，更能理解到事情的本质，从而得到高的结果
这里提出任何事物都是两次创建的过程，一次是在头脑中，然后是付诸实践，即二次创建。我们经常在第一次创建过程中没有做好，就进入了第二次创建。即我们通常在头脑中做的工作不够，而更喜欢直接动手工作。这样导致做出的结果可能不是我们想要的。
按照以终为始的思维方式，我们考虑的是别人会怎么用我们的平台。我们设计的方式为用户到我们的网站，阅读相关文档，然后参考文档一步一步照着做
这里关键的第一步是文档，这是用户接触我们平台的第一步，决定了他对我们产品的第一印象
我们应该从写文档开始，有了这个文档，团队的所有人对于我们平台是个什么样子，才有了一个比较初步的认识。有了这个文档，人们就会对这个构想出的平台进一步提出各种反馈，这些反馈进而让我们逐渐地锁定了目标，然后，我们才开始动手写代码
以终为始就是在做事之前，考虑结果，根据结果反推需要做的事情
这里要确定完成的定义，怎么才算事情做完了。它应该是一个清单，由一个个检查项组成，用来检查我们的工作完成情况，让人一目了然。目的是尽量消除不确定性，达成共识
需求是开发中关键一环，容易出现需求不清晰或理解偏差等问题。在实际的开发过程中，大量的分歧来自于对“需求完成”的定义。因此，在做任何需求或任务之前，先定好验收标准，避免大量的扯皮工作
上面提到了需求的验收标准，这里代码也有验收标准，这里主要的验收要求是持续集成，每次代码提交的代码都要集成
对于一些不确定性，特别是产品需求，默认所有需求都不做，直到弄清楚为什么要做这件事，要确保需求是经过严格思考的
Share
实现
https://crypto.stanford.edu/pbc/notes/zdd/implementation.html
我们看一些复杂的问题当实现ZDDs后变得清晰
表达一个ZDD
我们用一个3元组(V, LO, HI)的数组来表达一个ZDD。第一个元素V是变数，而LO和HI指向数组的其他三元组
数组中头两个元素为守卫代表FALSE和TRUE节点。在索引0，我们有三元组(-1, 0, 0)，其表示FALSE，在索引1，我们有三元组(-1, 1, 1)，其表示TRUE。-1为无意义值表示该节点为一个终止节点，一个替代是最大变量加1
两个守卫的LO和HI部分也是无意义值，其被算法用来检测终止节点。正常情况下，一个三元组必须指向包含一个更高域或这些守卫中的一个。回忆没有HI域允许指向FALSE三元组
在一个例子中，Knuth建议对V使用8位比特，另两个用28位比特，这样三元组可放入64位的地址中。当然，这对包含不超过256个变量的问题足够了。因此，也要避免布尔逻辑需要额外的相关域，我使用16、32和32比特代表这三个成员
struct node_s {
uint16_t v;
uint32_t lo, hi;
};
缩减一个ZDD
假设我们希望缩减一个未缩减的ZDD，我们希望重排列我们的数组使得每个(V, LO, HI)三元组是唯一的且没有HI域为0。明显的办法是从低向上遍历ZDD，哈希三元组，如果重复则用哈希表中的值替换重复节点，且移除零HI域的节点
Knuth描述一个更加空间友好的算法（基于Sieling和Wegener），其证明很重要因为ZDD很吃内存。我们给出一个简要说明
我们需要每个节点多一个域，称为AUX，包含链接。这样我们视一个节点为4元组(V, LO, HI, AUX)。实际上，我们把AUX作为两个域来使用：符号位存储一比特的信息，剩下的存储链接。在算法的最后，我们也处理LO域的符号位为一个独立的域。因此这个算法只在我们有最多 $ 2^{n-1} $个节点有效，当链接为n位宽
我们节省房间通过使AUX在算法中扮演不同的角色。除了AUX，我们只需要一个头链接的数组，每个变量一个，和一个单链接名为AVAIL，其指向删除节点的列表
第一个目标是构建相同标签的节点的链表，每个变量一个。这些链表被头链表索引。从根开始，我们深度优先探索ZDD，在每个节点，在我们第一个访问我们使用AUX记录未探索选择的最后的交点，且这样我们离开这个节点，我们把AUX作为和当前节点有相同标签的节点列表的链接。通过这个阶段，AUX的符号位代表是否我们已访问了一个节点
接着，从底部开始，我们遍历从它的头接着列表的相同标签的所有节点。我们使用AUX来链接下一节描述的通过一个方法有相同LO目标的节点形成桶。这些桶的末尾形成另一个列表；我们使用AUX位区分这些链接和桶里的链接
为找到确定的LO域，我们使用更低水平的AUX域作为空间。这很好因为所有更低水平现在已被缩减。在遍历过程中，我们设置它的LO节点的AUX域的符号位且指向当前节点的剩余；如果该位以被设置我们知道当前节点和其他的节点有相同的LO域
同时，我们也有机会删除节点其HI目标是TRUE。为删除一个节点，我们把它从桶中拿出，把LO指向父节点且也设置LO的符号位，且通过HI域链接到AVAIL列表
对每个桶，我们通过它的内容迭代且看相同HI目标的节点。又，我们使用更低水平的AUX域。当我们遍历桶，我们标签它的HI节点的AUX的位且链接剩余到当前节点。如果已经标签，则我们知道当前节点是重复的且我们删除：我们设置LO域的符号位且使用它指向原始的拷贝，且通过HI域添加当前节点到AVAIL列表
在节点删除时操作LO域允许上层水平来正确地探测和处理子节点
细节很繁琐因为AUX频繁被重使用。第一个阶段使用AUX的符号位记录是否一个节点已被访问，且AUX的链接部分有两个目的。首先，它指向最后一个未完全探索的节点。通过回溯，我们跟着这个链接，它变成一个头列表的链接
第二个阶段使用AUX在当前水平上作为一个内部桶或内部桶链接，其符号位代表链接类型，且然后使用AUX在低水平找到相同的LO域。这里，符号代表如果节点之前被访问，且链接指向首次访问的父节点。最后，低水平的AUX域被用来找到相同的HI域
有时AUX自动准备好下面的步骤，比如在深度优先遍历之后。其他时候，我们必须清理特殊的AUX节点在重使用它们之前
Melding ZDD
假设我们希望计算两个ZDD的并。明显的方法是生成形如(V, W, L, H)的元组，然而递归跟随融合过程，其(V,W)为融合节点且(L, H)链接到其他模版，不是节点。我们保持一个模版的哈希表来避免重复。然后当所有模版被生成，我们可构建最后的ZDD通过给每个模版制作节点，小心不产生重复或零HI域的节点
Knuth推荐分配一个巨大的元组池，且把输入ZDD放在数组的开头。在欲处理步骤，我们统计在每一层将产生的模版数。这给出该层哈希表大小的边界，其放于池的高端。使用链，且模版域有不同的意义
一旦所有模版产生，池底可自由使用。我们放置结果。我们应用我们之前的想法转换模版为节点：我们从底开始一层一层继续且桶排序来避免重复
Crit-bit树
我的哲学是让它先工作，然后让它工作得快。除了使用哈希表或桶排序，我使用crit-bit树这样我能开始快速使用ZDD
Knuth不使用二叉搜索树因为其时间复杂度上有一个额外的log因子。然而，虽然有关，我感觉tries为一个可接受的替代。与二叉树不同，我们不比较每个节点的key。像哈希表我们只在查找是最多读取key一次，且一旦更多来确认我们达到正确的目的地
主要的缺点是在一个crit-bit树中我们需要每个key位跟随一个指针，然而一个哈希函数操作在所有key上一次。另一方面，一个trie按需要增长，不需要估计空间和处理哈希冲突
虽然我当前的实现对trie节点不使用池的上尾端，它容易维护和调试，且适合我们的实验
ZDD Bases
以上描述如何构建一个基于栈的ZDD计算。我们开始于一个巨大的元组空数组。我们把ZDD放入栈，通过把他们放入下一个未使用的数组元素上。我们使用以上的融合算法操作最后的两个ZDD，用结果的ZDD替换它们
有时我们想要一个计算模型比栈更灵活；我们可例如想要ZDD当等于(ab + bc + ca)。在这个情况下，我们可设我们的ZDD共享节点，这样每个元组在ZDD间是唯一的。自然的，我们必须记住每个ZDD的开始节点。即我们的数组保持一个袋子是一个ZDD除了它可有多个源节点。该数据结构是一个ZDD base
我们维持一个映射从(V, LO, HI)元组到数组索引。该数据结构被称为唯一表。然后融合用之前描述的相似的方法，除了现在我们保持输入节点。对更快地查找，在关系下，唯一表是一个映射的数组，每个对应一个V
如果我们希望在ZDD base中支持删除，我们可使用引用计数来释放节点
并行计算
我没有探索并行，但这似乎为一个承诺的途径。许多问题需要几个家族的交，且自然地，独立线程可计算不同的交
在计算一个交时，不同的线程可能工作在不同的路径，但哈希表内容变成一个成本