数据库，简而言之可视为电子化的文件柜——存储电子文件的处所，用户可以对文件中的数据运行新增、截取、更新、删除等操作。
所谓“数据库”系以一定方式储存在一起、能予多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。一个数据库由多个表空间（Tablespace）构成。
数学建模基础（Ⅰ）
MATLAB（矩阵实验室）是MATrix LABoratory的缩写，是一款由美国The
MathWorks公司出品的商业数学软件。MATLAB是一种用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境。除了矩阵运算、绘制函数/数据图像等常用功能外，MATLAB还可以用来创建用户界面及与调用其它语言（包括C、C++、Java、Python和FORTRAN）编写的程序。
尽管MATLAB主要用于数值运算，但利用为数众多的附加工具箱（Toolbox）它也适合不同领域的应用，例如控制系统设计与分析、图像处理、信号处理与通讯、金融建模和分析等。另外还有一个配套软件包Simulink，提供一个可视化开发环境，常用于系统模拟、动态/嵌入式系统开发等方面。
From Wikipedia
另外，Matlab在上世纪七十年代前由Fortran编写，后来用C改写。
根据所用参考书将学习分为三部分，数值计算、符号计算、图形可视化。
Linux-RedHat/Debian概述
Linux 发行版（英语：Linux distribution，也被叫做GNU/Linux 发行版），为一般用户预先集成好的Linux操作系统及各种应用软件。一般用户不需要重新编译，在直接安装之后，只需要小幅度更改设置就可以使用，通常以软件包管理系统来进行应用软件的管理。Linux发行版通常包含了包括桌面环境、办公包、媒体播放器、数据库等应用软件。这些操作系统通常由Linux内核、以及来自GNU计划的大量的函数库，和基于X Window的图形界面。有些发行版考虑到容量大小而没有预装 X Window，而使用更加轻量级的软件，如：busybox, uclibc 或 dietlibc。现在有超过300个Linux发行版（Linux发行版列表）。大部分都正处于活跃的开发中，不断地改进。
由于大多数软件包是自由软件和开源软件，所以Linux发行版的形式多种多样——从功能齐全的桌面系统以及服务器系统到小型系统（通常在嵌入式设备，或者启动软盘）。除了一些定制软件（如安装和配置工具），发行版通常只是将特定的应用软件安装在一堆函数库和内核上，以满足特定用户的需求。
这些发行版可以分为商业发行版，比如Ubuntu（Canonical公司）、Fedora（Red Hat）、openSUSE（Novell）和Mandriva Linux；和社区发行版，它们由自由软件社区提供支持，如Debian和Gentoo；也有发行版既不是商业发行版也不是社区发行版，如Slackware。
LeetCode题解整理
2025-3-19
写 SSL 协议这篇博客时写到了 C++ 的 unordered_map 用的是 FNV 哈希，算是除了当年分析排序算法之外第一次试图理解 STL 的底层实现，让我回忆起 2022 年的 3 月 (25号~9月18号)，在残酷刷题群里麻木刷题时不懂底层道理只会调用 STL 的难受。在等待训练 chemprop 作为 molgen 奖励函数的时候，重新调通三年没碰的 macOS vscode cpp 工作流，试着借助 chatgpt 搞懂 STL 容器。
vector
vector 底层实现：动态数组（dynamic array，连续内存快）
C++ 的 std::vector、Java 的 ArrayList、Python 的 list 都是动态数组的实现，数组的元素在内存中是连续存储的。
时间复杂度：
- 读写：O(1)，内存中连续存储所以支持快速随机访问。
- 增删：如图所示，在元素占满数组时会开两倍内存，并把内容复制过去。O(n)。若不满：
- 尾部插入删除：O(1)。
- 中间或前部插入删除：O(n)，保持内存连续。
list
list 底层实现：双向链表（doubly linked list）
C++ 的 std::list、Java 的 java.util.LinkedList、Python 的 collections.deque（下文讲） 都是双向链表的实现。如图每个结点比单向链表多维护一个 prev 指针，因此在 O(1) 的时间内可以获取前驱结点，进而加速了插入和删除操作。
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 读写 | 由于链表不支持随机访问，必须从头或尾部遍历到目标位置 | |
| 头部插入删除（Insert or Delete at Head） | 直接修改 head 指针，不需要遍历 |
|
| 尾部插入删除（Insert or Delete at Tail） | 直接修改 tail 指针，不需要遍历 |
|
| 中间插入删除（Insert or Delete at Index k） | 需要遍历到索引 ，然后插入或删除 |
deque
deque, double-ended queue, 双端队列。
C++：std::deque（动态数组实现，写到这才发现有官方文档：https://cplusplus.com/reference/deque/ ），Java：ArrayDeque（动态数组实现）、LinkedList（实现了 Deque 接口，双向链表实现），Python：collections.deque（双向链表实现）。
着重讲一下 deque，因为 C++ 和 python 的 stack 和 queue 都是用 deque 实现的。在 C++ 里管 stack 和 queue 叫 Adaptors（适配器），指的是不直接存储数据，用已有容器（underlying container）提供新的接口，使其行为满足特定需求的特殊容器；在 python 里管 deques 叫做 stacks 和 queues 们的泛化（generalization）。
C++ 的 deque：分块（chunks）存储，每个内存块chunk都是定长的vector，用一个指针队列（map，如图所示）管理这些内存块，保持物理不连续但逻辑连续，map本身也是一个vector。deque跟vector有些像，内部结构稍微复杂一些，在存非常长的序列时deque会更高效地扩展，因为vector此时重新分配内存（reallocation, O(n)）会开销很大。
这篇文章gif失效了。
在 Python 里 deque 是用双向链表串连起内存块。3.8.1的源码在这。与之类似的 list（是C语言优化的指针数组）在增删头部（pop(0) 或 insert(0, v)）时有 O(n) 的内存移动成本，但对固定长度的快速操作做了优化。
stack
LIFO (last-in first-out)
C++有std::stack（deque的adaptor）Java有Stack<E>（Java的栈顶叫peek，C++和Python都叫top），Python里可以用list、deque模拟。
| 操作 | 时间复杂度 |
|---|---|
入栈 (push) |
|
出栈 (pop) |
|
访问栈顶 (top/peek) |
|
查找 (search) |
queue
FIFO (first-in first-out)
C++有std::queue（deque的adaptor），Java有Queue<E>，Python里提供了线程安全的队列实现。
| 操作 | 时间复杂度 |
|---|---|
入队 (enqueue) |
|
出队 (dequeue) |
|
访问队首 (front) |
|
查找 (search) |
priority_queue
priority_queue是大根堆，即每个结点的值都小于等于其父结点，堆是一棵树。
大根堆主要支持的操作有：插入一个数、查询最大值、删除最大值、合并两个堆、减小一个元素的值。
可并堆支持高效合并。
可持久化，是对任意历史版本进行查询或者操作，产生新的版本。
priority_queue往往是二叉堆，提到堆也往往指二叉堆。
下表来自oi-wiki，oi-wiki 对下面三个数据结构解释得都不错，建议直接看oi-wiki，这里只作为笔记。
操作 \ 数据结构 |
二叉堆 | 配对堆 | 左偏树 | 二项堆 | 斐波那契堆 |
|---|---|---|---|---|---|
| 插入（insert） | $O(\log n)$ | $O(1)$ | $O(\log n)$ | $O(\log n)$ | $O(1)$ |
| 查询最大值（find-max） | $O(1)$ | $O(1)$ | $O(1)$ | $O(1)$ | $O(1)$ |
| 删除最大值（delete-max） | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ |
| 合并 (merge) | $O(n)$ | $O(1)$ | $O(\log n)$ | $O(\log n)$ | $O(1)$ |
| 减小一个元素的值 (decrease-key) | $O(\log n)$ | $o(\log n)$（下界 $\Omega(\log \log n)$，上界 $O(2^{2\sqrt{\log \log n}})$） | $O(\log n)$ | $O(\log n)$ | $O(1)$ |
| 是否支持可持久化 | $\checkmark$ | $\times$ | $\checkmark$ | $\checkmark$ | $\times$ |
increase key呢？
详细复习一下七年前学的二叉堆和二叉搜索树：
Why is Binary Heap is better than BST for Priority Queue?
What is the underlying data structure of a STL set in C++?
玩熟练这下面这仨复杂高效的 STL 容器的数据结构（二叉堆、二叉搜索树（→二叉平衡树→红黑树）、哈希桶）基本就对算法题的数据结构得心应手了吧。
二叉堆Binary Heap
二叉搜索树Binary Search Tree
map
红黑树
unordered_map
哈希表
set
红黑树
unordered_set
哈希表
附图
肄业倒计时
今天交完房租，结束了在这个出租屋的第 25 个月。感谢邻居早 8 点准时响起的电钻，把我赶来北街咖啡，赶来大食堂。无论是以前还是现在，在家里一个人呆着只会让我腐烂发臭，turn into the Rotten of Black Gulch。
肄业(yì yè, Dropping Out)，肆业(sì yè, 勤于所业)。根据汉典，肄的意思有：「肄，習也。」「肄，嫩條也。」「肄，勞也。」算是个“退学”的仁慈版本。
By all means marry. If you get a good wife, you’ll be happy. If you get a bad one, you’ll become a philosopher. (Socrates，苏格拉底有个好老婆还是坏老婆呢)
