cpp之std::atomic

发表于 2022-12-25 更新于 2023-10-07 分类于 cpp ， concurrent-programming
本文字数： 1.5k 阅读时长 ≈ 5 分钟

std::atomic

原子类型是对数据的一种封装，可以防止数据竞争，达到同步多线程的内存访问的目的。对该变量的读写是原子的。

1	#include <atomic>

使用前需要包含头文件。该头文件中主要包含两个类：atomic 和 atomic_flag。本文主要讲解 std::atomic。

构造函数和赋值

atomic() noexcept = default;
constexpr atomic (T val) noexcept;
atomic (const atomic&) = delete;

T operator= (T val) noexcept;
T operator= (T val) volatile noexcept;
atomic& operator= (const atomic&) = delete;
atomic& operator= (const atomic&) volatile = delete;

构造一个未初始化的原子对象。
构造一个用 val 初始化的原子对象。
禁用拷贝构造函数，原子对象不可复制、移动。
可以赋值（val）。

memory_order

typedef enum memory_order {
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,
    memory_order_release,
    memory_order_acq_rel,
    memory_order_seq_cst
} memory_order;

它们的目的是为了做线程间的同步，原理是在线程内限制变量操作的顺序：

memory_order_relaxed：用于读写，不做任何限制。
memory_order_acquire：用于读，如果一个原子变量的 load 用了该选项，那么可以保证，在本线程内，该 load 语句之后的所有变量（不论是否原子变量）的读写语句，都实际在该 load 操作执行后执行。
memory_order_release：用于写，如果一个原子变量的 store 用了该选项，那么可以保证，在本线程内，该 store 语句之前的所有变量（不论是否原子变量）的读写语句，都实际在该 store 操作执行前执行。
memory_order_consume：用于读，如果一个原子变量的 load 用了该选项，那么可以保证，在本线程内，该 load 语句之后的所有依赖该变量的变量的读写语句，都实际在该 load 操作执行后执行。但是，它只保证与当前操作相关的数据依赖关系。从 2016 年后，所有编译器实现中，memory_order_consume 和 memory_order_acquire 完全一致。
memory_order_acq_rel：memory_order_acquire + memory_order_release
memory_order_seq_cst：sequence consistent，顺序一致，要求所有变量的读写执行顺序都和代码中的顺序一致。

memory_order_acquire 和 memory_order_release 直观上就像一个栅栏：在调用处设置一个栅栏，acquire 是拦住代码中在它后边的变量读写操作，不让其跑到它前边；release则相反，不让前边的跑到后边。（cpu 提供 memory_barrier 或者 memory_fence 指令）关于为什么 cpu 会进行内存重排，请见内存模型与内存序。

atomic::store()

1 2	void store (T val, memory_order sync = memory_order_seq_cst) volatile noexcept; void store (T val, memory_order sync = memory_order_seq_cst) noexcept;

用 val 替换原子对象中的值。该操作是原子性的，通过 sync 指定内存顺序。sync 可选项见上文。

atomic::load()

1 2	T load (memory_order sync = memory_order_seq_cst) const volatile noexcept; T load (memory_order sync = memory_order_seq_cst) const noexcept;

返回原子对象中的值。该操作为原子性。

atomic::exchange

1 2	T exchange (T val, memory_order sync = memory_order_seq_cst) volatile noexcept; T exchange (T val, memory_order sync = memory_order_seq_cst) noexcept;

用 val 替换原子对象中的值，并返回替换前的值。操作为原子性。整个过程完成之前，其他线程无法访问。

atomic::compare_exchange_weak

bool compare_exchange_weak (T &expected, T val, memory_order sync = memory_order_seq_cst) volatile noexcept;
bool compare_exchange_weak (T &expected, T val, memory_order sync = memory_order_seq_cst) noexcept;

bool compare_exchange_weak (T &expected, T val, memory_order success, memory_order failure) volatile noexcept;
bool compare_exchange_weak (T &expected, T val, memory_order success, memory_order failure) noexcept;

将原子对象的存储值和预期值比较：

若为 true，用 val 替换原子对象值。
若为 false，用包含的值替换预期值。

整个过程是原子性的。

下面版本使用的内存顺序取决于比较结果：true 则使用 success; false 则使用 failure。该函数比较的是原子对象和预期值中的物理内容，这可能导致使用操作符 == 比较相等的值的在这里比较失败。

与 compare_exchange_strong 不同，该 weak 版本允许错误的返回 false，即使原子对象存储值与预期值相等。对于某些循环算法，这可能是可接受的行为，并且可能在某些平台上显著提高性能。对于这些虚假的失败，函数返回 false，但不修改预期的值。对于非循环算法，通常首选 compare_exchange_strong。

atomic::compare_exchange_strong

bool compare_exchange_strong (T &expected, T val, memory_order sync = memory_order_seq_cst) volatile noexcept;
bool compare_exchange_strong (T &expected, T val, memory_order sync = memory_order_seq_cst) noexcept;

bool compare_exchange_strong (T &expected, T val, memory_order success, memory_order failure) volatile noexcept;
bool compare_exchange_strong (T &expected, T val, memory_order success, memory_order failure) noexcept;

原子操作。与 compare_exchange_week 不同，当期望值与对象存储的值相等时，这个强版本必须始终返回 true，不允许虚假的失败。但是，在某些机器上，对于某些在循环中检查这个的算法，compare_exchange_weak 可能有更高的性能表现。

专门化计算操作

atomic::fetch_add(T val, memory_order sync = memory_order_seq_cst)

