幻影彭的彩虹

Hello World

发表于 2022-07-12 更新于 2025-02-16

~~在无数久的 🐦咕咕咕后一个博客它建成了！~~

在无数久的 🐦咕咕咕后这个博客它复活了！

博客主要会收录这些东西：

OI/ACM 相关
- 考试技巧
- 题解
- 算法理解
学习笔记
面向各种人群的科普
我的开源项目
生活中有趣的事
一些奇思妙想

我是谁：

如果你线下认识我，可以叫我 "毛Ker" 或者 "老毛"
如果你线上认识我，可以叫我 "彭彭"。
这些 ID 都是我：huan-yp，幻影彭，huan_yp，huan_yp2002。

联系我：

QQ：3051561876

关于日志

有些事情单独开一篇博客太浪费，但是确实不得不记录一下，所以有了这个日志。目前打算是按月开。

VSCode 远程连接到服务器上开发卡死

不要连接到东西太多的目录，有些插件会扫目录，消耗巨大多内存。

建议是单独开一个 workspace 来干活。

另外远程服务器起码有 4GB 内存，2GB 内存纯属冤大头。

Python slots

Python 的 __slots__ 机制，可以限制实例的属性，只允许在创建实例时定义的属性，不允许动态添加属性。

如果尝试为没有在 slots 中声明的变量赋值，会引发 AttributeError。

git 拉取远端其它分支并与本地关联

1	git checkout -b feature-branch origin/feature-branch

git 删除分支

删除本地分支：

1	git branch -d feature-branch

删除远端分支：

1	git push origin --delete feature-branch

Python lambda 闭包问题

lambda 做函数绑定的时候变量是绑定到域上的变量的，而不是绑定到值上的。

例如下面循环的例子：

funcs = []
for i in range(10):
    funcs.append(lambda x: x + i)
print(funcs[0](10))

输出是 19，而不是 10，因为查找到的 i 是循环结束后域里面的 9。

正确的做法是：

funcs = []
for i in range(10):
    funcs.append(lambda x, i=i: x + i)
print(funcs[0](10))

C++ 全局变量的声明和定义

全局变量的声明和定义是分开的，声明是在 .h 中使用 extern 关键字，定义是 .cpp 中使用 = 赋值。

另外就算是用了 #ifdef XXX_H，也不能在 .h 里面定义。不然多个 .cpp 都包含了 .h，还是分开编译的，就会报重定义的错误。

类的静态成员变量是不允许在声明的时候初始化的，只能定义的时候初始化。

Python 线程独立资源

有时候每个线程需要一些独立的资源来执行一些操作，这个可以用 threading.local() 来实现。

一般需要配合 concurrent.futures 的线程池来使用。


def initializer():
    """初始化线程独立资源"""
    driver = uc.Chrome(use_subprocess=True, options=options, driver_executable_path=DRIVER_PATH)    

def exact(i):
    """任务"""
    driver.get(url)

def crawler():
    global driver_pools
    driver_pools = threading.local()
    with concurrent.futures.ThreadPoolExecutor(max_workers=5, initializer=initializer) as executor:
        # 提交任务
        futures = [executor.submit(lambda i=i: exact(i)) for i in range(1, 100)]
        # 等待任务完成
        for future in concurrent.futures.as_completed(futures):
            future.result()

Python 异步任务、线程任务

这两个任务一般来说只要开始阻塞执行后，都没办法强制中止的。

后台多线程任务可以设置成 daemon=True，关闭主程序的时候自动关闭后台任务。

异步任务一般要避免出现阻塞，否则主线程会卡死。

另外如果一定要强行中止线程，可以考虑 concurrent.futures 的 ThreadPoolExecutor._threads.clear 方法。

Python Queue

线程安全的 Queue.get 在使用的时候不管是不是保证有东西，最好都加点 timeout。

nullptr 和 iterator::end()

处理指针类型一定要想好有没有可能是 nullptr。

处理迭代器的时候一定要想好有没有可能是 end()。

C++ 容器

迭代的时候别TM的做删除操作，会漏内存。

git 设置代理

有时候 git 走不了系统代理，可以配置一个全局的代理设置：

1 2	git config --global http.proxy http://127.0.0.1:7890 git config --global https.proxy http://127.0.0.1:7890

C++ iostream

istream 和 ostream 是两个抽象类，不能直接实例化，用的时候应该把一个 ifstream 或者 ostream 的子类实例化，然后绑定到 istream 或者 ostream 上。

cerr, cout 这些都是 ostream 的子类，所以有时候

1 2	ifstream fin("in.txt"); istream &in = fin;

C++ Fsanitize

不要开 O2 优化，开了就定位不了错误。

VMWARE 无法打开内核设备

对应虚拟机 .vmx 文件中，将 vmci0.present 改为 "FALSE"

Win11 自定义快捷键反应慢

参考

就是开始菜单 (建议 Win+Q 搜索 设置)找到 "设置", 点击 "应用设置", 把 "后台组件权限" 改为 "从不" 即可。

左偏树的指针实现——C++移动语义的实例

发表于 2025-03-31 分类于技术

简介

左偏树是一种可并堆，核心操作是 $O(\log{n} + \log{m})$ 的 merge 操作。

通过 merge 操作来实现 push 和 pop 操作。

