-
数据表实现
文件格式对开发者来说，内存的访问是透明的。但磁盘访问需要通过系统调用实现。需要自己设计数据结构。字符串与变长数据字符串可以表示成size+size个字节物理组织文件拆成相同大小的页、单个块或者连续块。相同大小的页是为了简化读取和写入访问。表结构数据库的表结构一般是固定的，指定了字段的数量、顺序和类型。对于变长内容，会在固定字段区先存长度，再在之后的变长字段区存具体内容。页结构我们需要满足： 最小开销的变长存储需求 回收已删除记录的空间 引用页中的记录，无论它在哪PostgreSQL等...…
-
美团笔试记录
翻转字母 给定一个字符串，问最少修改其中多少个字母，可以让修改后的字符串不存在相邻的相同字母。 输出最小的修改次数贪心import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner in =new Scanner(System.in); String s = in.nextLine(); char[] c = s.t...…
-
设计模式（二）
建造者模式奖复杂对象的构建和表示分离，使得同样的构建过程可以创建不同的表示应用 需要生成的产品对象有复杂的内部结构 需要生成的产品对象的属性相互依赖，需要指定生成顺序 对象的创建过程独立于创建该对象的类 隔离复杂对象的创建和使用优点 可以奖产品本身和产品的创建过程解耦，使得相同的创建过程可以创建不同的产品对象。 用户使用不同的具体建造者可以得到不同的产品对象 可以更加精细控制产品的创建过程缺点 如果产品之间的差异性很大，则不适合使用建造者模式 如果产品的内部变化复杂，可能...…
-
设计模式（一）
策略模式策略模式定义一个算法族，让算法的具体实现和调用者解耦。应用策略模式应用于以下的场合 许多类只有行为上的差别，通过策略来实现行为配置和复用 某个算法需要多个复杂度不同的实现 数据职责需要封装的情况 需要if-else来选择行为的情况优点 可以借助继承来提取算法公共部分 替代子类型 消除条件判断缺点 需要选择实现方式 调用者需要了解具体的策略 调用者和策略的调用开销 增加更多的类简单工厂模式可根据参数的不同返回类的不同实例。优点 无需知道具体类的类名...…
-
需求工程复习
目标模型确定项目前景和范围保证项目涉众以符合项目需要的角度描述现实世界，并以尽可能符合项目需要的方式描述事物和世界，方法是： 定义项目前景：所有的涉众都从共同认同的项目前景出发，理解和描述问题域及需求。 定义项目范围：范围内的事物和事件是描述的目标。确定项目前景和范围的关键是定义业务需求和能够满足需求的高层解决方案，包括： 业务目标、目的 高层业务功能 每个高层业务功能所关联的高层数据 每个功能相关的项目设置 等等。。。如果存在不同业务需求之间的冲突，那么在该阶段必须予以解决...…
-
软件系统设计
单一职责原则一个对象只应该包含单一的职责，并且该职责被完整的封装在一个类里。另一种定义为：就一个类而言，一个类应该仅有一个引起变化的原因。分析一个类承担的职责越多，其被复用的可能性越小。如果一个类承担的职责过多，就会造成职责之间的耦合，当其中一个变化时，可能会影响其他职责的运作。类的职责主要包括两个方面：数据职责和行为职责，数据职责通过属性来体现，行为职责通过方法来体现。开闭原则一个软件实体应当对扩展开发，对修改关闭，即在不修改源代码的情况下改变其行为。分析抽象化是开闭原则的关键。开闭原则...…
-
安全分析
信息流安全静态分析中的信息流安全主要考虑的是机密性和完整性机密性机密性的主要目的是阻止秘密信息被泄漏。非推理规则禁止高密级的信息影响到低密级的信息。我们为每个变量设置密级，密级是具有偏序关系的格。当低密级的变量被高密级的变量赋值时，则违反了非推理规则，就会影响到机密性完整性机密性主要目的是组织不受信任的信息对系统造成破坏我们为每个变量设置完整性等级，完整性等级同样是具有偏序关系的格。低完整性的变量向高完整性的变量进行写入是禁止的。隐藏信道在计算系统中标识信息的机制叫做信道，而在传输信息目的...…
-
指针分析（五）
上下文敏感的指针分析算法该算法与上下文不敏感的指针分析算法类似，主要是在指针、对象和方法中多出了一个上下文属性。而上下文敏感中最重要的部分就是多出的Select函数，该函数用于生成上下文。不同的Select函数会产生不同的指针分析变种上下文敏感变种Select函数中包含调用者上下文、调用点、接收对象、调用方法，根据对这些参数的使用会产生不同的上下文敏感的变种上下文不敏感上下文不敏感可以看作是上下文敏感的一种特殊情况：Select(c,l,c':o,m)=[]调用点敏感每个上下文包含了一个调...…
-
句法分析（二）
LL(1)文法自顶向下构建语法分析树，根节点是起始符号S，每个中间结点表示堆某个非终结符应用某个产生式进行推导。叶节点是词法单元流，仅包含终结符和EOF($)。LL(1)总是选择最左边的非终结符进行展开，从左到右读入词法单元递归下降递归下降的典型实现：void A(){ 选择一个A产生式,A -> X1X2...Xk; for(i = 1 to k) { if(Xi是非终结符) Xi(); else if(Xi等于当前输入符号a) 读入下一个输入符号; else e...…
-
指针分析（四）
上下文敏感的指针分析上下文敏感模型通过区分不同上下文的不同数据流来为调用建模，从而提高精确度。当前最熟知的上下文敏感策略是调用点敏感。每个调用点代表了一个调用栈。基于复制基于复制的方法是最直接的实现方式。每个方法会被一个或多个上下文标识，其中的变量也会被上下文标识。而每创建一个上下文，方法和它的变量都会被复制一遍。上下文敏感堆在实际分析中，为了提高精度，我们为抽象对象也用上下文标识。最常用的策略是对象的上下文来自于创建它的方法记号 上下文$c\in C$ 上下文敏感方法$c:m\in ...…
-
客户洞察
客户洞察客户视角是商业模式的指导性原则，客户的观点决定了我们选择怎样的价值主张、渠道、客户关系和收益来源。 透彻的观察，发现情感的源泉，发现内在的内容、意义和本质 事实上，企业在市场上重金投入的产品、服务和商业模式往往会忽略客户的观点 成功的创新需要深入理解客户的环境、日常工作、担忧和渴望客户洞察的难度： 透彻理解客户 清楚了解企业当前关注那些客户的需要移情图看：描述该客户在ta的环境里所看到的东西听：描述环境如何影响这个客户想&感受：尝试勾勒客户思维的过程说&做...…
-
句法分析（一）
上下文无关文法上下文无关文法$G$是一个四元组$G=(T,N,P,S)$: $T$是终结符号，对应词法单元 $N$是非终结符号集合 $P$是产生式集合\[A\in N\rightarrow \alpha\in (T\cup N)\] $A$：单个非终结符 $\alpha$：终结符与非终结符构成的串，也可以是空串 $S$为开始符号，要求$S\in N$且唯一推导推导即将产生式的左侧替换成右侧 $E\rightarrow D$ 经过一步推导得出 $E\xrightarrow{+...…
-
指针分析（三）
过程间指针分析调用图过程间的指针分析需要建立调用图。传统的CHA是根据声明类型来建立调用图，会引入大量的无用边。通过指针分析可以构建比CHA更精确的调用图和指向关系。规则r = x.k(a1,...,an)的规则为\[o_i\in pt(x),m=Dispatch(o_i,k)\\o_u\in pt(a_j),1\le j \le n\\\underline{o_v\in pt(m_{ret})}\\o_i\in pt(m_{this})\\o_u\in pt(m_{pj}),1\le j...…
-
词法分析（二）
自动机理论自动机包含状态机$S$和状态转移函数$\delta$根据计算/表达能力的不同，自动机包含多个层次。其中用于词法分析的是有限状态机。词法分析的目标是通过正则表达式RE生成确定性有穷自动机DFA，进而生成词法分析器的代码。NFA非确定性有穷状态机$A$是一个五元组$A = (\Sigma ,S,s_0,\delta,F)$ 字母表$\Sigma$ 有穷的状态集$S$ 唯一的初始状态$s_0\in S$ 状态转移函数$\delta:S\times (\Sigma \cup {\...…
-
指针分析（二）
实现指针分析实现指针分析，关键在于将指向关系在指针间进行传播。当x的指向产生变化时，将变化的部分传播给和x有关的指针。指针流图指针流图（PFG）是一个有向图，表达对象在指针间的流动。节点：指针边：$x\rightarrow y$表示指针$x$指向的对象可能会流向指针$y$（即可能被其指向） Kind Statement PFG Edge New x = new T() N/A ...…
-
IO软件
IO软件的层次结构层次结构中断处理程序位于操作系统底层，与硬件相关联。在转入中断处理程序后，检查设备状态寄存器内容，判断产生中断的原因，根据IO操作的完成情况进行相应处理。 如果数据传送出错，向上层软件报告设备的出错信息，实施重新执行 如果正常完成，唤醒等待的进程，将其转化为就绪态 如果有等待传输的IO命令，通知相关软件启动下一个IO请求设备驱动程序包括与设备密切相关的所有代码，从独立于设备的软件中接收并执行IO请求。 把用户提交的逻辑IO请求转化为物理IO操作 监督设备是否正确...…
-
IO控制方式
设备控制器IO设备中的电子部件。又称设备适配器、IO控制器、IO控制接口，简称IO模块或IO接口。设备控制器包括状态/控制寄存器、数据缓冲寄存器、地址译码器和IO控制逻辑、外设接口控制逻辑IO方式轮询方式处理器向控制器发送IO命令，重复该过程直到设备准备就绪。CPU需要等待设备，需要参与数据传送。中断方式处理器发送IO命令，然后继续执行其他质量。控制器就绪后发起中断，进行数据读写。CPU不需要等待设备，参与数据传送。DMA方式处理器向DMA模块发送IO命令，随后继续执行其他工作，DMA模块...…
-
词法分析（一）
ANTLRANTLR是常用的词法分析器生成器，通过编写包含词法规则的g4文件，便可以自动生成一个词法分析器。一个g4文件主要的词法分析相关的内容是词法规则和句法规则。其中句法规则以小写字母开头，词法规则以大写字母开头。grammar SimpleExpr;@header {package simpleexpr;}//*: 0-nprog : stat* EOF ;//'if': literalstat : expr SEMI | ID EQUAL expr SEMI | I...…
-
段式存储管理
基本思想段式存储管理基于可变分区存储管理实现，硬件增加一组用户可见的段寄存器，供地址转化使用。存储管理增加一个段表，每个段占用一个段表项，包括段起始地址、段限长、存储保护等标志位地址转换从段表控制寄存器中得到当前段表，按逻辑地址中段号查段表，得到该段的起始地址和段长。将逻辑地址中的单元号与段长比较，如果未越界，则绝对地址为起始地址+单元号。虚拟化将进程的所有段放在辅存中，根据需要装入主存。段页式存储装入部分段，或者装入段中部分页面…
-
指针分析（一）
指针分析的要素堆抽象堆抽象将无限的动态分配出的对象建模为有限的抽象对象调用点抽象目前最常见的堆抽象方式。其在每一个创建点分配一个抽象对象来代表其可能的所有具体对象。上下文敏感性上下文敏感对同一个方法的不同调用进行区分。会对一个方法的每一个调用上下文分别分析。上下文不敏感将对一个方法的所有调用归并。对每个方法都只分析一次流敏感性控制流敏感考虑语句的执行顺序。会在每个程序位置产生一个指针映射控制流不敏感不考虑语句顺序，对所有语句以无序集合处理。会为整个程序产生一个指针映射分析域全程序分析分析整...…