存储的值 + val 并返回之前的值，整个操作是原子性的。如果第二个参数使用默认值，那么这个函数相当于 atomic::operator+=。

atomic::fetch_sub(T val, memory_order sync = memory_order_seq_cst)

存储的值 - val 并返回之前的值，整个操作是原子性的。如果第二个参数使用默认值，那么这个函数相当于 atomic::operator-=。

atomic::fetch_and(T val, memory_order sync = memory_order_seq_cst)

（存储的值 & val）并返回之前的值，整个操作是原子性的。如果第二个参数使用默认值，那么这个函数相当于 atomic::operator&=。

atomic::fetch_or(T val, memory_order sync = memory_order_seq_cst)

（存储的值 | val）并返回之前的值，整个操作是原子性的。如果第二个参数使用默认值，那么这个函数相当于 atomic::operator|=。

atomic::fetch_xor(T val, memory_order sync = memory_order_seq_cst)

（存储的值 ^ val）并返回之前的值，整个操作是原子性的。如果第二个参数使用默认值，那么这个函数相当于 atomic::operator^=。

atomic::operator++ ()

递增保存的值，返回递增后的值。

atomic::operator++ (int)

递增保存的值，返回递增前的值。

atomic::operator-- ()

递减保存的值，返回递减后的值。

atomic::operator-- (int)

递减保存的值，返回递减前的值。

reference：https://blog.csdn.net/u014673282/article/details/89789139

内存泄露定位

发表于 2022-12-08 更新于 2023-10-07 分类于 tools
本文字数： 571 阅读时长 ≈ 2 分钟

什么是内存泄漏？

内存泄漏（Memory Leak）是指程序中已动态分配的堆内存由于某种原因程序未释放或
无法释放，造成系统内存的浪费，导致程序运行速度减慢甚至系统崩溃等严重后果。

valgrid工具

(1) 简介：
Valgrind 是一套 Linux 下，开放源代码（GPL V2）的仿真调试工具的集合。Valgrind 由
内核（core）以及基于内核的其他调试工具组成。内核类似于一个框架（framework），它模
拟了一个 CPU 环境，并提供服务给其他工具；而其他工具则类似于插件 (plug-in)，利用内
核提供的服务完成各种特定的内存调试任务。最常用的工具为 Memcheck，用来检测程序中
出现的内存问题，所有对内存的读写都会被检测到，一切对 malloc()/free()/new/delete 的调用
都会被捕获。所以，它能检测以下问题：
• 对未初始化内存的使用；
• 读/写释放后的内存块；
• 读/写超出 malloc 分配的内存块；
• 读/写不适当的栈中内存块；
• 内存泄漏，指向一块内存的指针永远丢失；
• 不正确的 malloc/free 或 new/delete 匹配；
• memcpy()相关函数中的 dst 和 src 指针重叠。
(2) 使用示例：
valgrind --log-file=report.log --tool=memcheck --leak-check=full --show-leak-kinds=all ./benc
hmark arg1 arg2 …
(3) 输出日志解读：
• 报告中会指示出发生泄漏的函数和文件位置；
• 最后会给出一个总结，标明了泄漏的内存总量；
• definitely lost: 铁定丢失，一般来说存在明显的泄漏；
• indirectly lost: 间接丢失，当使用了含有指针成员的类或结构时可能会报这个错误；
• possibly lost: 可能丢失；
• 只能定位到内存最初被申请的位置，不能定位到是哪里泄漏

AddressSantizer

(1) 简介：
AddressSanitizer（ASan）是一个快速的内存错误检测工具。它包括一个编译器 instrumentation 模块和一个提供 malloc()/free()替代项的运行时库。
(2) 使用：
编译和链接选项中加入-fsanitize=address -fno-omit-frame-pointer 即可。可以通过 readelf 工具查看.so 的依赖库中是否包含 ASan 来确认编译是否成功。

推理性能优化

发表于 2022-11-23 更新于 2023-10-07 分类于 AI
本文字数： 726 阅读时长 ≈ 3 分钟

推理性能优化

推理优化工作可以归成四类

算子优化
图优化
模型压缩
部署优化

算子优化

算子优化就是优化单算子的性能，方法无非是算法优化和微架构优化。

对同一个算子可能有不同的算法去实现它。举个例子，对卷积算法我们常见的就有：矩阵乘法，直接卷积法，Winograd 变换法，FFT 变换法。需要我们针对目标问题，分析并实现合适的算法，来达到最佳性能。
微架构优化。微架构优化主要焦点是如何充分利用好微架构的内置加速器的能力去最大化算子的性能。

图优化

图优化主要通过子图变换和算子融合的方式来达到减少计算量或者其他系统开销（如访存开销），从而达到性能优化的目的。图优化主要是希望在不影响模型的数值特性的基础上，通过图变换达到简化计算、资源开销，提升性能，所以是性能优化时的首选方法之一。

子图变换

子图变换主要是通过数学变换的手段对图进行精简，从而减少计算和调度开销。常见的有常数折叠，公共子表达式折叠以及算术变换。

常数折叠 (Constant Folding)

算数变换

算子融合

在深度学习中，一般来说，计算密集型和访存密集型算子是相伴出现的。这时候我们可以通过 fusion 来实现寄存器计算，从而减少访存密集型算子的访存，减少内存访问延时和带宽压力，提高推理效率。

通过这种方式，减少两次 tensor 的内存读写操作。

模型压缩

上面的方案都是精度无损的，当这三点都做完了后，如果还需要额外的性能增益，这时候需要考虑模型压缩方案。

模型量化