基本信息

左偏树的结构是二叉树。
每个节点具有一个额外属性 dist。定义一个节点是边缘节点，当且仅当它的儿子个数不为 2。dist 表示该节点往儿子方向走，走到边缘节点需要经过的最小边数，空节点 dist 定义为 -1。
左偏树每个节点的左子树的 dist 不小于右子树的 dist，所以显然有 dist = right_son->dist + 1。

算法流程

push

创建一个新的堆，只分配一个节点，将新堆合并进原有堆。

pop

原有根节点删去，合并其左右儿子，得到新的根节点。

merge

找到根节点 val 较小的那个堆，将它的根节点作为新堆的根节点，它的左儿子作为新堆的左儿子，它的右儿子和另一个堆合并，作为新堆的右儿子。
合并时遇到一个堆为空时，非空堆即合并结果，可以直接返回。
如果合并后右儿子的 dist 大于左儿子的 dist，交换两个儿子。

复杂度分析

结论：

push：$O(\log{n})$
pop：$O(\log{n})$
merge：$O(\log{n} + \log{m})$

证明：

若一个节点的 dist 为 $x$，则它及其子树至少有 $2^x$ 个节点。故 dist 的值是 $O(\log{n})$ 级别的。
进行合并时，每递归一层，参与合并的两个堆的 dist 之和减少 1，故递归层数为 $O(\log{n} + \log{m})$。

实现

结构

一个内部的类 Node 表示左偏树的一个节点，包含 dist，val 两个变量，以及 son[0], son[1] 两个指针，分别指向左儿子和右儿子。
一个类 Heap，表示一个堆，包含一个 Node 指针，表示根节点。

声明

这里希望练习使用 C++11 中的智能指针和移动语义，所以声明为：

class Heap{
private:
    class Node{
    public:
        unique_ptr<Node> son[2];
        int val, dist;
        Node(int val=0){
            this->son[0]=nullptr;
            this->son[1]=nullptr;
            this->val=val;
            this->dist=0;
        }
    };
    unique_ptr<Node> root;
public:
/*
    其它部分暂时省略
*/
};

构造函数

class Heap{
    Heap(unique_ptr<Node> root){
        this->root=move(root);
    }
};

通过传入一个 unique_ptr<Node>，构造一个 Heap 对象。

unique_ptr 是一种智能指针，它指向的对象是它独享的，不能被其它东西访问。

unique_ptr 仅支持移动语义，这用于转移对象的所有权，对象所有权转移后，原来的 unique_ptr 将失效。

unique_ptr 不支持拷贝和赋值操作，所以上面的构造函数严格来说是有问题的，如果传入的 unique_ptr 不是右值则会尝试调用不存在的拷贝构造函数，导致编译错误。故应该将参数声明为右值引用(注意区分右值引用和常值引用)。

具体如下：

class Heap{
    Heap(unique_ptr<Node> &&root){
        this->root=move(root);
    }
};

至于为什么第一份代码是正确的，是因为只要保证传入的 unique_ptr 是右值，编译器就会优先自动调用移动构造函数，所以不需要在调用函数时显式地写出 move。

至于为什么第二份代码中右值引用的 root 仍然需要使用 move 来显式的转化为右值，这是因为右值在绑定到一个右值引用后，其本身在作用域内是一个具名变量，行为会退化退化为左值。，故需要显式的使用移动语义来调用移动构造函数。

merge

class Heap{
    Heap& merge(Heap &&other){
        if(root==nullptr){
            root=move(other.root);
        }
        else if(other.root==nullptr){

        }
        else{
            if(root->val > other.root->val){
                swap(this->root, other.root);
            }
            root->son[1] = move(Heap(move(root->son[1])).merge(move(other.root)).root);
            if(root->son[0] == nullptr || 
                (root->son[1] != nullptr && root->son[0]->dist < root->son[1]->dist)){
                swap(root->son[0], root->son[1]);
            }
            if(root->son[1] != nullptr)
                root->dist = root->son[1]->dist + 1;
            else
                root->dist = 0;
        }
        return *this;
    }
};

merge 返回一个左值引用是为了方便链式调用。

有几个细节：

swap: 可以用于交换 unique_ptr, 它应该是实现了这种移动语义的交换。
隐式构造: Heap(xxx).merge(move(other.root)).root 这里使用了隐式构造，Heap.merge 支持的参数是一个右值的 Heap，传入时传的一个右值的 unique_ptr，由于定义了右值 unique_ptr 到 Heap 的构造函数，这里直接隐式调用了构造函数，构造了一个右值的 Heap 并作为参数传递给了 merge。
返回左值引用: return *this 返回左值引用的目的是方便链式调用，至于为什么临时构造的 Heap 能返回一个左值引用，是因为临时对象的生存周期是到表达式结束为止，而临时对象在生命周期内可以被左值引用。

push && pop && top

class Heap{
    int top() const{
        return root->val;
    }
    void push(int x){
        this->merge(unique_ptr<Node>(new Node(x)));
    }
    int pop(){
        this->root = move(Heap(move(root->son[0])).merge(move(root->son[1])).root);
        // 当 merge 函数返回时, 它返回的是临时对象的左值引用, 临时对象在生命周期内可以被左值引用.
        return top();
    }
};

