JONY

USB外部总线

USB总线显卡等高速设备是十分适合通过PCI/PCIe连入计算机的。但对于键盘、鼠标等设备而言，如果每个设备都占用1个PCI/PCIe的“席位”，那么代价就会较昂贵。于是IBM、Intel、微软等公司联手设计了一种将低速设备连入计算机的方案，于1998年正式发布，称为通用串行总线(USB)。USB设备无需复杂的跳线和插槽、安装设备无需重启，单机可接入127个设备(采用7位的设备地址)，设备直接由数据线供电。USB经过多年的版本迭代，从USB1.0时的1.5Mbps带宽发展到目前USB3.2 Gen2的10Gbps带宽。 USB由接入系统总线(PCI/PCIe)的USB根集线器实现，根集线器可接入设备或扩展集线器，扩展集线器可提供更多接口用于接入设备，故其拓扑结构类似于以根集线器为根的树结构，具体如上图所示。… 阅读全文

堆与二叉堆

堆(Heap)堆也是种基于树的数据结构，整体上分为小根堆(min-heap)和大根堆(max-heap)。如果一个树中的每个节点都包含一个关键字，并且每个节点的关键字都不大于其所有后代的关键字，则称该树是一个小根堆，反之如果每个节点的关键字都不小于其所有后代的关键字，则称该树是一个大根堆。上图给出了一个大根堆的例子。考虑到之后会讨论一些使用到小根堆的算法，并且小根堆和大根堆在各个方面都高度对称，所以之后主要讨论小根堆，并默认堆是指小根堆。 堆和平衡树一样存在很多不同的实现，堆的实现通常比平衡树简单，但也更灵活多变，不同的堆会用到不同的树的表示。事实上之前讨论过的Treap数据结构就使用到了堆，其在同一个二叉树中维护了一个BST和一个堆。   二叉堆(Binary Heap)1964年英国学者J.… 阅读全文

左偏树与左偏堆

空节点路径长度(Null Path Length)定义二叉树节点\(x\)的空节点路径长度\(npl(x)\)等于从\(x\)到\(x\)子树中的空节点的最小距离。于是若\(x\)为空节点则\(npl(x)=0\)，否则若\(x\)有空孩子则\(npl(x)=1\)，否则\(npl(x)>1\)。需明确大部分教材规定\(npl\)始于-1。下面给出与之相关的重要性质： a1) 设\(x\)为二叉树中的非空节点，则\(x\)子树的前\(npl(x)\)层是完美二叉树，前\(npl(x)+1\)层不是完美二叉树； 证明：\(npl(x)=1\)时该命题易验证，只需考虑\(npl(x)>1\)的情况。首先\(x\)子树前\(npl(x)-1\)层的节点都必须有2个非空的孩子，否则会导致\(npl(x)\)小于当前值的矛盾，于是其前\(npl(x)\)层必然能被看作高度为\(npl(x)\)的完美二叉树。但在第\(npl(x)\)层必然存在有至少1个空孩子的节点，否则将导致\(npl(x)\)大于当前值的矛盾，于是其前\(npl(x)+1\)层不能被看作完美二叉树。… 阅读全文

斜堆

斜堆(Skew Heap)1986年美国学者Daniel Sleator和Robert Tarjan提出斜堆，这是种“松散”的左偏堆，其能保证运算的摊还代价是\(O(\lg{n})\)，但不保证每次运算的实际代价都是\(O(\lg{n})\)。斜堆和左偏堆的运算功能一致并且仅\(merge\)运算的步骤存在区别，斜堆的\(merge\)运算仍以左偏堆的为基础，但其在每次回溯都必须交换节点的左右孩子。这里不妨直接给出斜堆的运算步骤如下： 1) \(merge(r_1, r_2)\)：具体步骤分情况如下： 1.1) \(r_1,r_2\)不都非空：若\(r_1\)为空则返回\(r_2\)，否则返回\(r_1\)； 1.2) \(r_1,r_2\)都非空且\(r_1.key \leq r_2.key\)：置\(r_1.right=merge(r_1.right,… 阅读全文

二项树与二项堆

二项树(Binomial Tree)二项树的形态是递归定义的，通常用\(B_k\)表示每种二项树形态，其中\(B_0\)仅包含树根节点，\(B_k\)可通过连接2个\(B_{k-1}\)得到，连接方式是在2个\(B_{k-1}\)间额外加1条树边，使其中一个\(B_{k-1}\)成为另一个\(B_{k-1}\)的最左子树，具体可参考上图。注意到该定义表明二项树必须是有序树，另外二项树通常更适合用孩子兄弟表示法实现。下面给出关于二项树的重要性质： a1) \(B_k\)形态的二项树共包含\(2^k\)个节点； 证明：将二项树形态对应的节点数计为\(n(B_k)\)，则有\(n(B_k)=2n(B_{k-1})=…=2^kn(B_{0})=2^k\)。 a2) \(B_k\)形态的二项树的高度为\(k+1\)；… 阅读全文