模型量化主要是通过降低模型中 tensor 和 weights 精度的手段，从而减少计算需求和数据存储与传输需求，来达到加速的目的。例如把权重从 FP32 降低为 FP16。虽然可以加速，但是有一定的精度损失。

模型蒸馏

模型蒸馏采用的是迁移学习的方法，通过采用预先训练好的复杂模型（Teacher Model）的输出作为监督数据，去训练另外一个简单的网络（Student Model），最后把 Student Model 用于推理。有精度损失。

部署优化

部署优化主要通过调整模型在部署时的资源分配和调度的参数来进一步优化性能。如，调整了 NUMA 的参数。

cpp不同种类构造函数

发表于 2022-11-18 更新于 2023-10-07 分类于 cpp
本文字数： 646 阅读时长 ≈ 2 分钟

cpp 的构造函数种类

构造函数：生成一个新的对象。
拷贝构造函数：参数是 const T& x，用于拷贝。
赋值构造函数：这个严格意义来说不是构造函数，是赋值运算符 = 的重载。初始化的时候不会调用这个函数！
移动构造函数：参数是 T &&x，用于移动构造，提升效率。

代码示例

#include <iostream>
#include <string>

using namespace std;

class Integer {
private:
    int* m_ptr;
public:
    //  普通构造函数
    Integer(int value) : m_ptr(new int(value)) {
        cout << "constructor" << endl;
    }
    //  拷贝构造函数
    Integer(const Integer& source) : m_ptr(new int(*source.m_ptr)) {
        cout << "copy constructor" << endl;
    }
    //  移动构造函数
    Integer(Integer&& source) : m_ptr(source.m_ptr) {
        source.m_ptr = nullptr;
        cout << "move constructor" << endl;
    }
    //  赋值运算符重载
    Integer& operator=(const Integer& source) {
        m_ptr = new int(*source.m_ptr);
        cout << "copy assignment constructor" << endl;
        return *this;
    }
    ~Integer() {
        cout << "destructor:" << GetValue() << endl;
        delete m_ptr;
    }
    int GetValue(void) {
        if (m_ptr) {
            return *m_ptr;
        } else {
            return -1;
        }
    }
};

Integer getNum() {
    Integer a(100);
    return a;
}
int main(int argc, char const* argv[]) {
    Integer a(getNum()); 
    cout << "a=" << a.GetValue() << endl;
    cout << "-----------------" << endl;
    Integer temp(10000);
    Integer b(temp);
    cout << "b=" << b.GetValue() << endl;
    cout << "-----------------" << endl;
    Integer c = b;
    c = a;
    cout << "c=" << c.GetValue() << endl;
    cout << "-----------------" << endl;
    return 0;
}

在编译的时候一定要指定编译选项 --no-elide-constructors，否则会被编译器优化！

@└────> # ./a.out 
constructor
move constructor
destructor:-1
move constructor
destructor:-1
a=100
-----------------
constructor
copy constructor
b=10000
-----------------
copy constructor
copy assignment constructor
c=100
-----------------
destructor:100
destructor:10000
destructor:10000
destructor:100

分析

a

第一个 constructor，是在 getNum() 中首句 Integer a(100) 所打印的，调用默认的构造函数。
第二个 move constructor 是因为 return a 的时候，这个 a 是个右值，作为 main 函数 getNum() 的返回值，而调用的移动构造函数，将 getNum() 函数内的返回值移动构造给 main 函数接收 getNum() 的对象。
第三个 destructor 是析构 getNum() 中的对象 a。
第四个 move constructor 是因为 Integer a(右值)，所以调用移动构造函数。
第五个 destructor 是析构 Integer a(右值) 中的右值而显示的。

b

第一个 constructor 是 Integer temp(10000); 调用的默认构造函数。
第二个 copy constructor 是 Integer b(temp); 调用的拷贝构造函数，将 temp 拷贝给 b；

c

第一个 copy constructor 是 Integer c = b; 调用的拷贝构造函数，可以看到此处并没有调用拷贝赋值运算符，因为这是在初始化！
第二个 copy assignment constructor 是 c = a 调用的才是拷贝赋值运算符。

可以看到，初始化的时候不会调用拷贝赋值运算符！！！

析构

最后的四个 destructor 是析构。根据规则，先构造的后析构，后调用的先析构。析构顺序：c = 100，b = 10000，temp = 10000，a = 100。

cpp左值和右值

发表于 2022-11-17 更新于 2023-10-07 分类于 cpp
本文字数： 1.4k 阅读时长 ≈ 5 分钟

何为右值

任何值不是左值，就是右值。左值和右值是针对表达式定义的。

右值的生存周期只到表达式结束，即语句分号后右值的生存周期就结束了。
左值可以取地址，右值不行。
左值可以放在 = 的左右，但是右值只能放在右边。

为什么要引入这么复杂的概念呢？为了性能。在赋值的时候，难免会产生一些临时变量的构造和销毁，这些构造和销毁可能会引起内存的申请与释放。频繁的系统调用会有很大的性能开销。这种时候没必要重复申请内存，只要把那个将要销毁对象内部的指针指向的空间被新的对象所利用就可以了！

int t = 10;  // t为左值
++t;         // t为左值，没有拷贝，这就是为什么 ++t 比 t++ 高效
t++;         // t为右值，因为加之前的值是个将亡值，是个 t_copy，是个临时变量
int &&r = t; // 错误，右值不能绑定左值。

std::move()

实现代码