比较简单, 不解释了.

左值右值的理解

简单的说：

右值是只能放到表达式右边的值，左值是既能放到表达式右边，也能放到左边的值。
右值一般是没有命名的值，左值一般是有名字的值。
右值是临时的值，左值是持久的值。

更具体一点：

左值的特性

有固定内存地址：左值通常存储在堆或栈上，可以通过取地址操作符（&）获取其地址。
可以被多次访问：左值的生命周期较长，可以在多个语句中被访问。
可以被修改：左值通常可以被修改，例如变量赋值操作。

右值的特性

没有固定内存地址：右值通常是临时对象，没有固定的存储位置，或者其存储位置在表达式结束后立即失效。
不能被取地址：右值不能使用取地址操作符（&）获取其地址。
不能被多次访问：右值的生命周期仅限于当前表达式，不能被多次访问。
通常不可修改：右值通常是不可修改的，因为它们是临时的。

右值举例

C++ 的值除了右值就是左值，下面几个右值的例子：

函数的返回值是一个右值。
字面量，10, "hello" 是右值。
临时对象是右值，例如 c = a + b; 中的 a + b 这个整体。

下面是左值的例子：

命名变量名是左值，例如 int a = 10; 中的 a，a = b = c = 10; 的 a, b, c 都是左值。

左值引用和右值引用

名词解释

int a = 10; // 左值 被赋值为 右值 , a 是左值, 10 是右值.
int &&x1 = 10; // 右值引用 绑定到 右值, x1 是右值引用, 10 是右值, 允许.
int &&x2 = a; // 右值引用 绑定到 左值, x2 是右值引用, a 是左值, 允许, 一般用于模板编程.
int &y = a; // 左值引用 绑定到 左值, y 是左值引用, a 是左值, 允许.
int &y1 = 10; // 左值引用 绑定到 右值, y1 是左值引用, 10 是左值, 编译错误.
int &y2 = x1; // 左值引用 绑定到 右值引用, y2 是左值引用, x1 是右值引用, 编译错误.
int &&z1 = y; // 右值引用 绑定到 左值引用, z1 是右值引用, y 是左值引用, 允许, 并且, 支持引用折叠语法, 所以 z1 的实际行为是左值引用.
int &z2 = z1; // 左值引用 绑定到 可折叠为左值的 右值引用, z2 是左值引用, z1 是右值引用, 但可折叠到对 a 的左值引用, 允许.
int &z3 = x2; // 左值引用 绑定到 可折叠为左值的 右值引用, z3 是左值引用, x2 是右值引用 但可折叠到对 a 的左值引用, 允许.

右值引用的特性

右值引用似乎是命名变量吧？

所以：右值引用可以在不发生内存操作的前提下将临时右值变为左值，可以延长右值的生命周期，降低读写内存的开销。

左值引用的特性

左值引用等价于为变量取了一个别名。

特别的，在函数传参如果使用左值引用传参，函数类通过左值引用可以修改原变量的值。

引用折叠

在不发生编译错误的情况下, 可以支持引用折叠, 名词解释中的 z1, z2, z3 例子解释了这个特性。

具体的，在发生多次引用绑定时，按照以下规则折叠：

左 + 左 = 左
右 + 左 = 左
左 + 右 = 左
右 + 右 = 右

完整代码

#include "bits/stdc++.h"

using namespace std;

class Heap{
private:
    class Node{
    public:
        unique_ptr<Node> son[2];
        int val, dist;
        Node(int val=0){
            this->son[0]=nullptr;
            this->son[1]=nullptr;
            this->val=val;
            this->dist=0;
        }
    };
    unique_ptr<Node> root;
public:
    Heap(unique_ptr<Node> &&root){
        this->root=move(root);
    }
    int top() const{
        return root->val;
    }
    void push(int x){
        this->merge(unique_ptr<Node>(new Node(x)));
    }
    Heap& merge(Heap &&other){
        if(root==nullptr){
            root=move(other.root);
        }
        else if(other.root==nullptr){

        }
        else{
            if(root->val > other.root->val){
                swap(this->root, other.root);
            }
            root->son[1] = move(Heap(move(root->son[1])).merge(move(other.root)).root);
            if(root->son[0] == nullptr || 
                (root->son[1] != nullptr && root->son[0]->dist < root->son[1]->dist)){
                swap(root->son[0], root->son[1]);
            }
            if(root->son[1] != nullptr)
                root->dist = root->son[1]->dist + 1;
            else
                root->dist = 0;
        }
        return *this;
    }
    int pop(){
        this->root = move(Heap(move(root->son[0])).merge(move(root->son[1])).root);
        // 当 merge 函数返回时, 它返回的是临时对象的左值引用, 临时对象在生命周期内可以被左值引用.
        return top();
    }
};

int main(){
    Heap h(nullptr);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        int tp, x;
        cin >> tp;
        switch (tp){
            case 1:
                cin >> x;
                h.push(x);
                break;
            case 2:
                cout << h.top() << endl;
                break;
            case 3:
                h.pop();
                break;
            default:
                throw "unsupported operation";
        }
    }
    return 0;
}

C-malloc 简介

发表于 2025-03-11 分类于技术