斐波那契堆

斐波那契堆(Fibonacci Heap)F堆可以认为是“松散”版的二项堆，其也是基于“链表+树”的。F堆上的树无需是二项树，其仅松散的要求链表上的树根出度唯一(仅要求某些运算结构维护该性质)。并且注意到F堆使用“双向循环链表”的物理结构表示链表与树，这种链表不承载序信息，故F堆的链表与树都是无序的。相比二项堆用“孩子兄弟法”表示树，F堆在用“双向循环链表”表示树时，需把所有子节点都指向父节点，而父节点只需一个指向其任意子节点的指针。最后明确“双向循环链表”只有单节点时，该节点的左右指针都指向其自身。F堆用最小节点指针\(min\)实现二项堆的链表表头指针\(head\)的作用。 F堆的运算与二项堆相同，其除\(pop\)与\(delete\)的代价为\(O(lgn)\)，其他运算的代价为\(O(1)\)。所以F堆的理论代价非常的优秀，但由于其实际代价中隐含着“大系数”，故程序语言中的优先队列不用F堆，F堆只适用于需要大量执行其\(O(1)\)运算的场景(如MST/Dijkstra)，所以通常认为F堆只是一个理论上更高效的结构。… 阅读全文

棋盘覆盖问题

棋盘覆盖问题(chess cover problem)在\({2^k}\times {2^k}\)的棋盘格(\(k\)为正整数)中，其有1个确定位置的方格一开始是被覆盖的，现提供4种不同L型骨牌(如上图所示)。棋盘覆盖问题要求得到其中1种方案，用这4种骨牌覆盖所有方格，且覆盖是没有任何重叠的。 然后找该问题的分治算法，由于棋盘长宽相等且是2的幂，所以棋盘能拆成等大的4个象限，被覆盖的方格在某个象限里。这时考虑在中心位置选一种形状的骨牌放入1个，要求其刚好横跨另外3个没有被覆盖方格的象限。这时这4个象限每个都刚好有1个被覆盖的方格，这样就可把这4个象限当成“子棋盘”来递归的求解子问题，直到遇到\(2\times 2\)的“子棋盘”时，使用1个骨牌覆盖后就等于完全解决了这个子问题，而无需继续递归下去求更小规模的子问题。… 阅读全文

接口电路与地址译码电路

接口电路接口电路是指计算机之间，计算机与外围设备之间，计算机内部部件之间起连接作用的电路。一般由寄存器组、专用存储器和控制电路几部分组成，当前的控制指令、通信数据、以及外部设备的状态信息等分别存放在专用存储器或寄存器组中。 接口电路这4个字容易令人望文生义，联想到PCIe接口、USB接口。实际上接口电路一定程度上与总线这个概念平行，并且有部分的重合。接口电路强调两个部件直连，总线强调多个部件用公共的总线互连。接口电路强调信号和数据形式的转换，总线更注重可扩展性、灵活性、规范化。接口与总线有时也不加区分，合称为总线接口。通常接口电路是连入计算机系统总线的，比如INTEL 8255A接口电路芯片。 上图是个类似INTEL 8255A的接口电路芯片引脚图，是种并行IO接口(PIO)芯片。右边3×8根IO信号线可用于连接各种支持它的IO设备，可以是键盘，开关等。左边包括接入总线的D0-D7信号线，WR/WD的写信号线/读信号线，RESET充值信号线，A0-A1的地址信号线，CS片选信号线。该PIO接口芯片可通过3位的配置寄存器配置，来设置3个Port的输入输出，而每个Port都会对应一个8位锁存器用来暂存数据。… 阅读全文

TRIE树

TRIE(前缀树/字典树)TRIE常用于存储和表示字符串的集合，并实现该集合上的增删字符串运算。其核心思想是用公共前缀表示字符串，比如abcd与abc的公共前缀是abc，当字符串间恰好没有公共前缀时，比如abc,edfg,czx构成的集合，那么其会存储3个前缀abc,edfg,czx。   其常用于存储字符串构成的集合。其结构是这样的，Trie的根节点不存储字符，其他节点仅存储单个字符，且同一层节点无重复字符。节点有变量存储“颜色”，若某节点被“染色”说明从根到该节点的路径存储了一个字符串，除此之外Trie的叶节点肯定是“染色”的。下面讨论Trie的运算结构： 1）插入：首先查找根节点全部孩子节点，若找到待插入串首字符则进入该节点并重复该步骤，若没有则在该处新建节点并插入剩余字符，最终为叶节点染色。如果用哈希表/dict来记录每个节点的儿子，可以在\(O(1)\)时间完成当前层的查找，所以可以认为时间复杂度为字符数\(O(n)\)。… 阅读全文
滚动至顶部