/**
 *  @brief  Convert a value to an rvalue.
 *  @param  __t  A thing of arbitrary type.
 *  @return The parameter cast to an rvalue-reference to allow moving it.
*/
template<typename _Tp>
  constexpr typename std::remove_reference<_Tp>::type&&
  move(_Tp&& __t) noexcept
  { return static_cast<typename std::remove_reference<_Tp>::type&&>(__t); }

这个函数就一个作用：将左值明确的转换为右值。由于引用折叠的存在，导致返回值一定是右值。引用折叠概念见下一小节。

示例

#include <iostream>
using namespace std;
void func(string &&str) {
    cout << "右值函数" << endl;
}
void func(string &str) {
    cout << "左值函数" << endl;
}

int main() {
    string s;
    func(s + s);
    func(s);
    func(std::move(s));
}

结果：

@└────> # ./a.out 
右值函数
左值函数
右值函数

可以看到，s + s 是一个右值，编译器会自动匹配调用右值对应的函数。s 是一个左值，会调用左值对应的函数。使用 std::move() 强行把左值转换为右值，就匹配右值对应的函数。此处注意，因为 s 已经变为右值了，所以在调用之后，s 会失效。

std::forward()

在介绍 std::forward() 之前，先介绍下引用折叠。

引用折叠

引用折叠是指，在左值类型和右值类型叠加时，确认叠加规则。如下代码：

#include <iostream>
using namespace std;

template<typename T>
void WithoutPerfectForward(T &&t) {
    cout << "lvalue:" << std::is_lvalue_reference<decltype(t)>::value << endl;
    cout << "rvalue:" << std::is_rvalue_reference<decltype(t)>::value << endl;
    cout << endl;
}

int main() {
    int a = 1;
    int b = 2;
    const int c = 1;
    const int d = 0;
    int &e = a;
    int &f = b;
    const int &g = c;
    const int &h = d;
    WithoutPerfectForward(a);        // l + r = l
    WithoutPerfectForward(move(b));  // r + r = r
    WithoutPerfectForward(c);        // const l + r = l
    WithoutPerfectForward(move(d));  // const r + r = r
    WithoutPerfectForward(e);        // l ref + r = l
    WithoutPerfectForward(move(f));  // r ref + r = r
    WithoutPerfectForward(g);        // const l ref + r = l
    WithoutPerfectForward(move(h));  // const r ref + r = r
}

@└────> # ./a.out 
lvalue:1
rvalue:0

lvalue:0
rvalue:1

lvalue:1
rvalue:0

lvalue:0
rvalue:1

lvalue:1
rvalue:0

lvalue:0
rvalue:1

lvalue:1
rvalue:0

lvalue:0
rvalue:1

可以看到，因为 T 的不同会产生不同的模版函数特化版本，如参数会变为 T& && 和 T&& && 这两种形式，c++11 支持的编译器会对这种情况用 4 条规则做折叠处理，生成只有 & 和 && 的引用方式：

& + & = &
& + && = &
&& + & = &
&& + && = &&

即引用折叠时只要有左值引用，就折叠为左值引用，全部是右值引用，才折叠为右值引用。

那么考虑如下场景：

#include <iostream>
using namespace std;

void RunCode(int && m) {
    cout << "int && called!" << endl;
}
void RunCode(int &m) {
    cout << "int & called!" << endl;
}
void RunCode(const int && m) {
    cout << "const int && called!" << endl;
}
void RunCode(const int & m) {
    cout << "const int & called!" << endl;
}

template<typename T>
void WithoutPerfectForward(T &&t) {
    RunCode(t);
}

int main() {
    int a = 1;
    int b = 2;
    const int c = 1;
    const int d = 0;
    int &e = a;
    int &f = b;
    const int &g = c;
    const int &h = d;
    WithoutPerfectForward(a);        // l + r
    WithoutPerfectForward(move(b));  // r + r
    WithoutPerfectForward(c);        // const l + r
    WithoutPerfectForward(move(d));  // const r + r
    WithoutPerfectForward(e);        // l ref + r
    WithoutPerfectForward(move(f));  // r ref + r
    WithoutPerfectForward(g);        // const l ref + r
    WithoutPerfectForward(move(h));  // const r ref + r
}

结果：

@└────> # ./a.out 
int & called!
int & called!
const int & called!
const int & called!
int & called!
int & called!
const int & called!
const int & called!

可以看到虽然在函数 WithoutPerfectForward 中是右值，但是传给下一个函数的时候又默认都是左值了。虽然参数 t 是右值类型的，但此时 t 在内存中已经有了位置，所以 t 其实是个左值。

完美转发

为了实现不丢失传进来值的左右性，使用 std::forward() 就可以实现完美的转发了！

#include <iostream>
using namespace std;

void RunCode(int && m) {
    cout << "int && called!" << endl;
}
void RunCode(int &m) {
    cout << "int & called!" << endl;
}
void RunCode(const int && m) {
    cout << "const int && called!" << endl;
}
void RunCode(const int & m) {
    cout << "const int & called!" << endl;
}

template<typename T>
void WithoutPerfectForward(T &&t) {
    RunCode(std::forward<T>(t));
}

int main() {
    int a = 1;
    int b = 2;
    const int c = 1;
    const int d = 0;
    int &e = a;
    int &f = b;
    const int &g = c;
    const int &h = d;
    WithoutPerfectForward(a);        // l + r
    WithoutPerfectForward(move(b));  // r + r
    WithoutPerfectForward(c);        // const l + r
    WithoutPerfectForward(move(d));  // const r + r
    WithoutPerfectForward(e);        // l ref + r
    WithoutPerfectForward(move(f));  // r ref + r
    WithoutPerfectForward(g);        // const l ref + r
    WithoutPerfectForward(move(h));  // const r ref + r
}