C 使用 malloc() 和 free() 来动态分配和释放内存，C++ 使用 new 和 delete 来动态分配和释放内存。

C 管理数据的方式

malloc && free

malloc 的时候，会在堆上分配一块内存，然后返回一个指向这块内存第一个位置的指针。同时会记录一个 metadata，存储数据大小和分配状态等信息。

malloc 分配内存初值是随机的，需要手动初始化。

当使用 free 释放内存时，会检查 metadata，根据 metadata 决定所要释放数据的大小。

metadata 的存储位置一般在首地址之前，因此 free 的时候必须 free 首地址。

结构化数据

用 struct 之类的结构体来管理数据时，指针类型直接指示了应该如何处理内存中的数据。

C++ 管理数据的方式

new && delete

直接 new 一个数据类型，比如 new int，不会设置 metadata，而是直接使用指针类型来管理内存大小，并根据指针类型调用对应构造函数来初始化数据。

new 的数据必须通过 delete 来删除，并且必须显式指定指针类型，因为 delete 不仅需要指针类型指示的内存大小，还会调用对应析构函数来释放内存。

new [] && delete []

new [] 会分配一块连续的内存，然后返回一个指向这块内存第一个位置的指针。同时会记录一个 metadata，存储数据大小和分配状态等信息。new [] 分配时会调用对应构造函数来初始化数据。

delete [] 会检查 metadata，根据 metadata 决定所要释放数据的大小。delete [] 会调用对应析构函数来释放内存。

软件级应用的编译

发表于 2025-03-09 分类于技术

软件级是相对于程序级的概念，软件级应用往往包含多目录多文件的大量源代码，有复杂的第三方库依赖关系。

软件级应用的编译用时往往较长，并且过程相对繁琐。

我们这里介绍使用 MinGW 系列工具和 CMake 编译 cpp 软件级应用的过程和知识。

各种文件

CMakeLists.txt

CMakeLists.txt 一般用于跨平台的大型软件级项目，用于指示 CMake 生成平台对应的编译选项，也就是 Makefile 文件。

Makefile

Makefile 文件指定 make 工具编译生成 include/，lib/，bin/ 等成品的方式，我安装的是 MinGW套件，命令是 mingw32-make。

.dll/.so

这两个是动态链接文件，.dll 是 Windows 下的，.so 是 Linux 下的。

MinGW 默认是动态链接的，编译生成的 .exe 如果找不到 .dll 就运行不了。

.dll 或者 .so 默认只会在系统路径和工作目录两个地方去找

.o

.o 是可重定向目标文件，是汇编过程生成的源文件机器语言代码。

.a

.a 是静态链接归档文件，如果采用静态链接的方式编译，就需要在编译时加上这个。

它等价于把若干个 .o 打包在了一起。

C++ 编译速通

编译步骤：

预处理：把 #include 的东西全部粘贴到对应的位置，由 .cc，.cpp 生成 .i，.ii 预处理文件。
编译：编译器用 C/CPP 代码生成汇编代码，由 .i，.ii 生成 .s 汇编文件。
汇编：由汇编器将汇编代码编程二进制代码，由 .s 生成 .o 目标文件。
链接：由链接器把汇编的机器代码 .o，打包的静态链接库 .a，动态链接库 .

静态链接和动态链接的区别：

静态链接在编译时便将中的实现放入了 .exe 文件，在运行 .exe 时就将代码放入内存。
动态链接在运行时才去 .dll 中查找实现，并在调用对应函数时将这部分代码放入内存。

无论是静态链接还是动态链接，编译时都需要指定链接库。静态和动态的区别在于将对应代码加入内存的时间。

实现通常写在 .cpp 文件中，定义通常写在 .h 文件中，#include 时一般只会 #include .h 文件，所以如果编译时不指定链接库，链接步骤就会报 Undefined Refference 错误。

GNU-make 工具的使用

类 UNIX 环境下它叫 make，但是我们用的 MinGW，反正我这里叫 mingw32-make，路径是 path/to/mingw64/bin/mingw32-make.exe ，使用时记得加环境变量。

make 和 Makefile 结合，执行一些特定的命令，完成项目的编译，避免手敲 gcc 命令。

命令格式：

1	[mingw32-]make [<目标>] <可选参数...>

常用可选参数：

-n：不执行，只打印要执行的命令。
-f：指定 Makefile 的路径，默认情况下 Makefile 的（相对）路径为 Makefile 或 makefile。
-j[<num>]：多线程编译，例如 -j4 表示四线程编译。

目标是指 make 要执行的具体任务，如果没有指定目标，那么会执行第一个非伪目标。

Makefile 解读

一般情况下需要我们写 makefile 的机会不是很多，会读和改就可以了。

变量操作

<VAR_NAME> ?= <EXPR> 条件赋值，如果还没定义这个变量才赋值，规则同递归赋值。
<VAR_NAME> = <EXPR 递归赋值计算，每次使用时重新计算。
<VAR_NAME> := <EXPR 立即赋值计算，只计算一次。
$(<VAR_NAME>)：引用变量。

目标

目标的格式是 <target>:[<dependencies>]。

当 make 执行某个目标时，会对依赖项进行检查，如果依赖项对应的文件不存在，则会将先执行依赖的名字对应的目标。

例如：

