Xinhecuican's Blog

缘起B树属于动态查找树，二叉树，平衡二叉树，红黑树都是动态查找树。关于查找的基础内容可看。他们的查找效率都可以达到$log_2^n$，其中n是树的深度。 虽然他们的查找效率和遍历相比已经有很大提升了，但是和哈希相比又大大不如。QMap（红黑树为数据结构）在n=10之后效率就比不过QHash(哈希为数据结构)，越到后面差距越大。但是在数据库中却是使用B树作为数据结构。因为数据库除了考虑速度还要考虑空间，而hash对空间要求大。因此日常对空间不敏感的程序尽量使用hash。 前面已经说了，决定查找次数的是树的深度。假如有65535个数据，那么树的深度为16，那么平均查找深度为 (1 + 2 2 + 3 4 + 4 8 + 5 16 + …. + 16 * 32768) / 65535 = 14.如果14个数据块位于2个不同的磁盘块上（因为是指针不是连续存储），那么就需要2次磁盘读取，所需时间便在毫秒以上。他和直接查找也显现不出太多优势。 因此减少树高就是非常必要的了。一种解决思路就是由二叉树变为多叉树，每一层容纳的数量变多了，树高自然就减少了。此外，各个分支如果树高大致相同毫无疑问平 ...

8数码问题8数码问题是在一个九宫格上有8个数，初始中间一个空缺，外围随机排布，最终要8个数按顺序排列初始3281 4567中间的格子可以利用，也就是说可以328 14567最终1238 4765可以使用广度优先搜索进行遍历，那么第一层有四种情况（将上下左右4个移动到中间)，然后第二层有8种第二层的一个例子328 14567第一种 28314567或者328514 67 然后就这样不断遍历，直到找到最终结果 但是这样的复杂度明显太高，我们可以定义一个函数预先判断走那条路可能得到更好的结果。 定义f(n) = g(n) + h(n). 其中g(n)表示现在是第几层的搜索，h(n)表示现在和最终结果还有多少不同 拿上面的例子假设现在到了 28314567则g(n) = 2他和最终结果1238 4765有2个相同，因此h(n) = 6然后根据上面的这个式子，每次选取最小的进行搜索，这样相比于盲目的搜索更快 A*算法通过上面的例子，我们对A算法有了初步的了解。A算法的关键就是定义 f(n) = g(n) + h(n) g(n): 表示当前已经花费的代价。也可以说是距起点的代价 h(n): 预计 ...

组合电路和时序电路 组合电路： 由当前输入值决定输出值 时序电路： 由当前输入值和前一阶段的输入值共同决定输出 例如: 图b和图f属于时序电路，因为它的输出转化为了下一次的输入。图f中的符号是组合电路 图d是一个错误电路，因为到n6点可能会冲突 布尔表达式一些术语： *: 与符号，取交集，也叫相乘 +： 或符号，取并集，也叫相加 项： 变量或者它的反 最小项： 一个包含全部输入变量的乘积项。例如有三个变量A、B、C，则ABC是一个最小项（也就是 $A \cap B \cap C$), 而AB不是 最大项： 包含全部输入的和。 例如 A + B + C(也就是$A \cup B \cup C$)是一个最大项 蕴涵项： 多个项相乘 与或式与或与式与或式 A B Y 最小项 最小项名称 0 0 0 $\bar{A} \bar{B}$ $m_{0}$ 0 1 1 $\bar{A} B$ $m_1$ 1 0 0 $A \bar{B}$ $m_2$ 1 1 0 A B $m_3$ 真值表每一项都和一个为 TRUE的最小项相关联，并且它的编号正好是AB的 ...