结果：

@└────> # ./a.out 
int & called!
int && called!
const int & called!
const int && called!
int & called!
int && called!
const int & called!
const int && called!

实现代码

/**
 *  @brief  Forward an lvalue.
 *  @return The parameter cast to the specified type.
 *
 *  This function is used to implement "perfect forwarding".
 */
template<typename _Tp>
  constexpr _Tp&&
  forward(typename std::remove_reference<_Tp>::type& __t) noexcept
  { return static_cast<_Tp&&>(__t); }

/**
 *  @brief  Forward an rvalue.
 *  @return The parameter cast to the specified type.
 *
 *  This function is used to implement "perfect forwarding".
 */
template<typename _Tp>
  constexpr _Tp&&
  forward(typename std::remove_reference<_Tp>::type&& __t) noexcept
  {
    static_assert(!std::is_lvalue_reference<_Tp>::value, "template argument"
          " substituting _Tp is an lvalue reference type");
    return static_cast<_Tp&&>(__t);
  }

可以看到，std::forward() 有两个函数，会根据是左值还是右值调用不同的函数，返回不同种类出参。

KMP算法

发表于 2022-11-09 更新于 2023-10-07 分类于 algorithm
本文字数： 935 阅读时长 ≈ 3 分钟

KMP算法是什么

是用来解决字符串匹配的问题。在一个 $str$ 字符串中找到一个子字符串 $sub$ ，返回索引的位置。
常规能想到的最简单的方式就是一个一个比对，匹配失败的话就向下挪一个位置继续匹配。这样做时间复杂度是 $O(n^2)$ 。
KMP算法可以在 $O(n)$ 的时间复杂度内解决这个问题。

next数组是什么

$next$ 数组的本质是寻找子串中“相同前后缀的长度，并且最长”。并且不能是字符串本身。举个例子而言，如下所示：

A	B	A	B	C
0	0	1	2	0

第 $1$ 位 $A$ 只有一个字符，不能是字符串本身，为 $0$ ；
第 $2$ 位 $B$ 和 $A$ 比较，不相等，为 $0$ ；
第 $3$ 位 $A$ 和 $A$ 比较，相等，所以相同前缀为 $1$ ；
第 $4$ 位 $B$ 和前缀为 $1$ 后的 $B$ 比较，相等，和前缀组成了 $AB$ 的相同模式的串，所以相同前缀为 $2$ ；
第 $5$ 位 $C$ 和前缀为 $2$ 后的 $A$ 比较，不相等，和前缀长度为 $0$ 的比，相同前缀为 $0$ ；
关于最长前缀的理解是，如下图所示。

最后一位的 $A$ 很显然可以和 $ABA$ 组成长度为 $3$ 的相同前缀，也可以自己 $A$ 组成长度为 $1$ 的相同前缀。这种情况下选择较大的那个值。

求解next数组

$next$ 数组求解的本质是动态规划。假设我们已经知道当前数字的共同前后缀了，如下图所示。

接下来求第 $i$ 位的 $next$ 数组，分为两种情况。

下一位也和前缀相等
那就很明显等于 $next[i - 1]$ 加上 $1$ 。
下一位和前缀不相等
这里不是直接等于 $0$ 哦。如下图所示

虽然 $ABAB$ 和 $ABAC$ 并不相等，但是也不能直接设为 $0$ 。因为这个新来的 $B$ 可以和前面的 $A$ 组成 $AB$ ，达到 $2$ 的长度。那么这个数难道要暴力求解吗？其实不然。此时第 $i - 1$ 位的 $next$ 的可利用的值在前缀的 $next$ 数组中可以得到答案，在本图中为 $next[2]$ ，即是 $1$ 。此时修改前缀长度为 $next[2]$ ，则又回到了最开始的状况，匹配长度为 $1$ 并且匹配下一位，下一位 $B$ 相等，所以 $next[i]$ 为 $1 + 1 = 2$ 。
代码如下：

vector<int> buildNext(string sub) {
    vector<int> next;
    next.push_back(0);
    int prefix_len = 0;
    int i = 1; // 处理的索引，不会后退，以保证时间复杂度为O(n)
    while (i < sub.size()) {
        if (sub[i] == sub[prefix_len]) { // 下一位相等，next数组数值+1
            prefix_len++;
            next.push_back(prefix_len);
            i++;
        } else { // 下一位不相等
            if (prefix_len == 0) {
                next.push_back(prefix_len); // 目前没有相等的，就是0了
                i++;
            } else {
                prefix_len = next[prefix_len - 1]; // 有不为0的前缀选择，继续回到开始状况
            }
        }
    }
    return next;
}

next数组在KMP中的应用

KMP算法在匹配失败的时候，回去看最后失败的字符前一个字符所对应的 $next$ 值。 $next$ 数组中的值是什么作用呢？它代表我们可以“跳过匹配”的字符数量。

这样就可以保证匹配的 $i$ 不向后退，达到时间复杂度 $O(n)$ 的目的。
代码如下：

int kmp(string s, string sub) {
    vector<int> next = buildNext(sub);
    int i = 0; // 主串指针
    int j = 0; // 子串指针
    while (i < s.size()) {
        if (s[i] == sub[j]) { // 匹配，指针后移
            i++;
            j++;
        } else if (j > 0) { // 匹配失败，但是next跳过了一些字符继续匹配
            j = next[j - 1];
        } else { // 子串第一个字符就匹配失败
            i++;
        }
        if (j == sub.size()) {
            return i - j; // 成功，返回初始下标
        }
    }
    return -1; // 失败
}