foo: foo.o
	gcc -o foo foo.o
foo.o: foo.c
	gcc -c foo.o foo.c
	echo "compiled foo.o"

执行 make 时，过程如下：

没有指定目标，会找到第一个目标 foo 执行。
查找其依赖 foo.o，发现不存在，于是查找目标 foo.o。
找到 foo.o 其依赖 foo.c 作为一个文件存在，于是执行 gcc -c foo.o foo.c 编译生成 foo.o。
返回 2. 中步骤，依赖 foo.o 已经存在，执行 gcc -o foo foo.o 生成 foo[.exe]。

目标规则

有时候可能有很多文件，某些文件的生成方式，例如 .o，是一致的，这时可以利用目标规则来定义目标。

查找目标时，规则优先级为：越具体越优先。

目标规则大致分为三种：

显式目标规则

见上。
显示模式规则

显式模式规则使用通配符 % 来匹配任意字符，包括目录分隔符。其余同上。

下面的 $< 和 $@ 是自动变量，下面的部分有详细解释。
1
2
3
%.o: %.c
echo "Using generic rule"
gcc -c $< -o $@
隐式模式规则

隐式规则模式用于指定生成对应后缀名的文件，常见的有：
- .c.o: 从 .c 文件生成 .o 文件。
- .cpp.o: 从 .cpp 文件生成 .o 文件。
- .cpp.exe: 从 .cpp 文件申城 .exe 文件。

伪目标

一般情况下，目标会作为一个文件，通过判断文件是否已经生成来判断是否已经完成该目标。

但是，如果修改了 .cpp 源代码，但是 makefile 中有生成 .o 的过程，.o 还被保留了，那么再次 make 的时候检测到 .o 已经存在，只会用已经存在的 .o 重新链接生成一次可执行文件，没有达到重新编译的效果。所以，往往需要定义一个"清理操作"，来清理相关的文件以便重新完整编译。

"清理操作" 显然不生成文件，为了完成这个操作，引入了 "伪目标" 概念，伪目标在文件开头用 .PHONY 声明，例如：

.PHONY: clean
all: clean foo.o
  g++ -o foo foo.o
foo.o: foo.c
  g+++ -c foo.o foo.c
clean:
  rm *.o

这样便可以在每次执行 make 时清理缓存的 .o 文件达到重新编译的效果。

提醒：

伪目标表示一个过程，作为依赖时一定会被执行，如果执行返回代码为 0 才判定为完成，否则判定为没有完成，可能报错。
严格来说 all 也应该被定义为伪目标，实际上由于不会生成 all 文件，也就无所谓，clean 有时候不会被声明为伪目标。
make 不指定目标时，如果存在非伪目标，那么执行第一个非伪目标，否则仍然执行第一个目标。

自动变量

自动变量是执行规则时根据上下文动态生成的变量。

常用自动变量表如下：

$@
- 含义：表示当前规则的目标文件（Target）。
- 用途：常用于指定输出文件名。
- 示例：
  1
  2
  foo.o: foo.c
  gcc -c foo.c -o $@
  如果目标是 foo.o，$@ 的值就是 foo.o。

$<
- 含义：表示依赖列表中的第一个依赖项。
- 用途：常用于单个依赖项的场景，例如编译 .c 文件时指定源文件。
- 示例：
  1
  2
  foo.o: foo.c header.h
  gcc -c $< -o $@
  如果目标是 foo.o，$< 的值是 foo.c。

$^
- 含义：表示依赖列表中的所有依赖项（以空格分隔）。
- 用途：常用于需要处理多个依赖项的场景，例如链接多个对象文件。
- 示例：
  1
  2
  foo: foo.o bar.o
  gcc -o $@ $^
  如果目标是 foo，$^ 的值是 foo.o bar.o。

CMake 系列工具使用

不同平台使用的编译工具不一定相同，有时候根据实际情况，也可能会选择性编译整个项目的一部分。如果只提供 Makefile 可能不方便。这个时候可以利用 CMake 系列工具和 CMakeLists.txt 来根据具体需求生成特定的 Makefile。

CMake 工具可以在这里下载。

检查一个项目根目录是否包含 CMakeLists.txt 以便确认它是否支持使用 CMake 系列工具。

CMake-GUI 有个 Bug，详见。

下面是 CMake 的 UI：

配置源代码和构建路径

两个位置需要填写源代码目录（包含 CMakeLists.txt）和构建目录（自己创建一个）。

Configure

点击 Configure，会先让你选编译器之类的：

我们用 MinGW，翻一下找到选上就行，点 Finish 会自动读取所需配置项，读完之后你可以用 UI 界面方便的对它们进行改动。

Configure 过程也会读取平台信息等，大型项目 Configure 用时会很长。

如果改动了配置，需要再点一次 Configure。

由于 CMake 缓存相关的问题，如果第一次 Configure 爆红，也需要再点 Configure 一次解决问题。

Generate

完成 Configure 后，点 Generate，会在 build 目录生成 Makefile 和所需要的文件，在 build 目录执行 make 命令即可。

直接编译

gcc

命令格式：

1	gcc <功能参数> [主参数...] [包含目录参数...] [链接目录参数...] [链接参数...] [编译选项...]

