ZingLix 空间

动态规划

Dynamic Programming

动态规划与分治类似，都是通过拆分成子问题再组合来得到结果，但是分治将问题划分成了互不相关的子问题，而动态规划适用于子问题重叠的情况。动态规划通常用来求解最优解。原理对于适用于动态规划的问题，要求其满足最优子结构和子问题重叠两个要素。最优子结构最优子结构指的是对于一个规模的最优解，其包含的每个子问题都是最优解。有了这一性质就保证了我们可以先求解子问题的最优解，再用它来构...

Posted by ZingLix on November 25, 2018

8086 汇编指令集整理

8086 Assembly Instrution Cheatsheet

数据传送指令通用数据传送指令 MOV 格式：MOV dst,src 功能：将src传送到dst 限制：段寄存器间不可直接相互传送，立即数不能直接送段寄存器，CS 不可作为目的操作数。 PUSH & POP 格式：PUSH src & POP dst 功能：将 src 压栈 & 出栈送入 dst 限制：CS 不可作目的操作数 ...

Posted by ZingLix on October 14, 2018

「OS」内存管理和虚拟内存

Memory Management & Virtual Memory

内存是计算机中一个重要的资源，需要被认真管理。理想的存储器是私有的、容量无穷的、速度极快的的且非易失的，不过显然这样的存储器是不存在的，但是人们提出了分层存储器体系使得我们可以近乎得到这个理想存储器。在这个体系中，越接近 CPU 的容量越小但速度更快且易失，越远离的容量越大速度更慢但非易失。一般来说只有相邻的两层间会有数据交换。通过这一体系能保证有足够容量存储数据，在被使用时一步...

Posted by ZingLix on October 13, 2018

STL 解析 —— 无序关联容器

Unordered Associative Containers

从 C++11 开始，标准库中对于关联容器进行了扩充，提供了基于哈希表实现的关联容器。哈希表会占用比存储的元素更多的内存，换来的是均摊 \(O(1)\) 的性能。哈希表之前有过对于哈希表的详细介绍，所以本文更侧重于实现解决冲突的策略有很多，标准库中选择使用分离链接法，即冲突的元素都会被放在一个位置，用一个链表存储。数据结构这里将哈希表中每个元素称为一个...

Posted by ZingLix on September 29, 2018

STL 解析 —— 关联容器

set、map、multiset & multimap

关联容器中最为常用的是 map，是一个存储键值对（key-value）的数据结构，提供 key 可以在 \(O(logN)\) 的时间内得到 value，因此称为关联容器（Associative containers）。除了 map 外，关联容器中还有 set，行为与 map 类似但是只存储键。这两个不允许键重复，所以标准库为还提供了允许键重复的 multiset 和 multimap。...

Posted by ZingLix on September 27, 2018

STL 容器底层实现总结

顺序容器、关联容器及容器适配器

顺序容器可顺序访问的数据结构。容器数据结构 vector 数组 deque 数个缓冲区相接，由一个中央控制器管理 list 双向链表比较随机访问 ...

Posted by ZingLix on September 20, 2018

算法复杂度和渐进符号

Θ()、O()、Ω()

在分析算法性能的时候，通常有空间复杂度和时间复杂度两个维度，前者考虑的是对于存储空间的占用，后者考虑的是算法完成所需要的时间，在分析时候有许多记号用于不同需求时的表示。通常来说复杂度与输入的规模有关，下文中 n 均表示输入规模。 Θ 记号 \(\Theta (g(n))\) 用来表示一类函数 \(f(n)\) ，存在 \(c_1、c_2\) 和 \(n_0\)，使得对于所有 \(n ...

Posted by ZingLix on September 20, 2018

ICMP 因特网控制报文协议

Internet Control Message Protocol

ICMP 是用来给主机与路由器间沟通网络层信息的协议，用来弥补 IP 协议本身并未提供能诊断发送失败的功能这一缺陷，是网络层三个重要组件之一。最常见的用途是差错报告，例如在传输数据时在某一个结点发生了问题，此时该结点路由器就可以返回一个 ICMP 差错报文，发送方收到该报文时就可以针对该错误作出相应处理。封装 ICMP 报文封装于 IP 数据包中。通过 IP 数据报中协议字...

Posted by ZingLix on September 15, 2018

MIT 6.828 Lab 1 学习笔记

Part 1: PC Bootstrap 这一部分是为了引入 x86 汇编语言和了解 PC 的启动过程。相比较于直接运行在真机上，整个 Lab 都选择在一个叫 QEMU 的模拟器上进行。根据其指引编译，可以获得下图，代表编译成功。 PC 物理地址空间第一台 PC 搭载的是 Intel 8088，寻址范围只有 1MB。其中有 384KB 被保留用于特定用途，例如显示输出的缓冲和...

Posted by ZingLix on August 29, 2018

DHCP 动态主机配置协议

DHCP 可以实现网络的自动配置，对于一些客户会频繁出入的场景有不可或缺的作用。地址池和租用 DHCP 服务器从一个地址池中分配 IP 地址，提供的地址只能有效一段时间，称为租用期，这样可以避免客户离开网络但仍占用地址，导致地址池枯竭。当然客户机能够提出续租的请求，所以对于长期在网络中的客户机没有更换 IP 地址的问题。租用期常见为 12-24 个小时，过长的时间会导致地址池...

Posted by ZingLix on July 28, 2018

ZingLix Blog