nslookup程序(getaddrinfo和getnameinfo示例)

发表于 2022-09-26 更新于 2023-10-07 分类于 socket-programming
本文字数： 146 阅读时长 ≈ 1 分钟

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <netdb.h>

#define MAXLINE 64
int main(int argc, char **argv)
{
    struct addrinfo *p, *listp, hints;
    char buf[MAXLINE];
    int rc, flags;

    if (argc != 2) {
        fprintf(stderr, "usage: %s <domain name>\n", argv[0]);
        exit(0);
    }
    memset(&hints, 0, sizeof(struct addrinfo));
    hints.ai_family = AF_INET;  // 只用IPV4
    hints.ai_socktype = SOCK_STREAM;  // 只用TCP
    if ((rc = getaddrinfo(argv[1], NULL, &hints, &listp)) != 0) {
        fprintf(stderr, "getaddrinfo error: %s\n", gai_strerror(rc));
        exit(1);
    }

    flags = NI_NUMERICHOST;  // 展示数字而不是域名
    for (p = listp; p; p = p->ai_next) {  // 遍历结果链表
        getnameinfo(p->ai_addr, p->ai_addrlen, buf, MAXLINE, NULL, 0, flags);
        printf("%s\n", buf);
    }

    freeaddrinfo(listp);

    exit(0);
}

编译：

gcc nslookup.c -o nslook

运行：

Reference:

CSAPP: $P_{659}$

回文串

发表于 2022-09-10 更新于 2023-10-07 分类于 algorithm
本文字数： 1.9k 阅读时长 ≈ 7 分钟

什么是回文串？

回文串是如abcdedcba，abccba这样的字符串，从前往后和从后往前读是一样的结果。
算法逻辑也很简单，从前和从后同时校验一个字符串，如果不相等直接返回失败。时间复杂度为 $O(n)$ 。

bool check(string s) {
    int len = s.size();
    for (int i = 0; i < len / 2; i++) {
        if (s[i] != s[len - 1 - i]) {
            return false;
        }
    }
    return true;
}

最长回文串问题

给你一个字符串 s，找到 s 中最长的回文子串。
示例：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

暴力搜索

暴力搜索就是依次判断每个子串，如果是回文串就记录下他的长度。

string longestPalindrome(string s) {
    int len = s.size();
    if (len <= 1) {
        return s;
    }
    int maxlen = 1;
    string res = s.substr(0, maxlen);
    for (int i = 0; i < len; i++) {
        for (int j = 2; i + j <= len; j++) { // j是子串的长度，一种优化手段就是从 maxlen + 1 开始取
            string sub = s.substr(i, j);
            if (check(sub) && j > maxlen) { // 更新最长的回文串信息
                res = sub;
                maxlen = j;
            }
        }
    }
    return res;
}

遍历每个子串的时间复杂度是 $O(n^2)$ ，检验回文串时间复杂度为 $O(n)$ ，所以暴力求解的时间复杂度为 $O(n^3)$ 。

中心扩散法

从每一个位置出发，向两边扩散即可，遇到不是回文串就结束。

举例，s=acdbbdaa时，从s[2]=b开始扩散，是什么步骤呢？

向左扩散，直到不和原字符相等。
left = 2, right = 2, cur = 2, len = 1
acdbbdaa

向右扩散，直到不和原字符相等。
left = 2, right = 3, cur = 2, len = 2
acdbbdaa

同时向左右扩散，直到左右不相等。
left = 1, right = 4, cur = 2, len = 4
acdbbdaa

string longestPalindrome(string s) {
    int len = s.size();
    if (len <= 1) {
        return s;
    }
    int left = 0, right = 0, cur = 0;
    string res = "";
    while (cur < len) {
        left = cur, right = cur;
        while (left > 0 && s[left - 1] == s[cur]) { // 向左扩散
            left--;
        }
        while (right < len - 1 && s[right + 1] == s[cur]) { // 向右扩散
            right++;
        }
        while (left > 0 && right < len - 1 && s[left - 1] == s[right + 1]) { // 两边扩散
            left--;
            right++;
        }
        if (right - left + 1 > res.size()) { // 更新结果
            res = s.substr(left, right - left + 1);
        }
        cur++;
    }
    return res;
}

该方法遍历中心点时间复杂度 $O(n)$ ，扩散的时间复杂度 $O(n)$ ，总时间复杂度 $O(n^2)$ 。

动态规划

要判断 $dp[l][r]$ 是否是回文串，只需要知道 $dp[l+1][r-1]$ 是否是回文串就可以了。如果是的话，那么如果 $s[l] == s[r]$ ，那么就是回文串，否则不是。其中有一种特殊情况，在 $s[l] == s[r]$ 相等时，如果这俩相隔是 $2$ ，也可以认为是回文串。
初始化边界条件为所有都是 $false$ ，当 $l==r$ 时为 $true$ （单个字符是回文串）。
递推关系式为

dp[l][r] = ((dp[l+1][r-1]\ \ || \ \ j - i <= 2)\ \ \&\& \ \ s[l]==s[r])\ ?\ true : false

string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false)); // 初始化为都不是
    for (int i = 0; i < n; i++) { // 初始化边界
        dp[i][i] = true;
    }
    string res = s.substr(0, 1);
    for (int i = n - 1; i >= 0; i--) { // 注意遍历顺序，倒着遍历是为了保证依赖的数据是经过计算的
        for (int j = i + 1; j < n; j++) {
            if (dp[i + 1][j - 1] || j - i <= 2) {
                if (s[i] == s[j]) {
                    dp[i][j] = true;
                }
                if (dp[i][j] && j - i + 1 > res.size()) {
                    res = s.substr(i, j - i + 1);
                }
            }
        }
    }
    return res;
}