功能参数
- -o：完成链接停止。
- -c：完成汇编停止。
- -s：完成编译停止。
- -E：完成预处理停止。
主参数

主参数用于指定执行这次操作所需的各种文件的位置，包括 .cpp 文件、.a 文件、.o 文件等，如果这里没有显式指定，可以通过下面的参数补充指定。
包含目录

包含文件不能在主参数部分指定，必须位于包含文件搜索目录下。

#include 除了在工作目录和系统路径搜索之外，还可以使用多个 -I path\to\include 来指定包含文件搜索目录。
链接目录

使用 -L 参数指定链接搜索目录，需要和链接参数配合使用。
链接参数

使用 -l 参数，语法规则为 -l[链接名]（注意没有空格），优先链接到链接目录下动态链接文件 /path/lib[连接名].dll 文件。如果不存在动态链接，则会链接到静态链接文件 /path/lib[链接名].a 文件。

链接库可以在主参数中直接指定，写它的路径即可。

例如 -L ./lib/ -lzlib 等价于主参数中添加 ./lib/libzlib.dll 或者 ./lib/libzlib.a。
编译选项
- --static：强制使用静态链接。
- -O2：开启 O2 优化。
- -g：生成调试符号表启用 gdb 调试功能。
- -Wl,-rpath,<path/to/dll>：指定运行时链接搜索目录，运行时最优先到 path/to/dll 去搜索 .dll 文件，一般使用相对路径

示例（我使用了 [] 和 () 来划分部分，实际使用时需要去掉）：