语法分析基础编译的第一步是词法分析，第二步是语法分析。词法分析产生的结果是标识符，第二步是判断源程序文法是否合法。例如if{...}就是不合法的文法，但是他产生的标识符都是正确的。 工作原理： 通过上下文无关文法产生的文法式，识别输入字符串是否是一个句子。从左至右每次读入一个字符进行规则匹配。 问题及解决左递归例如 规则为P->Pa字符串为a起始非终结符为P读入a后将栈中的P展开为Pa,然后因为是从左往右匹配因此读入P，展开为Paa,如此递归，得到死循环 消除递归的方法： 消除直接左递归 经过这样的转换之后产生的语言没有改变，但是消除了直接的左递归 再将它一般化得： \begin{aligned} A &\to A \alpha_1 | A\alpha_2 | \dots | A \alpha_m | \beta_1 | \beta_2 | \dots | \beta_n\\ 则可以改写为\\ A &\to \beta_1 A^{'} | \beta_2 A^{'} | \dots | \beta_n A^{'}\\ A &\to \alpha_1 A ...

字符串匹配是在一个长度为s的t串中找到和长度为m的p串相同的部分。t串是匹配串，p串是模式串 Pabin-Karp算法它的基本思想是哈希。即将匹配串中每一个长度为m的子串进行哈希并与p串的哈希值进行比较。 假设模式串p[1…m]，得到哈希值的算法为 p = （p[m] + 10(p[m-1] + 10(p[m-2] + … + 10(p[2] + 10(p[1]))…)） % q — 霍纳法则 q是为了防止超范围的，10是基数，可以变成其他值 对于t串（匹配串），它的处理方法与p串相同，但是还需要进行移动，移动的方法为 t_2 = 10(t_1 - 10^{m-1}T[s+1]) + T[s+m+1]其中T[s+m+1]是原来字符串的高一位，T[s+1]就是原来字符串的最低位。也就是减去最低位然后将字符串左移一位再加上最高位。 $10^{m-1}$可以使用快速幂的方法在O(lgm)时间计算完。 在计算完所有子串之后就可以对每一个哈希值进行比较了。如果p串哈希值和子串哈希值相同并不能说明二者一定相同，还可能产生哈希冲突。因此还需要对每一个字符进行匹配。 bool match(stri ...

支配 支配集： 挑选出一些顶点组成支配集，使得所有其他的点都和这个集合中的点相连。 极小支配集： 支配集删去任意顶点之后不是支配集 最小支配集： 支配集中顶点数量最小的 只配速： 最小支配集中点的个数 例如图中两个都是极小支配集，其中第一个是最小支配集。 定理： 无向图无孤立点，$V_1^$是极小支配集，则存在$V_2^$也是极小支配集，且$V_1^ \cap V_2^ = \oslash$ 证明： $V_1^$是支配集，那么$V - V_1^$也是支配集反证： 如果不是支配集，那么存在$\exists u \in V_1^ , \forall v \in V - V_1^ , (u, v) \notin E$, 因为u不是孤立点，那么$V_1^ - {u}$还是支配集。所以$V - V_1^$是极小支配集 $V - V_1^*$是支配集，那么它的子集中必定存在极小支配集 求最小支配集 例如求上图的最小支配集 \begin{aligned} \Psi (v_1 , v_2 , v_3 , v_4 , v_5 , v_6 ) &= (v_1 + v_2 + v_3 + v_4 ...

多路复用和多路分解多路分解： 多路分解指的是将报文段中的数据提交到正确的套接字 1 1. 应用程序接受信息的接口 ↩ 多路复用：从主机不同套接字上收集数据，并为每个数据块加上首部信息（如源端口号和目的端口号等）形成报文段，然后传到网络层。 多路复用也就是从传输层到网络层的过程，而多路分解是从传输层到应用层的过程 要想提交到正确的套接字，其实也就是提交到正确的端口。在计算机中端口范围在 0-65535 中，其中 0-1023 是周知端口号，有特殊用途，而其他就是分配给应用程序使用的了。 UDP 的多路复用和多路分解 UDP 的运输层报文段包括应用程序数据，源端口号，目的端口号和其他两个值。通过目的端口号可以标识要送到目的的具体位置，而源端口号则是为了送回数据时使用的。 TCP 的多路复用和多路分解 TCP 和 UDP 区别是 TCP 套接字是一个四元组 (源 IP 地址， 源端口号， 目的 IP 地址， 目的端口号）来标识的。因此他还可以让两个到同一个端口号的 TCP 连接互不干扰（因为有了源 IP 地址，所以可以分辨出这个数据时从哪发出的） UDPUDP 是一种不可靠运 ...

概念很多词语在不同语境下有不同含义，我们需要确定在某种语境下具体的含义。 语义消岐（WSD)定义： 确定一个歧义词在某种语境下应该使用哪种语义 消岐面临的三个问题： 判断一个词是否是多义词 对不同多义词的含义进行区分 确定在不同语境下应该使用哪种语义 基于贝叶斯的消岐假设一个词有多个意象$s_1 s_2 .. s_n$，上下文（句子）C$w_1 w_2 … w_n$需要确定在该语境下使用哪种语义，即： P(s_i | C ) = \frac{P(C | s_i ) P(s_i )}{P(C)} P(C | s_i ) = P(\{w_j | w_j \in C \} | s_i ) = \prod_{w_j \in C}\frac{Count(w_j , s_i )}{Count(s_i )} 其中$P(s_i)$是这个词义出现的概率 基于互信息互信息是使用另一个信息来表示当前信息。例如想知道当前词的语义信息，我们可以根据上一个词的时态或者是语态。 设一个中文词在英语中有若干译词$t_1 t_2 … t_n$,并且这个中文词有若干含义$v_1 v_2 … v_n$。 算法过程 ...

HTTP协议基础HTTP由两个程序组成：客户程序和服务器程序。客户程序就是我们电脑上的程序 一个Web页面是由若干对象组成的，对象指的是一个文件，例如HTML文件，JPEG图像，Java小程序等。 多数Web页面包含一个HTML基本文件和几个引用对象。首先获得基本文件，基本文件之中又有链接到其他文件的URL,然后通过这些URL又获得其他文件。 例如有时我们直接从浏览器下网页文件打开后发现这个网页既没有排版也没有字体颜色，也没有图像。这里我们下载的文件就是HTML基本文件，如index.html.如果我们想要获得完整的页面就需要根据基本文件中的url再去获得其他文件然后通过浏览器合并到一起。 HTTP使用TCP作为传输层协议。TCP大致是首先发起一个与服务器的TCP连接，在链接成立之后就可以进行稳定的传输了。 非持续连接和持续连接非持续连接指的是所有请求都通过单独的TCP连接发送，持续连接时所有请求都通过同一个连接发送。 HTTP的非持续连接假设我们请求一个HTML基本文件和若干图形。并且这些对象位于同一台服务器上，那么非持续连接请求的大致过程是： HTTP客户进程在端口号80发起一个 ...

基础我们在生成程序的时候，会发现每个程序的起始地址都是一样的，那么这种一样的地址怎么赋给实际的物理地址上的呢？这就要依靠虚拟内存机制了。 虚拟内存着力于解决进程间内存分配的问题，并且它还有一个作用是使进程之间相互隔绝。例如不小心产生了一个野指针指向了其他内存的位置，但是实际上却不会破坏其他程序而只会破坏自己的程序，这是因为虚拟内存限制了每个程序所使用的空间，如果超出限制就会报错。 程序中所使用的空间叫做虚拟空间，一共有2的n次方。而系统上有一个物理地址空间。虚拟内存做的其实是把虚拟空间上的内存地址映射到物理空间上。在cpu中，有一个叫MMU的部件专门做虚拟地址和物理地址转化。 虚拟内存的组织形式虚拟内存中的内存其实是按页进行划分的。这类似与磁盘中的扇区概念，即使那个扇区中只有一个字节的数据，取数据时也是把一个扇区全取出来。 虚拟内存页的大小一般是4kb到2mb之间。而物理内存也是按页进行分块，并且块的大小和虚拟内存页的大小相同。 其实把程序加载到内存时也不是一股脑直接加载的，而是一块一块逐个加载，并且如果内存满了还有块替换策略，这实质上是把内存当做一级缓存使用。 虚拟页有三种情况： ...