这种方式时间复杂度为 $O(n^2)$ ，空间复杂度也为 $O(n^2)$ 。

Manacher算法

这种算法又被称为“马拉车”，可以用 $O(n)$ 的时间复杂度解决最长回文字符串问题。这个算法的总框架是，遍历所有的中心点，寻找每个中心点对应的最长回文子串，然后找到所有中心点对应的最长回文子串。但是在时间复杂度上做了优化，使其变成线性。

臂长

为了表述方便，我们定义一个新概念臂长，表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 $2 * length + 1$ ，其臂长为 $length$ 。
下面的讨论只涉及长度为奇数的回文字符串。长度为偶数的回文字符串可以在每个字符串之间添加用不到的字符从而达到长度变为 $2n + 1$ 为奇数的目的。

从中心扩展的长度即为臂长， $臂长 - 1$ 就是原子串的回文字符串长度。所以问题就变成了求臂长数组。

求原字符串下标

用 $(i - P[i]) / 2$ ，就是原字符串开头的下标了。例如 $P[6] = 5$ ，那么原字符串开头下标为 $(6 - 5) / 2 = 0$ ，所以返回的结果为原字符串的 $[0, 5 - 1]$ 即可。

求每个 P[i]

用 $C$ 表示回文串中心 $Centre$ ，用 $R$ 表示臂长右半部分下标边界，即 $R = C + P[i]$ 。 $C$ 和 $R$ 对应当前循环中 $R$ 最靠右的回文串（手最长的，能管这个数组到最远的，之所以可以保证复杂度是因为保证 $R$ 不退缩）。

如图，在求 $P[i]$ 时，用 $i\_mirror$ 表示要求的第 $i$ 个字符关于 $C$ 对应的下标。我们要求 $P[i]$ ，用中心扩展法就是向两边伸长。但是可以利用已经求出来的回文串中心 $C$ 的对称性，因为 $P[i\_mirror] = 3$ ，那干脆让 $P[i] = 3$ 。有以下 $3$ 中情况会导致这个直接赋值不正确：

1. 超出了 R

当求 $P[i]$ 时， $P[i\_mirror] = 7$ ，但是却不应该等于 $7$ ，因为从 $i$ 往后面数 $7$ 个已经等于 $22$ 了，然而 $R$ 才到 $20$ ，很显然还没有探索到那里。但是可以保证我们一定可以扩展到 $R$ （因为对称），所以 $P[i]$ 至少可以为 $5$ 。剩下的只能中心扩展了。

2. P[i_mirror] 遇到了原字符串左边界

此时 $P[i\_mirror] = 1$ ，但是 $P[i]$ 赋值成 $1$ 是不正确的，原因是 $P[i\_mirror]$ 在扩展时首先是 $\#=\#$ ，之后遇到了边界才终止循环的，但是 $P[i]$ 并没有遇到边界，所以和上面一样继续中心扩展。

3. i == R

这个和情况一很像，将 $P[i] = 0$ ，之后中心扩展即可。

C 和 R 的更新

一步一步求 $P[i]$ ，当求出的 $P[i]$ 的右边界大于当前 $R$ 时，就要更新 $C$ 和 $R$ 了。

此时 $P[i] = 3$ ，导致 $R_(new) = 10 + 3 = 13 > 11$ ，那么 $C = 10, R = 13$ 。

string longestPalindrome(string s) {
    int len = s.length();
    if (len < 1) {
        return "";
    }
    // 预处理
    string s1;
    for (int i = 0; i < len; i++) {
        s1 += "#";
        s1 += s[i];
    }
    s1 += "#";
    len = s1.length();
    int R = 0;               // 当前访问到的所有回文子串，所能触及的最右一个字符的位置
    int C = 0;               // R对应的回文串的对称轴所在的位置
    int MaxP = 0;            // 最大回文串的回文半径
    int MaxC = 0;            // MaxP对应的回文串的对称轴所在的位置
    vector<int> P(len, 0);   // P[i] 表示以第 i 个字符为对称轴的回文串的回文半径
    for (int i = 0; i < len; i++) {
        if (i < R) {  // 1) 当i在R的左边
            P[i] = min(P[2 * C - i], R - i);
        } else {  // 2) 当i在R的右边
            P[i] = 1;
        }
        // 尝试扩展 P[i]，注意处理边界
        while (i - P[i] >= 0 && // 可以把 P[i] 理解为左半径,即回文串的起始位不能小于 0
               i + P[i] < len && // 同上,即回文串的结束位不能大于总长
               s1[i - P[i]] == s1[i + P[i]]) {  // 回文串特性，左右扩展，判断字符串是否相同
            P[i] += 1;
        }
        // 更新 R, C
        if (P[i] + i - 1 > R) {
            R = P[i] + i - 1;
            C = i;
        }
        // 更新 MaxP, MaxC
        if (MaxP <= P[i]) {
            MaxP = P[i];
            MaxC = i;
        }
    }
    return s.substr((MaxC - MaxP + 1) / 2, MaxP - 1);
}

为何基类析构函数必须为虚函数

发表于 2022-08-17 更新于 2023-10-07 分类于 cpp
本文字数： 706 阅读时长 ≈ 3 分钟

基类析构函数为虚函数的必要性