[g++](命令) [-o main.exe](功能参数) [cli/main.cpp resource.o](主参数) [-I "C:\Users\huany\Desktop\work_space\ziptools-install\minizip-install\include" -I "C:\Users\huany\Desktop\work_space\ziptools-install\zlib-install\include"](包含目录) [-L "C:\Users\huany\Desktop\work_space\ziptools-install\minizip-install\lib\" -L "C:\Users\huany\Desktop\work_space\ziptools-install\zlib-install\lib\"](链接目录) [-lminizip -lzlibstatic](链接参数) [-fpermissive --static](编译选项)

ar

使用 ar 工具将多个 .o 文件打包成一个 .a 静态库文件。例如：

1	ar cr libmylib.a file1.o file2.o

这里，libmylib.a 是生成的静态库文件名，file1.o 和 file2.o 是输入的目标文件。

动态链接

我觉得自己造的轮子就没必要搞动态链接了，全静态吧。想起来我再补上。

软件的发布

发布 .cpp 编译生成的 .exe 软件时，需要考虑到用户的机子上没有运行环境的事实，一般采用两种方式：

全静态链接 --static。
同时发布所需的 .dll 文件，放在 .exe 同级目录下或者使用 -rpath 编译参数。
折中。

练习——Windows 编译 OpenCV

OpenCV 是使用最为广泛的计算机视觉库，编译文档十分完善，也有数量可观的资料可供查询。但 OpenCV 体型巨大，编译用时较长。

OpenCV源码

编译完成后应该得到以下文件：

包含目录 include/
静态链接库 lib/
动态链接和其它二进制文件库 bin/

练习——Windows 系统编译 minizip

minizip 是 zlib 库的一个子库，能够支持压缩和解压。minizip 目前已经放弃维护，相比成熟的 OpenCV，可能需要修改一些编译命令才能完成编译。

你需要完成 minizip 和 zlib 的编译，得到以下文件：

zlib 的包含目录 include/ 和静态链接库 lib/。
minizip 的包含目录 include/ 和静态链接库 lib/。

提醒：

注意，官方的 makefile 中可能没有生成目录的步骤，你可能需要手动创建目录或者更改 makefile。
minizip 的 makefile 无法针对 windows 使用，请自行排查其错误并进行修改后完成编译，或者使用 g++ 手动编译生成有关文件。
你可以用 CMake 完成 zlib 的编译，也可以阅读下面文档手动编译：

To compile all files and run the test program, follow the instructions given at the top of Makefile.in. In short "./configure; make test", and if that goes well, "make install" should work for most flavors of Unix. For Windows, use one of the special makefiles in win32/ or contrib/vstudio/ . For VMS, use make_vms.com.
minizip 源代码位于 zlib/contrib/minizip/，请自行解读代码结构并进行操作。注意其依赖的 zlib 相关的配置。

大练习——编译 NcatBot 发行包

背景简介

ncatbot 旨在让用户无门槛使用，开发者只关注业务代码，提供了一个 windows 平台下的 .exe 安装部署工具。

该工具只包括一个 main.exe 主程序，能够无下载过程的配置基础 Python 环境，并安装 ncatbot 本体，调用 ncatbot-cli 完成后续交互。

相应的代码 main.cpp，Python 环境压缩包 package.zip 都已经给出，请编译出可执行文件 main.exe。

有关资源

指示

main.cpp 开头部分含有编译命令，参考这一部分编译命令，你需要完成如下工作：

完成 zlib，minizip 的编译。
完成 package.zip 的编译。
正确书写设置 zlib，minizip 的路径和编译命令。
编译 main.cpp 并链接其它上述资源。

在 NcatBot-Release 中含有编译好的 zlib，minizip，package，如果你实在无法完成这些部分，可以下载使用并完成接下来的部分。

附录

命令格式书写语法

这是一种约定俗称的记号，而不是一个严格规范，每位开发者使用的书写方式不一定相同，也不会特意严格按照要求书写，下面给出我的习惯记号。

[EXPR]：表示这一部分是可选的。
- [mingw32-]make：可能是 mingw32-make 或者 make。
- 有些人也会写成 ()，但一般不会写成 <>。
<VAR>：表示一个变量，需要根据实际情况更改。
- 有时候你会明显感觉到不用 <> 包起来也表示一个变量，自己灵活处理，例如 path/to/zlib/ 可能表示 C:/Program Files(x86)/zlib/。
- 有时候也会写成 []。
<VAR...>：表示这里的参数个数是动态变化的，每个参数用空格分隔，可以是 0 个。
- <编译选项...> 可能表示 -O2 -fpermissive 或者 -O2 --static 或者 --static 或者啥都没有。
- 有时候也会写作 [VAR...] 或者 [<VAR>...]。

折腾 vmware

发表于 2025-03-01 更新于 2025-03-11 分类于技术

折腾 vmware

ubuntu24.04 环境。

config apt source

打开 /etc/apt/source.list.d/ubuntu.sources，在 URIs 一项中，http://archive.ub.... 前面加上 .cn，也就是 https://cn.archive.ub....。

第二项那个 security 不用改。

vmware tools

sudo su
apt-get update
apt-get install open-vm-tools
apt-get install open-vm-tools-desktop
reboot

共享文件夹

开共享后, 客户机共享文件夹目录: /mnt/hgfs/

重安装的网络问题

重新安装 vmware 时，可能会遇到以下问题：

安装程序在 "配置网络驱动" 时卡死
安装后客户机死活连不上网。

这是由于卸载时没有删除注册表导致的，解决方案（参考）如下：

在下载的软件中翻一翻，找到 "注册表"
一键扫描然后修复。
vmware 点 "编辑"，"虚拟网络编辑器"，还原默认设置。

输入法

百度输入法很靠谱，它甚至附带了安装说明。

百度输入法

先验概率 VS 后验概率

定义

先验概率是根据主观经验，在没有任何实验的情况下对某件事情发生概率的预测。
后验概率是根据某些已知证据，去估计的事情发生的概率。 \[ P(H|E) = \dfrac{P(E|H)*P(H)}{P(E)} \] 该式子中，每项含义如下：
- $P(H|E)$：在证据 $E$ 成立的前提下，假设 $H$ 成立的概率。
- $P(E|H)$：在假设 $H$ 成立的前提下，证据 $E$ 被观测的概率。
- $P(E)$：证据 $E$ 成立的先验概率。
- $P(H)$：假设 $H$ 成立的先验概率。

朱世衡之问

有关朱世衡提出的硬币之问，不妨设 $E$ 表示抛 $100$ 次硬币 $50$ 次正面朝上，$H$ 表示 $p=0.9$，也就是正面朝上的概率为 $90\%$。那么：

可以计算出 $P(E|H)\le \epsilon$，也就是如果 $H$ 成立，那么观测到 $E$ 的概率会很小。
不能说：因为 $P(E|H)\le \epsilon$，所以 $P(H|E)$ 很小。
$P(E)=\int^1_0{P(p=x)\cdot P(E|p=x) dx}$，显然 $P(p=x)$ 是个先验概率，是确定不了的，所以 $P(E)$ 没法计算，同理 $P(H)$ 也没法计算，故 $P(H|E)$ 计算不了。

最大似然

一般求解方式

考虑后验概率函数相对简单且为凸函数，对后验概率每个参数求偏导即可解出最大似然。
对后验概率函数使用梯度下降，求解极大似然。

EM 算法

算法用途

EM 算法主要用于近似求解一些最大似然问题。

算法流程

初始化模型参数 $\theta$。
对 $\theta$ 进行迭代，优化 $Q(\theta | \theta^{(t)}) = \mathbb{E}_{Z|Y,\theta^{(t)}} \left[ \log P(Y,Z|\theta) \right]$。
- 根据 $\theta^{(t)}$ 计算 $Z$ 不同取值的后验概率密度函数 $F = P(Z=x|\theta^{(t)})$。
- 根据 $F, \theta^{(t)}$ 求解上式的最大似然。

算法举例

有三个硬币 $A,B,C$，正面朝上的概率为 $\theta_A,\theta_B, \pi$，每次实验先抛硬币 $C$，如果 $C$ 正面朝上，则使用 $A$，否则使用 $B$，一次实验抛完 $C$ 后抛 $A$ 或 $B$ 五次，记录为：

实验一：2 正 3 反

实验二：4 正 1 反

实验三：1 正 4 反

实验四：3 正 2 反

实验五：4 正 1 反

根据实验结果给出一个最大似然参数估计 $\theta = (\theta_A, \theta_B, \pi)$。

E 步骤

计算每个实验由 $A$ 或 $B$ 生成的后验概率：
\[ \gamma_j(A) = \frac{\pi \cdot \theta_A^{n_j}(1-\theta_A)^{m_j}}{\pi \cdot \theta_A^{n_j}(1-\theta_A)^{m_j} + (1-\pi) \cdot \theta_B^{n_j}(1-\theta_B)^{m_j}} \]

M 步骤

迭代更新： \[ \pi' = \frac{\sum_{j=1}^5 \gamma_j(A)}{5} \]

\[ \theta_A' = \frac{\sum_{j=1}^5 \gamma_j(A) \cdot n_j}{\sum_{j=1}^5 \gamma_j(A) \cdot 5}, \quad \theta_B' = \frac{\sum_{j=1}^5 \gamma_j(B) \cdot n_j}{\sum_{j=1}^5 \gamma_j(B) \cdot 5} \]

迭代

设置一个收敛阈值，似然估计变化小于阈值时令其停止。

EM 原理证明

首先对似然函数取对数，记： \[ L(\theta) = \log(P(Y|\theta))=\log{\sum\limits_{z}P(YZ|\theta)}=\log(\sum\limits_{z}P(Y|Z,\theta)P(Z|\theta)) \] 考虑： \[ \begin{align} L(\theta) - L(\theta^{(i)})&= \log\big({\sum\limits_{z}P(Y|Z,\theta)P(Z|\theta)}\big) \\ &=\log\big({\sum\limits_{z}P(Z|Y, \theta^{(i)})\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y, \theta^{(i)})}}\big) - \log(P(Y|\theta^{(i)})) \end{align} \] 由 $\text{Jensen}$ 不等式，得 \[ \begin{align} \text{上式} &\ge \sum\limits_{z}P(Z|Y,\theta^{(i)})\log{\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y, \theta^{(i)})}} - \log(P|\theta^{(i)})\\ &= \sum\limits_{z}P(Z|Y,\theta^{(i)})\log{\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y, \theta^{(i)})P(|\theta^{(i)})}}) \end{align} \] 令： \[ \begin{align} B(\theta, \theta^{(i)})&= L(\theta) + P(Z|Y,\theta^{(i)})\log{\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y, \theta^{(i)})P(Y|\theta^{(i)})}}\\ &=L(\theta)+P(Z|Y,\theta^{(i)})\log{\frac{P(YZ|\theta)}{P(YZ|\theta^{(i)})}} \end{align} \] 第二行来自贝叶斯公式。

则有 $L(\theta)\ge B(\theta, \theta^{(i)})$，且 $B(\theta,\theta)=L(\theta)$。

所以令： \[ \theta^{(i+1)} = \mathbf{argmax}_\theta B(\theta, \theta^{(i)}) \] 则有： \[ L(\theta^{(i+1)}) \ge B(\theta^{(i+1)}, \theta^{(i)}) \ge B(\theta^{(i)},\theta^{(i)})=L(\theta^{(i)}) \] 即： \[ L(\theta^{(i+1)})\ge L(\theta^{(i)}) \]

算法分析

对比

上面的三硬币问题理论上也可以直接求解最大似然，但是列出来后是一个 PDE，一般 PDE 目前是没有闭式解，所以也只能退而求其次找近似解。

梯度下降也行，但是相比于 EM，梯度下降的梯度计算比较复杂，而且无法保证满足概率约束，可解释性弱，收敛不可靠等等等。

M 步骤最大似然的求解

三个变量是独立的，分别求偏导就能代出值来。

Docker 实践

发表于 2025-02-22 分类于技术

本文介绍了 Docker 的基本操作方法, 强调了一些易错点.

阅读全文 »

神经网络学习笔记

发表于 2025-02-20 更新于 2025-02-22 分类于学术

本文是神经网络学习笔记，主要记录了几种常用神经网络的结构和变体，以及一些训练技巧及其原理。

阅读全文 »

OSI 七层模型简单理解

发表于 2025-02-17 更新于 2025-02-22 分类于技术

本文以现代计算机网络硬件为基础，介绍了现代硬件环境下应该了解的网络知识，能够为网络编程打下一个较好的基础。

阅读全文 »

关于日志

VSCode 远程连接到服务器上开发卡死

Python slots

git 拉取远端其它分支并与本地关联

git 删除分支

Python lambda 闭包问题

C++ 全局变量的声明和定义

Python 线程独立资源

Python 异步任务、线程任务

Python Queue

nullptr 和 iterator::end()

C++ 容器

git 设置代理

C++ iostream

C++ Fsanitize

VMWARE 无法打开内核设备

Win11 自定义快捷键反应慢

简介

基本信息

算法流程

push

pop

merge

复杂度分析

实现

结构

声明

构造函数

merge

push && pop && top

左值右值的理解

左值的特性

右值的特性

右值举例

左值引用和右值引用

名词解释

右值引用的特性

左值引用的特性

引用折叠

完整代码

C 管理数据的方式

malloc && free

结构化数据

C++ 管理数据的方式

new && delete

new [] && delete []

各种文件

CMakeLists.txt

Makefile

.dll/.so

.o

.a

C++ 编译速通

GNU-make 工具的使用

Makefile 解读

变量操作

目标

目标规则

伪目标

自动变量

CMake 系列工具使用

配置源代码和构建路径

Configure

Generate

直接编译

gcc

ar

动态链接

软件的发布

练习——Windows 编译 OpenCV

练习——Windows 系统编译 minizip

大练习——编译 NcatBot 发行包

背景简介

有关资源

指示

附录

命令格式书写语法

更多自动变量

config apt source

vmware tools