由于 C++ 中类的多态性，使用基类指针指向派生类时，若函数是虚的，则调用派生类中的函数。析构函数也是如此。如果有个基类指针指向了派生类对象，删除这个指针，调用的则是派生类的析构函数。派生类的析构函数又会自动调用基类的析构函数，达到所有空间都释放的目的。

如果不声明为虚函数，那么编译器实行静态绑定，在删除基类指针时，只调用基类的虚构函数而不调用派生类的析构函数，造成派生类中有空间没有释放完全而导致内存泄漏。

所以声明为虚函数是必要的，为了防止只析构基类而不析构派生类。

非虚析构函数会发生什么

#include <iostream>
using namespace std;
class Parent {
    public:
        Parent() {
            cout << "父类构造函数" << endl;
        }
        ~Parent() {
            cout << "父类析构函数" << endl;
        }
};

class Son : public Parent {
    public:
        Son() {
            cout << "子类构造函数" << endl;
        }
        ~Son() {
            cout << "子类析构函数" << endl;
        }
};

int main() {
    Parent *p = new Son();
    delete p;
    p = nullptr;
    return 0;
}

结果：

@└────> # ./a.out 
父类构造函数
子类构造函数
父类析构函数

可以看到，子类析构函数并没有被调用到。

基类析构函数定义为虚函数

#include <iostream>
using namespace std;
class Parent {
    public:
        Parent() {
            cout << "父类构造函数" << endl;
        }
        virtual ~Parent() {
            cout << "父类析构函数" << endl;
        }
};

class Son : public Parent {
    public:
        Son() {
            cout << "子类构造函数" << endl;
        }
        ~Son() {
            cout << "子类析构函数" << endl;
        }
};

int main() {
    Parent *p = new Son();
    delete p;
    p = nullptr;
    return 0;
}

结果：

@└────> # ./a.out 
父类构造函数
子类构造函数
子类析构函数
父类析构函数

小技巧

如果父类的设计者忘记了在析构函数处加 virtual，子类的设计者有义务提醒父类设计者，避免内存泄漏。

C++11 的关键字 override 可以起作用。override 表示函数应当重写基类中的虚函数（用于派生类的虚函数中）。编译器会检查基类中的虚函数和派生类中带有 override 的虚函数有没有相同的函数签名，一旦不匹配便会报错。

因此子类设计者可以在其析构函数后增加关键字 override，一旦父类缺少关键字 virtual，就会被编译器发现并报错。

#include <iostream>
using namespace std;
class Parent {
    public:
        Parent() {
            cout << "父类构造函数" << endl;
        }
        ~Parent() {  // 此处没加 virtual，会有编译错误
            cout << "父类析构函数" << endl;
        }
};

class Son : public Parent {
    public:
        Son() {
            cout << "子类构造函数" << endl;
        }
        ~Son() override {
            cout << "子类析构函数" << endl;
        }
};

int main() {
    Parent *p = new Son();
    delete p;
    p = nullptr;
    return 0;
}

编译结果：

@└────> # g++ test.cc 
test.cc:18:9: error: ‘Son::~Son()’ marked ‘override’, but does not override
         ~Son() override {
         ^

并查集

发表于 2022-08-09 更新于 2023-10-07 分类于 data-structure
本文字数： 683 阅读时长 ≈ 2 分钟

并查集是为了解决什么问题

有10个人，他们之间有错综复杂的关系。如果认定1和2为朋友，2和3也为朋友，那么就认定1和3也是朋友。现在给定两个编号，能否快速知道这两个人是否是朋友？这就是并查集的领域了。

基本思想：

并查集的本质是一个单向且出度为1的图。可以用一个数组来表示，这个数组记录的内容为这个节点所指向的另一个节点的编号。由于这个图出度为1，所以每个元素只唯一的指向另一个元素。而指向的这个节点，我们称为该节点的父节点。
并查集英文叫 unionFind，顾名思义这个数据结构有两个方法，union 和 find。union 用于连接两个集合，find 用于找到这个集合所属的编号。

初始化

只需要把每个节点的父节点设置为自己即可。

void init() {
    for (int i = 0; i < N; i++) {
        parent[i] = i;
    }
}

所属集合的判断

所属的集合只要一直向上遍历，直到找到祖先为止。祖先的编号就是这整个集合的标志编号。

int find(int i) {
    while (parent[i] != i) {
        i = parent[i];
    }
    return i;
}

关系的建立

如果要把两个节点建立并查集关系，只需要指定一个节点的祖先为另一个节点的父节点就可以了。

void merge(int a, int b) {
    int x = find(a);
    int y = find(b);
    if (x == y) {
        return;
    }
    parent[x] = y;
}

路径压缩

在某些极端情况下，这棵树型结构的集合可能会退化为线性结构，这样的情况下find函数会十分耗时。所以我们可以试着在某些方面优化这个效率。

查找时优化

在查找的过程中就直接将沿途的所有元素都指向根节点，大大的缩短下次查找时的时间。

int find(int i) {
    if (i == parent[i]) {
        return i;
    }
    return parent[i] = find(parent[i]); //在第一次查找的时候 将结点直接连到祖先
}

合并时优化

目前的合并是无论如何都让第二个节点的祖先当第一个节点祖先的新祖先，无视了每个集合内树的高度。如果我们记录下树的高度，让较高的树作为新的祖先，较低的树作为它的子节点，可以一定程度的平衡下树的高度。

void merge(int a, int b) {
    int x = find(a);
    int y = find(b);
    if (x == y) {
        return;
    }
    // 比高度
    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (rank[x] == rank[y]) {
            rank[x]++;
        }
    }
}