Ylin's Blog
0%

发表于 更新于
本文字数： 45 阅读时长 ≈ 1 分钟

你好呀！

这里记录我的学习经历和内容

希望能够帮到你们

: )

标签对应使用的编程语言

分类中查看对应的板块

发表于 更新于 分类于 ，
本文字数： 2.3k 阅读时长 ≈ 8 分钟

找到一个比较好的项目Byterun，这里进行一下复现。

Byterun

Byterun 是一个基于Python实现的Python字节码解释器，简化了Cpython的实现，展示了Python解释器在底层上的实现原理，以及相关的组织过程。

搭建一个解释器

解释器本质上就是一个虚拟机，他会对你产生的字节码信息进行解释，然后基于栈运行，实现运算、分支条件、循环结构等功能。

Python解释器实际上就是一个字节码解释器，它接受字节码，然后输出运行结果。当你写下一段Python代码时，会被词法分析器解析为token流，然后通过语法分析和编译器，作为字节码（code object）进行输出。然后字节码再由Python解释器进行运行。这里字节码的作用有点像汇编语言在C语言编译过程。

微型解释器

我们最简单的解释器开始，它只能识别以下三个指令，我们基于一点一点拓展实现我们的整个项目：

  • LOAD_VALUE：加载值
  • ADD_TWO_VALUES：相加
  • PRINT_ANSWER：输出值

我们对7+5生成以下指令集：

1
2
3
4
5
6
7
8
9
byte2exec = {
    "inst": [
        ("LOAD_VALUE",0),
        ("LOAD_VALUE",1),
        ("ADD_TWO_VALUES",None),
        ("PRINT_ANSWER",None)
    ],
    "num": [7,5]
}

之所以通过这种单指令和零指令的方式进行计算，是因为我们的Python解释器实际上是一个基于栈的虚拟机。

我们将指令和数据分开存放，这样保证了指令是定长的。因此，我们也需要向指令指出数据存放的位置，所以一个完整的指令集有两部分，指令和参数位置。对于不需要参数的零指令，我们用None表示。

现在我们可以基于栈来实现一个简单的解释器结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Interpreter:
    def __init__(self):
        self.stack = []

    def LOAD_VALUES(self,number):
        self.stack.append(number)

    def ADD_TWO_VALUES(self):
        first = self.stack.pop()
        second = self.stack.pop()
        total = first + second
        self.stack.append(total)

    def PRINT_ANSWER(self):
        answer = self.stack.pop()
        print(answer)

现在我们已经实现了一个虚拟机的基本结构和支持的指令，我们需要一个方法来驱动我们的虚拟机进行对指令的解析与执行：

1
2
3
4
5
6
7
8
9
10
11
12
def run(self, code):
    insts = code["inst"]
    nums = code["num"]
    for i in insts:
        inst ,arg = i
        if inst == "LOAD_VALUES":
            num = nums[arg]
            self.LOAD_VALUES(num)
        elif inst == "ADD_TWO_VALUES":
            self.ADD_TWO_VALUES()
        elif inst == "PRINT_ANSWER":
            self.PRINT_ANSWER()

现在我们可以尝试使用它们进行简单的计算3+4+5:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
code = {
    "insts":[
        ("LOAD_VALUES",0),
        ("LOAD_VALUES",1),
        ("LOAD_VALUES",2),
        ("ADD_TWO_VALUES",None),
        ("ADD_TWO_VALUES",None),
        ("PRINT_ANSWER",None),
    ],
    "nums":[3,4,5]
}

interpreter = Interpreter()
interpreter.run(code)
# 12

可以看到虚拟机按照预期输出了我们想要的结果。

变量

现在我们向虚拟机添加存储功能，我们可以将数值存入变量中，实现变量和值的映射关系，我们将实现以下两个指令：

  • STORE_NAME：存入变量
  • LOAD_NAME：取变量值

为了实现这个功能，我们需要再初始化一个内存空间（这里使用字典比较直观），用于存放变量名和值的绑定关系，同时需要在我们的code中添加变量名。我们的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Interpreter:
    def __init__(self):
        self.stack = []
        self.mem = {}	# 添加内存空间

    def LOAD_VALUE(self,number):
        self.stack.append(number)

	def ADD_TWO_VALUES(self):
        x = self.stack.pop()
        y = self.stack.pop()
        self.stack.append(x+y)	

    def PRINT_ANSWER(self):
        answer = self.stack.pop()
        print(answer)

    def STORE_NAME(self,name):
        val = self.stack.pop()
        self.mem[name] = val

    def LOAD_NAME(self,name):
        val = self.mem[name]
        self.stack.append(val)

    # 参数索引可能是访问数字也可能是变量 需要进行判断
    def parse_arg(self,inst,arg,code):
        nums = ["LOAD_VALUE"]
        vars = ["STORE_NAMES", "LOAD_NAMES"]
        if inst in nums:
            arg = code["nums"][arg]
        elif inst in vars:
            arg = code["vars"][arg]
        return arg

    def run(self, code):
        insts = code["insts"]
        for step in insts:
            inst ,arg = step
            # 根据指令内容解析对应的参数
            arg = self.parse_arg(inst,arg,code)
            if inst == "LOAD_VALUE":
                self.LOAD_VALUE(arg)
            elif inst == "STORE_NAME":
                self.STORE_NAME(arg)
            elif inst == "LOAD_NAME":
                self.LOAD_NAME(arg)
            elif inst == "ADD_TWO_VALUES":
                self.ADD_TWO_VALUES()
            elif inst == "PRINT_ANSWER":
                self.PRINT_ANSWER()

这里我们可以试着运行一下x = 3; y = 7; print(x+y):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
code = {
    "insts":[
        ("LOAD_VALUE",0),
        ("STORE_NAME",0),
        ("LOAD_VALUE",1),
        ("STORE_NAME",1),
        ("LOAD_NAME",0),
        ("LOAD_NAME",1),
        ("ADD_TWO_VALUES",None),
        ("PRINT_ANSWER",None),
    ],
    "nums":[3,7],
    "vars":["x","y"]
}

interpreter = Interpreter()
interpreter.run(code)
# 10

成功的运行了我们的函数。

程序结构优化

随着我们支持的指令增多，我们需要不断的通过if-else结构来进行对指令的执行。在我们的实现中，类的方法名和字节码中的指令是相同的，所以我们通过getattr方法来对run()进行优化：

1
2
3
4
5
6
7
8
9
10
def execute(self, code):
    insts = code["insts"]
    for step in insts:
        inst ,arg = step
        arg = self.parse_arg(inst,arg,code)
        inst = getattr(self,inst)	# 查找和inst同名的方法
        if arg is None:
            inst()
        else:
            inst(arg)

Python字节码

现在我们可以尝试解析一下真实的Python字节码，我们可以以下面的这个函数为例： 

1
2
3
4
5
6
def cond():
    x = 3
    if(x < 5):
        return 'yes'
    else:
        return 'no'

我们可以通过特殊方法__code__获取函数的字节码和元信息，具体的用法如下：

1
2
3
4
5
6
7
8
9
10
11
函数对象 (function)
    │
    └── __code__  (code对象 - 包含完整元数据)
           │
           ├── co_code     (字节码 - 仅指令)
           ├── co_consts   (常量元组)
           ├── co_varnames (变量名元组)
           ├── co_names    (全局名元组)
           ├── co_argcount (参数数量)
           ├── co_nlocals  (局部变量数量)
           └── ... 其他属性

这里我们可以通过这个方式得到我们的字节码指令

1
2
3
4
codebyte = cond.__code__.co_code
codebyte = list(codebyte)
print(codebyte)
# [151, 0, 100, 1, 125, 0, 124, 0, 100, 2, 107, 2, 0, 0, 114, 1, 121, 3, 121, 4]

我们得到了这个函数的字节码，但是我们无法阅读它。所以我们需要用到Python中的字节码反汇编器dis，将字节码进行翻译并以可读的形式输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import dis
codebyte = cond.__code__.co_code
dis.dis(codebyte)
'''
          0 RESUME                   0
          2 LOAD_CONST               1
          4 STORE_FAST               0
          6 LOAD_FAST                0
          8 LOAD_CONST               2
         10 COMPARE_OP               2 (<)
         14 POP_JUMP_IF_FALSE        1 (to 18)
         16 RETURN_CONST             3
    >>   18 RETURN_CONST             4
'''

其中第一列是该指令对应的字节码索引，第二列是该字节码的可读形式，第三列是指令的参数索引（第4列可能会指出使用的是什么参数）

同时我们也可以使用dis库中的opname方法，将对应的字节码翻译成可读的指令：

1
2
3
4
5
6
7
8
codebyte = cond.__code__.co_code
codebyte = list(codebyte)
print(dis.opname[codebyte[0]])
print(dis.opname[codebyte[4]])
'''
RESUME
STORE_FAST
'''

条件与循环

一个语言中条件分支和循环结构的能力也很重要，我们可以借这一段字节码深入的理解Python运行的实现。在我们的例子中if x>5被翻译成了：

1
2
3
4
 6 LOAD_FAST                0
 8 LOAD_CONST               2
10 COMPARE_OP               2 (<)
14 POP_JUMP_IF_FALSE        1 (to 18)

其中LOAD_FAST将局部变量加载到栈上，LOAD_CONST将常数5加载到栈上，然后通过COMPARE_OP指定的比较类型，对栈顶的两个数值进行比较，然后将比较结果放回栈上。最终POP_JUMP_IF_FALSE，根据比较的结果，跳转到指定的指令。跳转后要被加载的指令我们称之为跳转目标，作为POP_JUMP的参数，dis会用>>指出跳转目标。

有了条件判断和跳转之后，我们就可以实现最基本的循环结构，我们对下面这个循环结构进行分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def cond():
    x = 1
    while x<5:
        x += 1
    return x

'''
          0 RESUME                   0
          2 LOAD_CONST               1
          4 STORE_FAST               0
          6 LOAD_FAST                0
          8 LOAD_CONST               2
         10 COMPARE_OP               2 (<)
         14 POP_JUMP_IF_FALSE       11 (to 38)
    >>   16 LOAD_FAST                0
         18 LOAD_CONST               1
         20 BINARY_OP               13 (+=)
         24 STORE_FAST               0
         26 LOAD_FAST                0
         28 LOAD_CONST               2
         30 COMPARE_OP               2 (<)
         34 POP_JUMP_IF_FALSE        1 (to 38)
         36 JUMP_BACKWARD           11 (to 16)
    >>   38 LOAD_FAST                0
         40 RETURN_VALUE
'''

要理解这个循环结构，我们需要从几个跳转指令入手。首先是第一个POP_JUMP，如果判断为真，就进入循环体结构，不为真就直接退出。第二个POP_JUMP则是判断是否退出循环结构。第三个比较特殊JUMP_BACKWARD，它将无条件跳转到循环体的起点。通过跳转和条件分支的功能，实现了循环结构。

其他的语法结构也是类似的，如if ... elif, for ,...，可以通过dis慢慢探索

栈帧

实现了数值的计算和控制转移之后，现在我们需要进一步认识Python 函数调用的过程。正如上面的那个例子，我们看到RETURN_VALUES，那么结束这个函数之后会返回到哪里呢？

如果我们在函数中，我们会返回到调用者。如果是在模块顶层，我们可能会直接结束程序。我们将上一层的信息返回给下一层，例如在递归调用时，我们还需要保存每一层的局部状态。这就引出了Frame的概念，frame是函数调用的一次执行的上下文。它在python运行的过程中不断的被创建和销毁。

对于一个code object，我们可能会有多个frame。但是对于一个frame，我们有且仅对应一个code object。

frame存在于调用栈之中（和C一样）。Python中有三种类型的栈结构：

  • 调用栈：用来管理程序运行的函数调用状态
  • 数据栈：用于存放数据
  • 块栈：用于特定的控制流块，如异常和循环结构…

在调用栈的每个frame都有它自己的数据栈和块栈。以下面这个程序为例，它在调用栈中的状态大概就是这样的：

1
2
3
4
5
6
7
8
9
10
11
>>> def bar(y):
...     z = y + 3     
...     return z
...
>>> def foo():
...     a = 1
...     b = 2
...     return a + bar(b) 
...
>>> foo()             
3
image.png

至此，我们对Python字节码的基本分析就结束了

发表于 更新于 分类于 ，
本文字数： 8.3k 阅读时长 ≈ 30 分钟

上一章中完成了对图形渲染的饿BVH加速，现在我们要尝试将图片纹理映射到物体中。

纹理映射

图形学中的纹理映射是将材质效果应用于场景中的物理过程。其中”纹理”指的是效果（这个效果可以是材质属性，或是部分存在与否）本身，而映射则是将效果映射到物体的表面上。

最为常见的纹理映射就是将图像映射到物体表面上，就像是把世界地图依附到球体表面。和我们的直觉不同，纹理映射是一个逆向的过程，我们首先确定物体上的一个点，然后查找纹理贴图给定的颜色，以实现对图片的映射。

不过在此之前，我们先用程序化的方式生成纹理颜色，并创建一个纹理贴图。为了执行纹理查找，我们需要物体表面的纹理坐标(u,v)以定位纹理中的像素，同时也需要保存当前点的三维坐标（部分纹理需要这一部分的信息）

恒定色彩纹理

我们的纹理颜色类将从最简单的恒定色彩纹理开始实现，实际上我们可以将物体的颜色也视作一种纹理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#ifndef TEXTURE_H
#define TEXTURE_H

#include "utils.h"

class texture{
    public:
        virtual ~texture() = default;
        virtual color value(double u, double v, point3& p) const = 0;
};
class solid_color : public texture{
    public:
        solid_color(const color& albedo) : albedo(albedo) {}

        solid_color(double red, double green, double blue) : solid_color(color(red,green,blue)) {}

        color value(double u, double v, point3& p){
            return albedo;
        }
    private:
        color albedo;
};

#endif

这里我们先实现对纹理类的接口的一个实现，然后创建一个恒定色彩纹理类，返回恒定的颜色类型。

注意到我们这里需要使用到(u,v)表面坐标，我们还需要更新hit_record结构，对这些射线碰撞信息进行存储：

1
2
3
4
5
6
7
8
class hit_record {
public:
    point3 p;
    double u;
    double v;
    vec3 normal;
	...
};

棋盘纹理

棋盘纹理作为实体纹理中的一种。实体纹理取决点在空间中的位置，我们可以理解为给空间中的指定点进行着色，而不是给空间中的某个物体上色。正因如此，当我们的物体在空间中移动时，纹理并不会随物体进行移动，反而像是物体在穿过纹理。

这里我们将实现一个棋盘纹理类，它是一种空间纹理（即实体纹理）。根据点在空间中给定的位置进行纹理颜色的渲染。

为了实现棋盘格图案，我们需要对当前点的每个坐标分量取floor，这样我们就将整个空间分割为1x1x1的单元格，每个坐标都可以映射到对应的单元格，我们对奇数的单元格赋予一种颜色，对偶数赋予另外的一种颜色，这样就实现了棋盘的样式。同时我们还可以设置一个缩放因子scale，控制单元格的大小，从而实现对棋盘格的大小控制：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class checker_texture : public texture{
    public:
        checker_texture(double scale, shared_ptr<texture> even, shared_ptr<texture> odd)
            : inv_scale(1.0/scale), even(even), odd(odd) {}

        checker_texture(double scale, const color& c1, const color& c2)
            : checker_texture(scale, make_shared<solid_color>(c1), make_shared<solid_color>(c2)) {}

        color value(double u, double v, point3& p) const override{
            auto xInt = int(floor(inv_scale*p.x()));
            auto yInt = int(floor(inv_scale*p.y()));
            auto zInt = int(floor(inv_scale*p.z()));

            bool isEven = (xInt + yInt + zInt) % 2 == 0;

            return isEven ? even->value(u,v,p) : odd->value(u,v,p);
        }

    private:
        double inv_scale;
        shared_ptr<texture> even;
        shared_ptr<texture> odd;
};

为了进一步的支持纹理，我们拓展lambertian类，使用纹理代替颜色：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class lambertian : public material {
public:
    lambertian(const color& albedo) : tex(make_shared<solid_color>(albedo)) {}

    lambertian(shared_ptr<texture> tex) : tex(tex) {}

    virtual bool scatter(
        const ray& r_in, const hit_record& rec, color& attenuation, ray& scattered
    ) override {
        auto scatter_direction = rec.normal + random_unit_vector();
        if (scatter_direction.near_zero()) {
            scatter_direction = rec.normal;
        }
        scattered = ray(rec.p, scatter_direction, r_in.time());
        attenuation = tex->value(rec.u, rec.v, rec.p);
        return true;
    }

private:
    shared_ptr<texture> tex;
};

这里通过多态的思想实现了对lambertian材质的纹理的实现。

现在我们可以向我们的场景中添加纹理了：

1
2
3
4
   // main.cpp中将地面设置成棋盘样式
auto checker = make_shared<checker_texture>(0.2, color(0,0,0), color(1,1,1));
   auto ground_material = make_shared<lambertian>(checker);
   world.add(make_shared<sphere>(point3(0,-1000,0), 1000, ground_material));

渲染结果如下：

image.png

空间纹理的特殊情况

正如之前所提到的，这种实体纹理的上色方式，更像是物体在穿过纹理，从而完成上色。

我们现在创建一个新的场景来观察这种特殊的情况，我们将先前的main函数保存为一个bounding_ball场景，然后现在我们再来创建一个新的场景：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void checkered_spheres() {
    hittable_list world;

    auto checker = make_shared<checker_texture>(0.32, color(.2, .3, .1), color(.9, .9, .9));

    world.add(make_shared<sphere>(point3(0,-10, 0), 10, make_shared<lambertian>(checker)));
    world.add(make_shared<sphere>(point3(0, 10, 0), 10, make_shared<lambertian>(checker)));

    camera cam;

    cam.aspect_ratio      = 25.0 / 16.0;
    cam.image_width       = 800;
    cam.samples_per_pixel = 100;
    cam.max_depth         = 50;

    cam.vfov     = 20;
    cam.lookfrom = point3(13,2,3);
    cam.lookat   = point3(0,0,0);
    cam.vup      = vec3(0,1,0);

    cam.defocus_angle = 0;

    cam.render(world);
}

我们通过main函数中的switch来切换我们想要渲染的场景：

1
2
3
4
5
6
int main(){
    switch(2){
        case 1: bounding_ball(); break;
        case 2: checkered_spheres(); break;
    }
}

我们渲染出来的结果如下：

image.png

这就是空间纹理渲染的特殊情况，不过你应该能理解这是什么情况。所以为了解决这个问题，我们需要使用表面纹理，这就意味着我们需要根据(u,v)的球体表面位置信息来创建纹理。

球体表面纹理坐标

空间纹理通过空间中一点的坐标，实现纹理的绘制。但是真如我们先前所提到的空间纹理的局限性，我们希望能够更具球体表面的坐标实现对图像点对点的映射。这就以为着我们需要一种方法来查找三维球体表面任意点的坐标(u,v)。

这里用到一个经纬度的思想，首先确定出这个点在球体上的经纬度(θ, ϕ)（横纬竖经，这里θ从-Y向上，ϕ从-X到+Z到+X到-Z），然后再将球面坐标表示出来，这里的话，如果学过球面坐标，自然能够得到以下式子： $$ 我们可以简单的推导得到： $$ 所以我们可以写出sphere类中的get_uv方法：

1
2
3
4
5
6
static void get_uv(const point3& p, double& u, double& v){
    auto theta = std::acos(-p.y());
    auto phi = std::atan2(-p.z(),p.x()) + pi;
    u = phi / (2*pi);
    v = theta / pi;
}

然后我们向hit方法中添加，每次碰撞记录的(u,v):

1
2
3
4
5
6
7
8
9
10
11
  bool hit(const ray& r, interval t_range, hit_record& rec) const override {
...
      rec.t = root;
      rec.p = r.at(rec.t);
      vec3 outward_normal = (rec.p - cur_center) / radius;
      rec.set_face_normal(r, outward_normal);
      // 这里的outward 就是从球心指向碰撞点的向量
      get_uv(outward_normal,rec.u,rec.v);
      rec.mat = mat;
      return true;
  }

现在我们就实现了对球体表面的位置的(u,v)二维定位

访问纹理图像数据

现在我们需要一种手段，将图片数据解析为一种二维关系，我们希望通过(u,v)访问图像数据上对应的像素值。所以我们需要将图片加载为一个浮点数数组，便于我们访问。这里我们使用第三方库stb_image.h来实现

首先我们创建一个辅助类来帮助我们管理图片信息内容，以提供一个pixel_data(int x,int y)方法，来访问任意像素的8位（unsigned char）RGB。

我们的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#ifndef IMAGE_H
#define IMAGE_H

#ifdef _MSC_VER
    #pragma warning (push,0)
#endif

#define STB_IMAGE_IMPLEMENTATION
#define STBI_FAILURE_USERMSG

#include "stb_image.h"
#include "utils.h"

class image{
    public:
        image(){}

        image(const char* image_file){
            auto filename = std::string(image_file);
            if(load("../images/" + filename)) return;

            std::cerr << "ERROR: Could not load image file" << image_file << "\n";
        }

        ~image(){
            delete[] bdata;
            STBI_FREE(fdata);
        }

        bool load(const std::string& filename){
            auto n = bytes_per_pixel;
            fdata = stbi_loadf(filename.c_str(), &image_width, &image_height, &n, bytes_per_pixel);
            if(fdata == nullptr) return false;

            byte_per_scanline = bytes_per_pixel * image_width;
            convert_to_bytes();
            return true;
        }

        int width() {return (fdata==nullptr) ? 0 : image_width;}
        int height() {return (fdata==nullptr) ? 0 : image_height;}

        const unsigned char* pixel_data(int x, int y) const{
            static unsigned char magenta[] = {255,0,255};
            if(bdata==nullptr) return magenta;

            x = clamp(x,0,image_width);
            y = clamp(y,0,image_height);

            return bdata + x*bytes_per_pixel + y*byte_per_scanline;
        }

    private:
        const int bytes_per_pixel = 3;      // 每像素的位数(即通道数)
        float* fdata = nullptr;             // 浮点像素数据
        unsigned char* bdata = nullptr;     // 8bit像素数据
        int image_width = 0;                // 图像宽度
        int image_height = 0;               // 图像高度
        int byte_per_scanline = 0;          // 宽的像素数量

    	// return [low,high)
        static int clamp(int x, int low, int high){
            if(x < low) return low;
            if(x < high) return x;
            return high - 1;
        }

        static unsigned char float_to_byte(float value){
            if(value <= 0.0)
                return 0;
            if(value >= 1.0)
                return 255;
            return static_cast<unsigned>(value*256.0);
        }

        void convert_to_bytes(){
            int total_bytes = bytes_per_pixel * image_height * image_width;
            bdata = new unsigned char[total_bytes];

            auto *bptr = bdata;
            auto *fptr = fdata;
            for(auto i=0; i<total_bytes ; i++,fptr++,bptr++)
                *bptr = float_to_byte(*fptr);
        }
};


#ifdef _MSC_VER
    #pragma warning (pop)
#endif

#endif

现在我们封装好了一个加载并获取图像内容的image类，我们可以利用它实现图像纹理image_texture:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class image_texture : public texture{
    public:
        image_texture(const char* filename) : image(filename){}

        color value(double u, double v, const point3& p) const override{
            if(image.height() <= 0) return color(0,1,1);

            u = interval(0,1).clamp(u);
            // 由于图片坐标起始位置是从左上角开始
            // 而图形学坐标从左下角开始,所以需要进行反转
            v = 1.0 - interval(0,1).clamp(v);
            
            auto i = int(u*image.width());
            auto j = int(v*image.height());
            auto pixel = image.pixel_data(i,j);

                    auto color_scale = 1.0 / 255.0;
        return color(color_scale*pixel[0], color_scale*pixel[1], color_scale*pixel[2]);
        }

    private:
        image image;
};

图像纹理渲染

现在我们可以尝试将一个图片进行渲染：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void earth() {
    auto earth_texture = make_shared<image_texture>("earthmap.jpg");
    auto earth_surface = make_shared<lambertian>(earth_texture);
    auto globe = make_shared<sphere>(point3(0,0,0), 2, earth_surface);

    camera cam;

    cam.aspect_ratio      = 25.0 / 16.0;
    cam.image_width       = 2000;
    cam.samples_per_pixel = 100;
    cam.max_depth         = 10;

    cam.vfov     = 20;
    cam.lookfrom = point3(-3.75,4,-9);
    cam.lookat   = point3(0,0,0);
    cam.vup      = vec3(0,1,0);

    cam.defocus_angle = 0;

    cam.render(hittable_list(globe));
}

我们使用一张地球的贴图（效果如下）：

image.png

至此 我们的纹理样式就简单介绍完了

发表于 更新于 分类于 ，
本文字数： 3.1k 阅读时长 ≈ 11 分钟

书接上回，上一次实现了物体运动下的图形学渲染。实现了动态模糊的构建。

包围体积层级

现在随着我们场景的复杂化，和对图片质量的提升，有时候渲染一张照片都需要十几分钟。为了让代码运行的更快，我们需要引入一个新的结构 包围体积层级BVH，以优化程序渲染的性能。

射线 - 对象求交，是光线追踪过程中的主要性能瓶颈，运行的时间和物体的数量呈线性关系。每当我们发射一条射线，就需要对场景内的所有物体进行求交判断。但是实际上和很多物体的求交是没有必要的，我们向天空发射的一条光线并不会和地上的物体有所交集。

所以我们为了优化这个过程，我们需要避免不必要的射线 - 对象求交计算，接下来我们要学习的方法就是通过包围体积层次来实现对求交场景的优化。

关键思想

为一组对象创建一个完全包围所有对象的包围盒，假如射线会错过这个包围盒，那么它一定会错过这个包围盒中的所有物体，反之，则有可能击中盒中的任意一个对象，所以我们的思想如下：

1
2
3
4
if(ray hits bounding object)
    return whether ray hits bounded objects
else
    return false

包围体积的层级

为了提高计算的效率，使得处理时间的增长速度慢于物体数量的增长。首先我们需要构建有一个层次化的包围体结构，这里我们通过自顶向下的方法，生成我们的包围体积的层级结构。

一开始我们需要构建一个层次化的包围体结构，用大的包围体包住一群物体，再逐层细化，就像下面这样：

image.png

我们可以写出以下伪代码：

1
2
3
4
5
6
if(hit purple)
    hit0 = hits blue enclosed objects
    hit1 = hits red enclosed objects
    if(hit0 or hit1)
        return true and info of closer hit
return false

当我们确定击中紫色包围盒时，分别对里面的蓝色组和红色组进行分析，从而进一步缩小碰撞检测的范围

轴对齐边界框(AABBs)

要让整个层次结构高效工作，我们需要要一个好的划分方式，而且我们需要一个较快的检测光线和包围体相交的算法，否则我们检测相交的速度会抵消掉包围结构层次带来的加速效果。这里我们选择轴对齐包围盒作为我们的包围体。我们通常将其称为AABB。

接下来我们需要了解光线和AABB相交检测的slab方法：

首先我们需要知道什么是片层(Slab)，片层是在一个坐标轴方向上，由两个平行平面围成的空间区域，比如在 x 轴方向，若 AABB 的 x 范围是 [x_min, x_max]，那么这个 slab 就是所有满足 x_min ≤ x ≤ x_max 的点。在我们要用到的3D场景中，AABB = x-slab && y-slab && z-slab。

理解片层之后，我们检测碰撞的关键就在于计算光线和不同片层之间的交点，其中射线的函数定于为P(t) = Q + td，我们可以求出其在x = x0t平面的交点为： $$ \begin{align*} x_0 &= Q_x + t_0d_x \\ t_0 &= \frac{x_0 - Q_x}{d_x} \\ t_1 &= \frac{x_1 - Q_x}{d_x} \end{align*} $$ 知道光线与各个片层之间的交点之后，我们可以进一步判断光线和AABB的相交情况了，以下图为例：

image.png

这是一个二维的AABB场景，上面的射线和x、y片层中的交集段并没有重叠，所以我们知道射线并没有和AABB发生交集，下面的射线和x、y片层的交集段发生了重叠，所以说射线和AABB之间是有交集的。

与AABB的射线交

上图我们可以用于以下伪代码确定射线是否和AABB发生碰撞：

1
2
3
interval_x <- compute_intersection_x(ray, x0, x1)
interval_y <- compute_intersection_y(ray, y0, y1)
return overlaps(interval_x, interval_y)

相应的三维版本如下：

1
2
3
4
interval_x <- compute_intersection_x(ray, x0, x1)
interval_y <- compute_intersection_y(ray, y0, y1)
interval_z <- compute_intersection_z(ray, z0, z1)
return overlaps(interval_x, interval_y, interval_z)

我们已经知道了怎么求出射线和片层的相交区间，我们需要进一步的检测这些相交区间是否有交集，现在，我们的关键在于实现overlaps了，在此之前我们需要考虑以下几种特殊情况：

  • 如果射线沿着负x方向运动，我们的计算得到的区间会发生反转，所以我们始终需要根据min和max来标识我们的区间
  • 当dx为0 或接近0时，会求得t为-infinity/+infinity，我们通过min/max可以解决这个问题
  • 当dx为0 但Qx在AABB的界限上/界限内时，加缓冲防止边界问题

现在我们可以写出伪函数overlaps:

1
2
3
4
bool overlaps(t_interval1, t_interval2)
    t_min = max(t_interval.min, t_interval2.min)
    t_max = min(t_interval.max, t_interval2.max)
    return t_max>t_min

对于第三种特殊情况，此时我们无法给出准确的t_min和t_max，所以我们将这个情况称之为NaN，这里我们需要进行手动的处理，为区间添加一个padding，将NaN的情况视作fasle

为此我们需要为interval添加一个expend函数，它给区间填充给定的值：

1
2
3
4
5
6
7
8
9
10
class interval {
public:
	...
    interval expand(double delta) const{
        auto padding = delta/2;
        return interval(min-padding, max+padding);
    }
	...
    static const interval empty,universe;
};

现在，我们可以开始实现AABB类了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#ifndef AABB_H
#define AABB_H

#include "utils.h"

class aabb{
    public:
        interval x,y,z;

        aabb() {}   // 默认为空
        aabb(const interval& x, const interval& y, interval& z)
            : x(x), y(y), z(z) {}
        aabb(const point3& a, const point3& b){
            // 这里的a和b是AABB盒的对顶角
            x = (a[0]<=b[0]) ? interval(a[0],b[0]) : interval(b[0],a[0]);
            y = (a[1]<=b[1]) ? interval(a[1],b[1]) : interval(b[1],a[1]);
            z = (a[2]<=b[2]) ? interval(a[2],b[2]) : interval(b[2],a[2]);
        }

        const interval& axis_interval(int n)const{
            if(n==1) return y;
            if(n==2) return z;
            return x;
        }

        bool hit(const ray& r, interval ray_t) const{
            const point3& ray_orig = r.origin();
            const vec3& ray_dir = r.direction();

            for(int axis=0;axis<3;axis++){
                const interval& ax = axis_interval(axis);
                const double adinv = 1.0 / ray_dir[axis];

                auto t0 = (ax.min - ray_orig[axis]) * adinv;
                auto t1 = (ax.max - ray_orig[axis]) * adinv;
                
                // 收缩区间（取交集）
                if(t0 < t1){
                    if(t0 > ray_t.min) ray_t.min = t0;
                    if(t1 < ray_t.max) ray_t.max = t1;
                }else{
                    if(t1 > ray_t.min) ray_t.min = t1;
                    if(t0 < ray_t.max) ray_t.max = t0;
                }

                // 说明无交点
                if(ray_t.min >= ray_t.max)
                    return false;
            }
            return true;
        }
};

#endif

这里的关键在于hit函数，我们通过区间收缩的方式实现对交集的判断。

为可击中类创建包围盒

现在我们需要为所有的可击中类构建一个包围盒，对于单个的物体，我们将其包围盒视作包围结构层次中的叶子节点，这个我们之后会提到。

由于我们的物体有部分是动画的，所以我们为其生成的包围盒边界应该等于其运动范围，首先，我们需要升级我们的hittable类：

1
2
3
4
5
6
class hittable{
public:
    virtual ~hittable() = default;
    virtual bool hit(const ray& r, interval t_range, hit_record& rec) const = 0;
    virtual aabb bounding_box() const = 0;
};

对于静态和动态的球体，我们很容易为其创建出包围盒：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class sphere: public hittable {
public:
    // 静态球体
    sphere(const point3& static_center, double radius, shared_ptr<material> mat)
        : center(static_center,vec3(0,0,0)), radius(radius), mat(mat) {
            auto rvec = vec3(radius,radius,radius);
            bbox = aabb(static_center - rvec, static_center + rvec);
        }
    // 动态球体
    sphere(const point3& center1, const point3& center2, double radius, shared_ptr<material> mat)
        : center(center1,center2-center1), radius(radius), mat(mat) {
            auto rvec = vec3(radius,radius,radius);
            aabb box1(center.at(0) - rvec, center.at(0) + rvec);
            aabb box2(center.at(1) - rvec, center.at(1) + rvec);
            bbox = aabb(box1,box2);
        }
    
    aabb bounding_box() const override {return bbox;}

	...

private:
	...
    aabb bbox;
};

这里注意到我们直接将box1和box2合并成了一个新的包围盒区间，这是我们新定义的一种构造方法，也便于之后的包围盒合并：

1
2
3
4
5
6
7
8
9
10
   aabb(const aabb& box1, const aabb& box2){
       x = interval(box1.x, box2.x);
       y = interval(box1.y, box2.y);
       z = interval(box1.z, box1.z);
   }
// 这里用到的Interval合并形式，来自于interval类中新定义的合并构造
interval(const interval& a,const interval& b){
       min = a.min <= b.min ? a.min : b.min;
       max = a.max >= b.max ? a.max : b.max;
   }

创建对象列表的边界框

现在我们需要更新对象列表hittable_list，现在列表中的物体被创建时，会生成相应的包围盒边界。而我们需要随着每个新子节点的加入逐步的更新边界框，于是我们有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class hittable_list : public hittable {
private:
    aabb bbox;
public:
    std::vector<shared_ptr<hittable>> objects;
	....
    void add(shared_ptr<hittable> object) { 
        objects.push_back(object); 
        bbox = aabb(bbox,object->bounding_box());
    }
    aabb bounding_box() const override {return bbox;}

	....
};

BVH节点类

BVH本质上也是一个hittable ，它代表一组几何体，光线可以击中它以进行相交判断。我们将它视作一个对象的容器，它封装了几何体，通过包围盒相交测试进行加速检测。

我们通过一个类来实现它，它既可以是节点，也可以是整棵树的根：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#ifndef BVH_H
#define BVH_H

#include "AABB.h"
#include "hittable.h"
#include "hittable_list.h"
#include "utils.h"

class bvh_node: public hittable{
    public:
        bvh_node(std::vector<shared_ptr<hittable>>& objects, size_t start, size_t end) {
            // 待具体实现
        } 
        bvh_node(hittable_list list): bvh_node(list.objects, 0, list.objects.size()) {
            // 重载并使用了上面的初始化方法
        }

        bool hit(const ray& r, interval ray_t, hit_record& rec) const override{
            if(!bbox.hit(r,ray_t))
                return false;

            bool hit_left = left->hit(r, ray_t, rec);
            bool hit_right = right->hit(r, ray_t, rec);

            return hit_left||hit_right;
        }

        aabb bounding_box() const override{return bbox;}

    private:
        shared_ptr<hittable> left;
        shared_ptr<hittable> right;
        aabb bbox;
};

#endif

接下来的重点在于怎么将hittable_list构建成我们想要的BVH。我们希望每个BVH下至多有两个左右节点，但是我们以什么为依据进行划分呢，以下是我们的做法：

  • xyz轴任选其一
  • 根据轴值进行排序
  • 将子树对半存放

当我们构建BVH的递归生成时，会有以下几种情况：

  • list表中剩余一个物体，我们让BVH节点的子树均指向它
  • list表中剩余两个物体，我们让BVH节点的左右子树分别指向
  • list表中有两个以上物体，我们取一轴进行排序，递归进行生成BVH

因此，我们的BVH生成的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bvh_node(std::vector<shared_ptr<hittable>>& objects, size_t start, size_t end) {
    int axis = random_int(0,2);
    
    auto comparator = (axis==0) ? box_x_compare : (axis==1) ? box_y_compare : box_z_compare;

    size_t object_span = end - start;

    if(object_span == 1){
        left = right = objects[start];
    }else if(object_span == 2){
        left = objects[start];
        right = objects[start+1];
    }else{
        sort(std::begin(objects)+start, std::begin(objects)+end, comparator);
        auto mid = start + object_span/2;
        left = make_shared<bvh_node>(objects, start, mid);
        right = make_shared<bvh_node>(objects, mid, end);
    }
    bbox = aabb(left->bounding_box(), right->bounding_box());
}

这里sort使用的判断逻辑如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static bool box_compare(
            const shared_ptr<hittable> a, const shared_ptr<hittable> b, int axis_index
        ) {
            auto a_axis_interval = a->bounding_box().axis_interval(axis_index);
            auto b_axis_interval = b->bounding_box().axis_interval(axis_index);
            return a_axis_interval.min < b_axis_interval.min;
        }

        static bool box_x_compare (const shared_ptr<hittable> a, const shared_ptr<hittable> b) {
            return box_compare(a, b, 0);
        }

        static bool box_y_compare (const shared_ptr<hittable> a, const shared_ptr<hittable> b) {
            return box_compare(a, b, 1);
        }

        static bool box_z_compare (const shared_ptr<hittable> a, const shared_ptr<hittable> b) {
            return box_compare(a, b, 2);
        }

不过实际上我们是可以对这一部分优化的。我们希望构造出来的BVH树是均衡的，所以每次对场景内的物体进行划分时，我们希望，左右子树的分布是均衡的，这就要求我们每次选择的检测轴应该是边长最长的轴。为此我们需要一个函数为我们计算出包围盒的范围，我们将以此为依据实现更加平衡的BVH树结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bvh_node(std::vector<shared_ptr<hittable>>& objects, size_t start, size_t end) {
            bbox = aabb::empty;
    		// 对区间内的所有包围盒取并集 
            for(size_t object_index = start; object_index < end; object_index++)
                bbox = aabb(bbox, objects[object_index]->bounding_box());
            // 选择边长最大的维度 作为划分轴
            int axis = bbox.longest_axis();
            
            auto comparator = (axis==0) ? box_x_compare : (axis==1) ? box_y_compare : box_z_compare;

            size_t object_span = end - start;

            if(object_span == 1){
                left = right = objects[start];
            }else if(object_span == 2){
                left = objects[start];
                right = objects[start+1];
            }else{
                sort(std::begin(objects)+start, std::begin(objects)+end, comparator);
                auto mid = start + object_span/2;
                left = make_shared<bvh_node>(objects, start, mid);
                right = make_shared<bvh_node>(objects, mid, end);
            }

            bbox = aabb(left->bounding_box(), right->bounding_box());
        }

为了实现对最长轴的判断 和 包围盒并集的实现，我们需要优化我们的aabb类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class aabb{
    public:
		...
		// 取最长轴
        int longest_axis() const {
            if(x.size() > y.size())
                return x.size() > z.size() ? 0 : 2;
            else
                return y.size() > z.size() ? 1 : 2;
        }
		// 空包围盒 与 无限包围盒
        static const aabb empty, universe;
};

const aabb aabb::empty = aabb(interval::empty, interval::empty, interval::empty);
const aabb aabb::universe = 
    aabb(interval::universe, interval::universe, interval::universe);

至此我们就实现了图形的加速渲染。太爽了。

速度差不多提升3-4倍，随着场景规模的提升，这个提升的效果更加明显，可以借下面这个图来感受一下。我们差不多实现了从O(n)到O(logn)的优化：

image.png

发表于 分类于
本文字数： 795 阅读时长 ≈ 3 分钟

最近思绪有点乱，感觉要做的事情很多，但是不知道何从下手，所以我要从头缕一缕现在的问题。

首先是分析一下现阶段我要做的事情，按优先级进行分类：

  • 课程任务：（这几门课是这个学期的大头）
    • 离散数学：这个课我现在最大的问题就是没有明确的学习路线（对着书硬啃？找个网课学？）
    • 概率论：这个课我的进度很慢，但是有一高数的课程可以跟着学习，可以从现在开始每天学一点
    • 操作系统：这个课我学的还行，但是我对自己有一定的要求，不想只是简单学会
    • 计算机组成原理：这个课的应试考法我也不是很熟悉，对于数据的部分不是很熟悉，其他的还可以，但是我对自己也有一定的有要求
    • 数据结构：这门课学的还行，但是不熟悉应试的考法
    • 密码学：目前不清楚考试考察的方向，需要花时间巩固
    • Python：现在要开始准备大作业
    • Java：需要对着PPT再进一步学习，需要准备大作业
    • 毛思想：需要了解一下考什么，和题型。考前需要花时间学习一下
  • 课外任务：
    • 科研任务：科研训练从和开始入手，怎么去查看论文，怎么去找创新点，怎么去构建项目。
    • 个人任务：
      • 锻炼身体：需要加强身体的锻炼和饮食的均衡
      • 练习英语：提升英语水平
      • CTF二进制安全竞技水平
      • 学习新知识
      • 看书阅读

这里加粗的部分是需要着重注意的地方，那么我该怎么安排呢？

生活上的安排

首先是睡眠，每天十二点必须上床，手机最多玩到十二点半就要睡觉。有早八就七点一十起床，没早八就八点起床。周日可以休息久一点

每天早上至少喝一瓶牛奶，还有早餐。在寝室的期间要喝热水。平时尽量不喝奶茶喝其他饮料，也要控制自己的饮食，不能像以前一样想怎么吃就怎么吃。

平时要坚持锻炼，一周至少锻炼4次，两次耐力，两次力量。没事的时候可以在寝室举哑铃

每天要积极一点，心情不好就出去走一走，要开心。

节假日和周六晚上可以玩久一点游戏，平时尽量少玩一点。要珍惜现在的时间。

学习上的安排

除掉周日，单日学概率论，双日学离散数学，每天至少完成一个章节的学习。在什么课上学什么的知识，不能拆东墙补西墙。

这周之内要开始科研训练的内容，首先给出自己一个项目的框架，可行demo

课余的时间学什么由自己决定，优先课程的任务。

感情上的安排

别想太多 要接受分开的事实 继续走下去

发表于 分类于 ，
本文字数： 3.8k 阅读时长 ≈ 14 分钟

上个学期也尝试了解过这些，但是那个时候还没有接触编译链接，对DWARF信息的理解不够深刻。最近有计划了解一下调试器的原理，所以重新捡起来好好学一遍。

我参考的教程是DWARF的官方介绍文档Debugging using DWARF，作为对其的简单了解

DWARF概述

一开始我并不知道怎么说明这一部分，AI给了我一个很好的比方。如果说程序是一个设计图纸（源代码），它事无巨细的包含一个城市的所有信息，那么编译器就是一个工程师，他根据设计图纸将建造出城市（可执行文件）。而DWARF信息，就相当于这个城市的地图，它告诉你每条街道（机器指令，数据信息）对应设计图中的哪个位置（源代码）。而调试器就是一个导游，它根据这个地图带你去任何地方。

现代的编程语言大多是块状结构的，一个实体往往包含着更多的实体，每个实体中可能都有若干个数据和函数定义，那么在这个实体中，就产生了词法的作用域。这个定义仅在被定义的作用域中有意义。

我们可以用一个常见的文件结构来描述这种特征：

1
2
3
4
5
6
7
8
9
10
源文件
├── 函数A
│   ├── 变量x
│   ├── 语句块1
│   │   ├── 变量y (只在当前块内有效)
│   │   ├── 函数C
│   │   └── ...
│   └── ...
└── 函数B
    └── ...

对于数据和函数一类的内容，我们按照编译链接的习惯，称之为符号。一般情况下，一个符号的作用域属于当前块（也可以通过关键词指定作用域范围）。所以我们要查找特定符号的定义，先从当前作用域中查找定义，然后从连续的外层定义域中依次查找，直到找到该符号。

1
2
3
4
5
6
7
8
int global_var;          // 全局作用域
void my_function() {     // 函数作用域
    int local_var;       // 函数内有效
    if (condition) {
        int block_var;   // 只在if块内有效
    }
    // block_var 在这里结束
}

但是在编译链接的过程中，这些信息会被抛弃或者是简化。因为编译器只在乎对内存和寄存器的管理和操作，所以我们很难根据机器指令去恢复这些信息。

所以这里我们就需要DWARF信息来保存这些信息，DWARF和程序语义一样，通过树状结构来组织信息。DWARF中的所有描述性实体都包含在一个父条目中，且实体中还可以包含更多节点，这些节点可能表示类型，变量或是函数…一个常见的结构可以是下面这样的：

1
2
3
4
5
6
7
8
9
10
11
12
编译单元 (CU)
├── 函数: main
│   ├── 类型: int
│   ├── 变量: argc
│   ├── 变量: argv
│   └── 代码位置: 0x400500-0x400600
├── 函数: add
│   ├── 参数: a (int)
│   ├── 参数: b (int) 
│   ├── 局部变量: result (int)
│   └── 代码位置: 0x400610-0x400650
└── 全局变量: global_counter

而接下来，我们将学习怎么去理解这些常见的DWARF信息

调试信息条目（DIE）

标签与属性

DWARF 中的基本描述实体是调试信息条目。一个 DIE 包含一个标签——用于指定该 DIE 描述的是什么，以及一个属性列表——用于填充细节并进一步描述该实体。除了最顶层的 DIE 外，每个 DIE 都包含在或归属于一个父 DIE，并且可能拥有兄弟 DIE 或子 DIE。属性可以包含各种值：常量（例如函数名）、变量（例如函数的起始地址），或者指向另一个 DIE 的引用（例如函数返回值的类型）

例如下图中就展示了一个简单的程序的DWARF信息：

image.png

最上面的是CU编译单元，它作为DWARF信息的根节点，包含了两个下级DIE。其中一个描述main的信息，如返回类型、行号、函数起始地址…另一个DIE描述的是int类型，通过子程序DIE中的Type属性而被引用。

DIE类型

DIE可以分为两种通用类型：

  • 一类用来描述数据的DIE
  • 另一类用来描述函数或者其他可执行代码

基础类型->数据类型

大多数语言都有复杂的数据类型体系，例如内置数据类型、指针、数据结构、自定义结构等类型。这些基于语言底层设计的主要类型我们称之为基础类型，其他的数据类型都由这些基础类型构造而成。

一个具名变量由一个拥有多种属性的 DIE 描述，其中一个属性是对类型定义的引用。下图就描述了一个名为x的整型变量：

image.png

int 的基础类型将其描述为一个占用四个字节的有符号二进制整数。用于变量 x 的 DW_TAG_variable DIE 给出了它的名称和一个类型属性，该属性引用了基础类型 DIE。

同样的，DWARF 也可以使用基础类型通过组合来构建其他数据类型定义。一个新类型是作为对另一个类型的补充而创建的。以下面这个int* px的DIE信息为例：

image.png

这个 DIE 定义了一个指针类型，指明其大小为四个字节，并继而引用了 int 基础类型。

还可以更复杂的，比如加上关键词去限定这个变量的属性和类型，也可以将更多类型的DIE链接在一起以描述更复杂的数据类型，例如const char ** argv的DIE信息如下：

image.png

总的来说，在DWARF信息中，我们通过组合基本类型的方式来表示程序语言中的数据类型。这样我们无需了解所有程序语言的数据结构，也可以描述出数据类型的信息。

常见类型

数组

数组类型由DW_TAG_array_type表示，对于int arr[10]，其一般DWARF结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
< 1><0x0000002e>    DW_TAG_array_type
                      DW_AT_type                  <0x00000045>
                      DW_AT_sibling               <0x0000003e>
< 2><0x00000037>      DW_TAG_subrange_type
                        DW_AT_type                  <0x0000003e>
                        DW_AT_upper_bound           9
< 1><0x0000003e>    DW_TAG_base_type
                      DW_AT_byte_size             0x00000008
                      DW_AT_encoding              DW_ATE_unsigned
                      DW_AT_name                  long unsigned int
< 1><0x00000045>    DW_TAG_base_type
                      DW_AT_byte_size             0x00000004
                      DW_AT_encoding              DW_ATE_signed
                      DW_AT_name                  int
< 1><0x0000004c>    DW_TAG_variable
                      DW_AT_name                  arr
                      DW_AT_decl_file             0x00000001 /home/ylin/Program/test/./test.c
                      DW_AT_decl_line             0x00000001
                      DW_AT_decl_column           0x00000005
                      DW_AT_type                  <0x0000002e>
                      DW_AT_external              yes(1)
                      DW_AT_location              len 0x0009: 0x034040000000000000:
                          DW_OP_addr 0x00004040

其中DW_TAG_subrange_type用来存储描述数组维度的范围（下标范围），这里不仅指示了下标的上界DW_AT_upper_bound 9也指明了下标的数据类型DW_AT_type <0x0000003e>

我们可以看到左边的<1> <2>的符号，这代表当前条目在条目树结构中的深度。

理解了数据类型的结构分析之后，我们看到变量的定义信息：

  • DW_AT_name：变量名
  • DW_AT_decl_line：变量的定义行
  • DW_AT_decl_column：变量的定义列
  • DW_AT_type：变量定义类型
  • DW_AT_external：变量的作用域范围（全局符号）
  • DW_AT_location：变量在内存中的存储位置

通过这些信息，我们就可以还原出数组的数据类型、存储结构、以及在源代码中的定义位置等信息

结构、类、联合体、接口

大多数的语言都支持将各种数据类型的组合到一个结构体中，只不过不同的语言叫法不一样而已，这里的我们就简单的介绍一下结构体和类的标签。

结构体相较于类更加纯粹，它主要对数据进行封装，将不同的数据类型整合成一个大的结构体，在结构体中通过字段对这些数据进行索引，我们可以看下它的DWARF结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
< 1><0x0000002e>    DW_TAG_structure_type
                      DW_AT_byte_size             0x00000010
                      DW_AT_decl_file             0x00000001 /home/ylin/Program/test/./test.c
                      DW_AT_decl_line             0x00000001
                      DW_AT_decl_column           0x00000001
                      DW_AT_sibling               <0x00000052>
< 2><0x00000037>      DW_TAG_member
                        DW_AT_name                  age
                        DW_AT_decl_file             0x00000001 /home/ylin/Program/test/./test.c
                        DW_AT_decl_line             0x00000002
                        DW_AT_decl_column           0x00000009
                        DW_AT_type                  <0x00000052>
                        DW_AT_data_member_location  0
< 2><0x00000044>      DW_TAG_member
                        DW_AT_name                  name
                        DW_AT_decl_file             0x00000001 /home/ylin/Program/test/./test.c
                        DW_AT_decl_line             0x00000003
                        DW_AT_decl_column           0x0000000b
                        DW_AT_type                  <0x00000059>
                        DW_AT_data_member_location  8
< 1><0x00000052>    DW_TAG_base_type
                      DW_AT_byte_size             0x00000004
                      DW_AT_encoding              DW_ATE_signed
                      DW_AT_name                  int
< 1><0x00000059>    DW_TAG_pointer_type
                      DW_AT_byte_size             0x00000008
                      DW_AT_type                  <0x0000005f>
< 1><0x0000005f>    DW_TAG_base_type
                      DW_AT_byte_size             0x00000001
                      DW_AT_encoding              DW_ATE_signed_char
                      DW_AT_name                  char
< 1><0x00000066>    DW_TAG_variable
                      DW_AT_name                  student
                      DW_AT_decl_file             0x00000001 /home/ylin/Program/test/./test.c
                      DW_AT_decl_line             0x00000004
                      DW_AT_decl_column           0x00000002
                      DW_AT_type                  <0x0000002e>
                      DW_AT_external              yes(1)
                      DW_AT_location              len 0x0009: 0x032040000000000000:
                          DW_OP_addr 0x00004020

结构体类型由DW_TAG_structure_type进行表示，这里我们定义的结构体如下：

1
2
3
4
struct{
    int age;
    char* name;
}student;

我们可以阅读到以下结构体的属性：

  • DW_TAG_member：结构体的成员
  • DW_AT_data_member_location：字段在结构体中偏移值，我们可以通过这个值访问结构体中的成员
  • DW_AT_byte_size：结构体的大小（这里可以看出内存对齐了）
  • 还有典型的一些属性…

然后是类的，类相当于结构体的plus版，既可以组合数据类型，也可以包含函数方法，不过对于类的内存分布，我暂时也不是很清楚。我们可以看看类的DWARF信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
< 1><0x0000002a>    DW_TAG_class_type
                      DW_AT_name                  Student
                      DW_AT_byte_size             0x00000010
                      DW_AT_decl_file             0x00000001 /home/ylin/Program/test/test.cpp
                      DW_AT_decl_line             0x00000003
                      DW_AT_decl_column           0x00000007
                      DW_AT_sibling               <0x0000006d>
< 2><0x00000037>      DW_TAG_member
                        DW_AT_name                  ID
                        DW_AT_decl_file             0x00000001 /home/ylin/Program/test/test.cpp
                        DW_AT_decl_line             0x00000005
                        DW_AT_decl_column           0x0000000d
                        DW_AT_type                  <0x0000006d>
                        DW_AT_data_member_location  0
< 2><0x00000043>      DW_TAG_member
                        DW_AT_name                  name
                        DW_AT_decl_file             0x00000001 /home/ylin/Program/test/test.cpp
                        DW_AT_decl_line             0x00000008
                        DW_AT_decl_column           0x0000000f
                        DW_AT_type                  <0x00000074>
                        DW_AT_data_member_location  8
                        DW_AT_accessibility         DW_ACCESS_public
< 2><0x00000051>      DW_TAG_subprogram
                        DW_AT_external              yes(1)
                        DW_AT_name                  getID
                        DW_AT_decl_file             0x00000001 /home/ylin/Program/test/test.cpp
                        DW_AT_decl_line             0x00000009
                        DW_AT_decl_column           0x0000000d
                        DW_AT_linkage_name          _ZN7Student5getIDEv
                        DW_AT_type                  <0x0000006d>
                        DW_AT_accessibility         DW_ACCESS_public
                        DW_AT_declaration           yes(1)
                        DW_AT_object_pointer        <0x00000066>
< 3><0x00000066>        DW_TAG_formal_parameter
                          DW_AT_type                  <0x00000080>
                          DW_AT_artificial            yes(1)
< 1><0x0000006d>    DW_TAG_base_type
                      DW_AT_byte_size             0x00000004
                      DW_AT_encoding              DW_ATE_signed
                      DW_AT_name                  int
< 1><0x00000074>    DW_TAG_pointer_type
                      DW_AT_byte_size             0x00000008
                      DW_AT_type                  <0x00000079>
< 1><0x00000079>    DW_TAG_base_type
                      DW_AT_byte_size             0x00000001
                      DW_AT_encoding              DW_ATE_signed_char
                      DW_AT_name                  char
< 1><0x00000080>    DW_TAG_pointer_type
                      DW_AT_byte_size             0x00000008
                      DW_AT_type                  <0x0000002a>
< 1><0x00000085>    DW_TAG_const_type
                      DW_AT_type                  <0x00000080>

类的类型由DW_TAG_class_type进行表示，这里我们定义的类是这样的：

1
2
3
4
5
6
7
8
9
10
class Student{
    private:
        int ID;

    public:
        char* name;
        int getID(){
           return ID;
        }
};

我们可以阅读以下类的信息：

  • DW_TAG_subprogram：这里表示这是类的一个方法，之后会详细描述一下这个标签
  • DW_AT_accessibility：用来指出数据和方法的成员属性（公/私），默认为私有，DW_ACCESS_public为公有
  • DW_AT_object_pointer：这个是隐含得参数指向this指针参数。

类由还有很多标签，但是这里不过多进行讲解。

变量

变量通常相当简单。它们有一个名称，代表一块可以存储某种值的内存（或寄存器）。变量可以包含的值的种类，以及对其修改方式的限制（例如，是否为 const），都由变量的类型来描述。

区分变量的关键在于其值的存储位置和其作用域。变量的作用域定义了变量在程序中的哪些位置是已知的，并在某种程度上由变量声明的位置决定。在 C 语言中，在函数或块内声明的变量具有函数或块作用域。在函数外声明的变量具有全局或文件作用域。这允许在不同文件中定义同名的变量而不会冲突，也允许不同的函数或编译单元引用同一个变量。

DWARF 将变量分为三类：常量、形式参数和变量。

  • 常量用于那些语言本身包含真正具名常量的情况，例如 Ada 参数。（C 语言本身没有将常量作为语言的一部分。声明一个 const 变量只是表示你不能在没有使用显式类型转换的情况下修改变量。）
  • 形式参数表示传递给函数的值。我们稍后再讨论这个。

大多数变量都有一个位置属性，用于描述变量的存储位置。

  • 在最简单的情况下，变量存储在内存中并具有固定地址。
  • 但是许多变量，例如在 C 函数内声明的变量，是动态分配的，定位它们需要进行一些（通常简单的）计算。例如，一个局部变量可能在栈上分配，定位它可能简单到只需给帧指针加上一个固定偏移量。
  • 在其他情况下，变量可能存储在寄存器中。
  • 其他变量可能需要更复杂一些的计算来定位数据。作为 C++ 类成员的变量可能需要更复杂的计算来确定基类在派生类中的位置。

可执行代码段：函数与子程序

这里的函数和子程序实际上是同一个东西，硬要细分的话，函数是有返回值的，而子程序没有（我们更多是利用子程序的副作用）。我们可以看一下函数会包含的DWARF信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
< 1><0x00000065>    DW_TAG_subprogram
                      DW_AT_external              yes(1)
                      DW_AT_name                  hello
                      DW_AT_decl_file             0x00000001 /home/ylin/Program/test/test.c
                      DW_AT_decl_line             0x00000001
                      DW_AT_decl_column           0x00000005
                      DW_AT_prototyped            yes(1)
                      DW_AT_type                  <0x0000005e>
                      DW_AT_low_pc                0x00001129
                      DW_AT_high_pc               <offset-from-lowpc> 24 <highpc: 0x00001141>
                      DW_AT_frame_base            len 0x0001: 0x9c:
                          DW_OP_call_frame_cfa
                      DW_AT_call_all_calls        yes(1)
< 2><0x00000083>      DW_TAG_formal_parameter
                        DW_AT_name                  x
                        DW_AT_decl_file             0x00000001
                        DW_AT_decl_line             0x00000001
                        DW_AT_decl_column           0x0000000f
                        DW_AT_type                  <0x0000005e>
                        DW_AT_location              len 0x0002: 0x916c:
                            DW_OP_fbreg -20
< 2><0x0000008e>      DW_TAG_formal_parameter
                        DW_AT_name                  y
                        DW_AT_decl_file             0x00000001
                        DW_AT_decl_line             0x00000001
                        DW_AT_decl_column           0x00000016
                        DW_AT_type                  <0x0000005e>
                        DW_AT_location              len 0x0002: 0x9168:
                            DW_OP_fbreg -24

首先我们可以看到包含源代码位置信息的三元组（文件、行、列），然后是函数的高低内存范围，一般情概况下，我们默认函数的低内存地址（起始地址）为函数的入口。函数的返回类型，由类型属性指定。

这里需要注意的是DW_OP_call_frame_cfa指定的CFA0x9c。CFA就是函数执行时，其调用者的栈帧的栈顶位置，标志着一个函数栈帧的开始边界。以下图结构为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
（高地址）
+----------------------+
| ...                  |
| main 的局部变量       | <--- main 函数的栈帧
+----------------------+
| 返回地址              | <--- [!] hello 函数的 CFA 指向这里
+----------------------+------ hello 函数栈帧的“边界”
| 保存的 RBP (帧指针)   | <--- 帧基址 (Frame Base) 常常指向这里
+----------------------+
| hello 的局部变量      |
| ...                  |
|  可能还有保存的寄存器  |
+----------------------+ <--- 当前 RSP 指向这里（栈顶）
（低地址）

在我们的示例中，DWARF信息指出DW_AT_frame_base : DW_OP_call_frame_cfa，所以这里我们的栈基址等于CFA值。基于栈基址，我们就可以对被调用栈帧中的变量进行访问。我们看到DW_AT_location的属性下，通常有DW_OP_fbreg - 偏移值的形式来计算参数在栈帧上的位置。

DWARF不定义函数的调用约定，这一部分有应用程序二进制接口规范确定（ABI）

编译单元

大多数的程序室友多个文件构成的，每个文件会被独立编译，然后与系统库链接成最终的程序，DWARF将每个独立编译的源文件称为一个编译单元

每个编译单元的DWARF数据，都会从一个编译单元调试信息项开始。该调试信息项包含编译过程中的通用信息

1
2
3
4
5
6
7
8
< 0><0x0000000c>  DW_TAG_compile_unit
                    DW_AT_producer              GNU C17 13.3.0 -mtune=generic -march=x86-64 -g -O0 -fasynchronous-unwind-tables -fstack-protector-strong -fstack-clash-protection -fcf-protection
                    DW_AT_language              DW_LANG_C11
                    DW_AT_name                  test.c
                    DW_AT_comp_dir              /home/ylin/Program/test
                    DW_AT_low_pc                0x00001129
                    DW_AT_high_pc               <offset-from-lowpc> 61 <highpc: 0x00001166>
                    DW_AT_stmt_list             0x00000000

包括：

  • 编译器和编译参数
  • 源文件的目录路径和文件名称
  • 编译单元在内存中的起始结束地址（如果编译单元在内存中是连续的）
  • 编译单元占用内存的地址列表（如果编译单元在内存中非连续）
  • 指向调试器行号的指针(DW_AT_stmt_list)

编译单元调试信息项是所有该编译单元调试信息的父项。一般情况下，调试信息会先描述数据类型，接着是全局数据，然后再是子函数。

至此基本的DWARF信息就介绍到这里。

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 5 分钟

也是好不容易水到第100篇了，我本来准备了好多台词的，但是不知道说什么。我就记录一下我的几个感悟吧

学会放弃

刚开始觉得只要努力学就会有所收获吧，如果没学会就是自己比较笨什么的。但事实不是这样的，认知一个领域的过程是循序渐进的，就像游戏里的科技树一样，解锁一个科技需要一大堆前置科技。有时候一些知识也是这样，所以一开始学不会一些东西很正常，这个时候应该先放一放，去试试其他的方向，或者是从前置的内容开始学。

关于这一点我的感受就很明显吧，我每次遇到学不会的东西，就会放弃然后去学其他的东西。但是过一段时间之后再来看这些内容反而有一种水到渠成的感觉，我猜测一个是知识体系上的补齐，还有一个是你对这个领域的认知能力也在慢慢变强。你能对一些内容做出自己的解释，能说服自己我认为是理解一个知识的开始吧。不管你的猜想是不是对的，只要他能补齐你对这方面的认识，你就可以视作自己理解了。之后随着需求和认知的提升，再一步步完善自己对这方面的理解吧。

我发现生活中也有很多这样的事情，给你一种无从下手或者无能为力的感觉。如果实在不行就放弃吧，可以之后再试试，先把其他的事情做好，也许很多事情时间会给出答案，因为我们每天都在慢慢长大。只要不放弃从头再来的决心，迟早有一天也能找到自己的答案。

主动学习

大家都在学习凭什么，也不存在谁比谁笨，为什么有的人能学会有的人不能呢？我认为这不是努不努力的事情，大家回宿舍都是打游戏，如果能认真学下去，活该他学的好。我觉得更多是对于这个知识的态度吧，有的人是被动的接受的，有的人是主动的接受的。主动接受的话你就会发现很多问题啥的，就是你的脑子里的东西和答案不一样，或者你脑子里没有这个东西。在这个不断碰撞思考的过程中，你的知识体系会被答案说服或者补全，这样你的认知体系就会慢慢完善，感觉这个就是高中老师说的框架/查漏补缺，这个就是主动学习。但是大多数人就是书上讲得是啥就是啥，老师说啥就是啥，一上来就记住正确答案，对知识很内容知其然不知其所以然，这种效率就很差。中国传统的应试教育就是这样的，所以大家都是这样的，我也是这样的。

这也是为什么比起看网课我更喜欢看书，看网课的时候，老师叽里咕噜讲个不停，你很难有自己思考的时间，更别说有时候发呆什么的。但是看书不一样，你不懂得时候可以对着书上得那句话发呆，等你发完呆它还在那里，你就有充分得时间去理解它，或者再来一遍。就是这个时候你的大脑是属于你自己的，你的想法不是跟着别人走的，更自由一点。这样你就能做出更多自己的思考。

我知道这样子很不好，但是有时候动脑子真的好累，偶尔主动学习一些重要的东西也还行。我的话有时候突然想做项目或者刷视频看到什么好帅的东西，我会迫不及待的去了解一下。主要是对游戏方面感兴趣一点

要有耐心

就是电视上和老师经常说的要坐的住冷板凳吧，有时候学一些东西确实挺牢的，就是很无聊，知识从脑袋里滑走了。这个时候就是看你有没有耐心了，感觉这个和我第一条说的是相反的，按道理这种情况是要放弃的，但是有时候就是不太想放弃，你就需要耐心一点。所以这么看来放弃是一件很理性的事情，坚持反而是一件很感性的事情。回到正题，我想说的是，人生的常态就是失败和无聊，但是不耐心去做一件事的话就会错过很多东西。什么时候放弃，什么时候坚持是一件很哲学的问题吧。我到这里也不知道说什么好了。

今天就暂时写到这些吧，希望之后的时间也能继续加油。现在虽然学了很多东西，但是没办法把知识串联在一起，也有点迷茫。有时候分析一些问题的时候，反而会因为知道的太多而被绕进去。就像之前不知道从哪里看到的三大境界：

  • 看山是山 看水是水
  • 看山不是山 看水不是水
  • 看山还是山 看水还是水

我现在可能介于一二之间吧，很难受，技术不到家，看很多东西都是残破不堪的，漏洞百出，我自己也知道。希望以后能慢慢解决这个这个问题吧。还有就是我现在也遇到了一些生活中难以解决的问题，我也不知道怎么做，在迷茫的时候还是要坚定的提升自己，也许以后时间会给出答案吧。之后也要继续加油。

发表于 更新于 分类于 ，
本文字数： 2.4k 阅读时长 ≈ 9 分钟

今天接着来认识一下图，结束了图的学习，数据结构的部分就告一段落了。之后就是涉及到一些基本的算法问题，感觉也会越来越难。

图

认识图

和之前的数据结构不同，图是一种非线性的结构，由顶点和边组成，以下面为例，我们可以将图G抽象的表示成一组顶点和一组边的集合：

1
2
3
V = {1,2,3,4,5}
E = {(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(4,5)}
G = {V,E}

如果将顶点看作节点，将边看作连接各个节点的引用（指针），我们就可以将图看作一种从链表拓展而来的数 据结构。

image.png

图的常见类型和术语

结合不同的场景，我们可以从不同的角度对图进行分类：

  • 根据边是否具有方向，分为有向图和无向图
  • 根据顶点直接是否全部联通，分为联通图和非联通图
  • 根据边上的权重，非为无权图和有权图
  • ….

在不同的场景中我们选择合适的类型，来解决问题。

图的数据结构有以下常用术语：

  • 邻接：当两顶点之间存在边相连时，称这两个顶点邻接
  • 路径：从顶点A到顶点B经过的边构成的序列被称为从A到B的路径
  • 度：一个顶点拥有的边数。对有向图，根据边的方向，还分为入度和出度。

图的表示

图通常使用两种表示方式，我们这里均以无向图为例：

邻接矩阵

设图的顶点数量为𝑛，邻接矩阵使用一个n×n大小的矩阵来表示图，每一行（列）代 表一个顶点，矩阵元素代表边，用1或0表示两个顶点之间是否存在边。

设邻接矩阵为𝑀、顶点列表为𝑉 ，那么矩阵元素𝑀[𝑖,𝑗]=1表示顶点𝑉[𝑖]到顶点𝑉[𝑗] 之间存在边，反之𝑀[𝑖,𝑗]=0表示两顶点之间无边。

image.png

邻接矩阵有以下性质：

  • 在简单图中，顶点不能和自己相连，所以邻接矩阵主对角线上的元素是没有意义的
  • 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称
  • 将邻接矩阵的元素替换成权重就是有权图

邻接表

邻接表使用n个链表来表示图，链表节点表示顶点。第i个链表对应顶点i，其中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）。如下图：

image.png

两种表示方法的比较

对于邻接矩阵，我们可以直接访问矩阵元素实现对边的CRUD，时间效率高达O(1)。但是矩阵存储的空间复杂度为O(n2)

对于邻接表，由于表中只存储实际已存在的边数，而边数通常小于n2，所以空间存储的效率上来看，邻接表要更加的节省空间。但是对于CRUD的操作，邻接表需要通过遍历搜索的方式来进行，所以时间效率更差。

但是结合先前的只是，对于这种链表较长的情况，我们可以将它优化成哈希表或者AVL树等结构，实现对时间效率的优化，所以对于大规模的图的使用场景，邻接表也更加普遍。

图的基本操作

图的操作主要可以分为对顶点和对边的操作，这里分别通过邻接矩阵和邻接表的方式进行实现。

基于邻接矩阵的实现

给定给一个顶点数量为n的无向图，我们需要完成以下操作：

  • 添加或删除边：直接在邻接矩阵修改指定的边，只不过要注意同时更新两个方向的边（无向图）
  • 添加顶点：在邻接矩阵的尾部添加一行一列，并初始化为0即可。
  • 删除顶点：在邻接举证中删除一行一列，将剩下的元素向左上补齐。对于最坏的情况（删除首行首列）需要移动(n − 1)2个元素
  • 初始化：传入n个顶点，初始化长度为n的顶点列表和nxn大小的邻接矩阵
image.png

我们的具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class GraphMap{
    private:
        vector<int> vertices;           // 顶点列表
        vector<vector<int>> adjMat;     // 邻接矩阵
    
    public:
        GraphMap(const vector<int> &vertices, const vector<vector<int>> &edges){
            for(int val : vertices)
                addVertex(val);
            for(const vector<int> &edge : edges)
                addEdge(edge[0],edge[1]);
        }

        int size() const{
            return vertices.size();
        }

        void addVertex(int val){
            int n = size();
            vertices.push_back(val);
            // 向邻接矩阵中添加一行
            adjMat.emplace_back(vector<int>(n,0));
            for(vector<int> &row: adjMat)
                row.push_back(0);
        }

        void removeVertex(int index){
            if(index >= size())
                throw out_of_range("顶点不存在");
            vertices.erase(vertices.begin() + index);
            // 删除行
            adjMat.erase(adjMat.begin() + index);
            // 删除列
            for(vector<int> &row : adjMat)
                row.erase(row.begin() + index);
        }

        void addEdge(int i,int j){
            if(i<0 || i>=size() || j<0 || j>=size() || i==j)
                throw out_of_range("顶点不存在");
            adjMat[i][j] = 1;
            adjMat[j][i] = 1;
        }

        void removeEdge(int i,int j){
            if(i<0 || i>=size() || j<0 || j>=size() || i==j)
                throw out_of_range("顶点不存在");
            adjMat[i][j] = 0;
            adjMat[j][i] = 0;
        }
};

基于邻接表的实现

设无向图的顶点总数为n、边总数为m，我们需要完成以下操作：

  • 添加边：在顶点对应链表的末尾添加边就行了。但是要注意无向图要加两个方向的边
  • 删除边：在顶点管理的链表中查找并删除指定的边。无向图中删两个方向。
  • 添加顶点：在邻接表中添加一个链表，并将新增顶点作为链表头节点
  • 删除顶点：遍历整个邻接表，删除包含指定顶点的所有边
  • 初始化：在邻接表中创建n个顶点和2m条边
image.png

以下是邻接表的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class GraphList{
    private:
        unordered_map<Vertex* ,vector<Vertex*>> adjList;

        void remove(vector<Vertex*> &vec, Vertex* vet){
            for(int i=0;i<vec.size();i++){
                if(vec[i]==vet){
                    vec.erase(vec.begin()+i);
                    break;
                }
            }
        }

    public:
        GraphList(const vector<vector<Vertex*>> &edges){
            for(const vector<Vertex *> & edge: edges){
                addVertex(edge[0]);
                addVertex(edge[1]);
                addEdge(edge[0],edge[1]);
            }
        }

        int size(){
            return adjList.size();
        }

        void addVertex(Vertex* vet){
            if(adjList.count(vet))
                return;
            adjList[vet] = vector<Vertex*>();
        }

        void removeVertex(Vertex* vet){
            if(!adjList.count(vet))
                throw invalid_argument("不存在顶点");
            adjList.erase(vet);
            for(auto &adj : adjList)
                remove(adj.second,vet);
        }

        void addEdge(Vertex* vet1, Vertex* vet2){
            if(!adjList.count(vet1) || !adjList.count(vet2) || vet1==vet2)
                throw invalid_argument("不存在顶点");
            adjList[vet1].push_back(vet2);
            adjList[vet2].push_back(vet1);
        }

        void removeEdge(Vertex* vet1, Vertex* vet2){
            if(!adjList.count(vet1) || !adjList.count(vet2) || vet1==vet2)
                throw invalid_argument("不存在顶点");
            remove(adjList[vet1],vet2);
            remove(adjList[vet2],vet1);
        }
};

这里为了方便，我们使用动态数组代替了链表。用哈希表来表示邻接表结构。

同时需要注意在邻接表中我们使用Vertex类来表示顶点，也是为了方便。如果我们使用列表索引来区分不同德顶点的话，那么每当我们删除一个索引为i的顶点，就需要遍历整个邻接表，把所有索引大于i的顶点重新更新一遍，这样的话效率就很差。

图的遍历

树代表的是一对多的关系，图代表的是多对多的关系，所以我们可以将树视作图的一个特例。所以说树的遍历操作实际上也是图的遍历操作的一种特例。

和树类似的，我们有两种遍历方式实现对图的遍历操作：广度优先遍历和深度优先遍历

广度优先遍历

广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外 扩张。以下图为例：

image.png

从左上角顶点出发，首先遍历该顶点的所有邻接顶点，然后遍历下一个顶点的所有邻 接顶点，以此类推，直至所有顶点访问完毕。

算法实现

BFS通常需要一个辅助队列来实现，通过队列先进先出的性质，实现BFS由近及远的思路。我们的实现流程如下：

  • 将遍历起始顶点startVet加入队列中，开始循环
  • 在每次迭代中，弹出队首顶点并访问，将该顶点的所有邻接点加入到队列尾部
  • 循环上一步，知道队列为空

同时我们还需要一个哈希集合visited来记录哪些节点被访问，以防止重复遍历顶点。

我们的具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<Vertex*> graphBFS(GraphList &graph, Vertex* startVet){
    vector<Vertex*> res;				// 返回的顶点序列
    unordered_set<Vertex*> visited;		 // 哈希集合,用来记录被访问过的顶点	
    queue<Vertex*> que;					// 辅助队列	
    que.push(startVet);
    while(!que.empty()){
        Vertex* vet = que.front();
        que.pop();
        res.push_back(vet);
        for(auto adjVet : graph.adjList[vet]){
            if(visited.count(adjVet))
                continue;				// 跳过已访问的顶点
            que.push(adjVet);
            visited.emplace(adjVet);
        }
    }
    return res;
}

可以通过画图的方法帮助理解一下这个过程

深度优先遍历

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。以下图为例

image.png

算法实现

这种走到尽头并返回的样式，我们可以通过递归的方式实现。关键在于怎么设置边界条件，退出递归。我们的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(GraphList &graph, unordered_set<Vertex*> &visited,
         vector<Vertex*> &res, Vertex * vet){
    // 记录访问节点
    res.push_back(vet);
    // 标记已访问节点
    visited.emplace(vet);
	// 遍历所有邻接顶点
    for(Vertex* adjVet : graph.adjList[vet]){
        if(visited.count(adjVet))
            continue;
        // 递归访问邻接顶点
        dfs(graph,visited,res,adjVet);
    }
}

vector<Vertex*> graphDFS(GraphList &graph, Vertex* startVet){
    // 顶点遍历序列
    vector<Vertex*> res;
    // 以访问过的顶点
    unordered_set<Vertex*> visited;
    dfs(graph,visited,res,startVet);
    return res;
}

可以自己尝试手推一下这个过程，加深理解。

发表于 更新于 分类于 ，
本文字数： 1.8k 阅读时长 ≈ 7 分钟

学一种新的数据结构——“堆”，但是貌似和底层原理中的堆并不一样。之前总是略有耳闻，但是一直都很少仔细去了解。

堆

堆是一种满足特定条件的完全二叉树，根据性质可以分为两种类型：

  • 小顶堆：任意节点的值 <= 子节点的值
  • 大顶堆：任意节点的值 >= 子节点的值
image.png

堆作为完全二叉树的一个特例，有以下规则：

  • 最底层的节点靠左排列，其他层被节点填满。
  • 二叉树的根节点被称为堆顶，二叉树底层靠右的节点称为堆底
  • 对于大(小)顶堆，堆顶元素的值是最大(小)的

堆的常用操作

有一种抽象的数据结构——优先队列，定义为具有优先级排序的队列。通常我们会使用堆来实现优先队列，大顶堆就相当于元素按大到小的顺序出队的优先队列。这里我们将其视作等价的数据结构。

这里我们先通过优先队列来认识一下堆的一些操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main(){
    priority_queue<int, vector<int>, greater<int>> minheap;
    priority_queue<int, vector<int>, less<int>> maxheap;

    maxheap.push(1);
    maxheap.push(5);
    maxheap.push(4);
    maxheap.push(2);
    maxheap.push(2);
    maxheap.push(3);

    cout << "The size is " << maxheap.size() << endl;
    int top = maxheap.top();
    cout << "The top is " << top << endl;

    bool isEmpty = maxheap.empty();

    return 0;
}

常用的可以总结为以下几类：

image.png

堆的实现

现在我们尝试从底层实现一个堆，这里我们用大顶堆演示，小顶堆只需要将所有的大小逻辑判断反转即可。

堆的存储和表示

堆是一种完全二叉树，我们之前提到过完全二叉树十分适合用数组来进行存储，所以这里我们的底层实现选择用数组，和之前的实现一样。我们使用索引的映射公式来代替节点指针：

1
2
3
4
5
6
7
8
9
10
11
int left(int i){
    return 2*i+1;
}

int right(int i){
    return 2*i+2;
}

int parent(int i){
    return (i-1)/2;
}

访问堆顶元素

堆顶元素就是二叉树的根节点，也就是我们数组的首元素：

1
2
3
4
5
6
7
8
9
10
class Heap{
    public:
		...
        int peek(){
            return heap[0];
        }
		...
    private:
        vector<int> heap;
};

元素入堆

给定val，我们将其添加到堆底。但是此时插入的值可能会破坏当前到根节点的路径，导致堆的成立条件被破坏。所以我们需要遍历修复从插入节点到根节点路径上的所有节点，这个过程我们称之为堆化

从入堆节点开始，我们从底执行堆化。我们依次比较当前节点和父节点的大小，如果插入节点更大就讲他们交换，知道修复所有的节点关系。

image.png

我们可以通过以下方式实现这个过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
      void push(int i){
          heap.push_back(i);
          // 从堆底开始堆化
          siftUp(heap.size()-1);
      }
	
// 堆化
      void siftUp(int i){
          while(true){
              int p = parent(i);
              if(p<0 || heap[i] <= heap[p])
                  break;

              swap(heap[i],heap[p]);
              // 向上堆化
              i=p;
          }
      }

堆顶元素出栈

堆顶元素是二叉树的根节点，如果我们直接从数组中删除首元素，那么会破坏整个树的树状结构，这导致后续的堆化难以修复。所以我们采取以下步骤将堆顶元素出栈：

  • 交换堆顶元素（根节点）和堆底元素（最右元素）
  • 交换完成之后，我们将堆底删除
  • 从根节点开始自顶向底执行堆化

自顶向下的堆化和自底向上的堆化逻辑相反，我们将当前节点和较大的子节点进行比较，然后进行交换，直到没有子节点或者无需再交换了：

image.png

出堆的实现方式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void pop(int i){
    if(heap.empty())
        throw out_of_range("堆为空");
    swap(heap[i], heap[heap.size()-1]);
    heap.pop_back();
    siftDown(0);
}

void siftDown(int i){
    while(true){
        // ma为较大的节点
        int l=left(i), r=right(i), ma = i;
        if(l < heap.size() && heap[i] < heap[l])
            ma = l;
        if(r < heap.size() && heap[i] < heap[r])
            ma = r;
        // l,r越界或者i已经是最大节点 则退出堆化
        if(ma==i)
            break;
        swap(heap[i],heap[ma]);
        i = ma;
    }
}

建堆操作

我们希望能直接根据一个列表中的所有元素来构建一个堆。我们有两种可行的方案：

  • 创建一个空堆，然后遍历列表，对每一个元素都进行入堆操作。但是对于n个元素执行复杂度为O(logn)的入堆操作，时间复杂度会增长到O(nlogn)
  • 另一个方法就是，将列表中的元素添加到完全二叉树中，尽管现在的堆的性质并没有被满足。接下来我们倒序遍历堆，并对每个非叶节点进行一次自顶向下的堆化。这样每当我们堆化一个节点之后，都会以该节点为根节点形成一个子堆。

这里我们着重分析一下第二种方法。我们可以通过以下方法实现：

1
2
3
4
5
6
Heap(vector<int> vec){
    heap = vec;
    // 倒序遍历的第一个非叶节点 就是最后一个叶节点的父节点
    for(int i=parent(heap.size()-1); i>=0; i--)
        siftDown(i);
}

这个方法下的复杂度被优化到了O(n)，更加的便捷。

Top-k问题

所谓top-k问题，就是给定一个长度为n的无序数组nums，请返回数组中最大的k个元素。

对于这个问题我们有很多种解决方案：

遍历选择

我们可以像这样对一个长度为n的序列进行k次遍历，每轮遍历都提取出当前序列中的最大的数据。时间复杂度为O(nk)。当k接近n时，时间复杂度增长到O(n^2)

image.png

排序

先对数组nums进行排序，然后再返回最右边的k个数据。这个方法主要取决于对数组排序的时间复杂度，对于std::sort，这个方法的复杂度是O(nlogn)

堆

我们可以基于堆更加高效的完成这个任务，我们遵循以下步骤实现：

  • 初始化一个小顶堆，此时其堆顶元素最小。
  • 然后将数组的前k个元素依次入堆
  • 从第k+1个元素开始，如果当前元素大于堆顶元素，我们就将堆顶出堆，并将当前元素入堆。
  • 遍历完成之后，堆中保存的就是最大的k个元素。

我们可以写出以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
priority_queue<int, vector<int>, greater<int>> topHeap(vector<int> nums, int k){
    priority_queue<int, vector<int>, greater<int>> heap;
    for(int i=0;i<k;i++)
        heap.push(nums[i]);
    for(int i=k;i<nums.size();i++){
        if(heap.top() < nums[i]){
            heap.pop();
            heap.push(nums[i]);
        }
    }
    return heap;
}

总共进行了n轮入堆和出堆，由于堆大小是固定的k，所以我们只需要维护k个元素，所以实际上我们的计算复杂度只有O(nlogk)，在k较小时，我们的时间复杂度约等于O(n)

由此可以看到通过堆的思路，对解决TopK问题的显著提升。尤其是对于这种方法，适用于动态数据流的使用场景。在不断加入数据时，我们可以持续维护堆内的元素，从而实现 最大的𝑘个元素的动态更新。

发表于 更新于 分类于 ，
本文字数： 1.4k 阅读时长 ≈ 5 分钟

书接上回，接着研究一下AVL树。

AVL树

在二叉搜索树中，我们可以知道，在多次的插入和删除之后，二叉树的左右可能会失去平衡，从而导致退化成链表，在这样的情况下我们的算法的效率会从O(logn)退化到O(n)：

image.png
image.png

但是我们接下来将要提到的AVL树，将解决这些问题

AVL树的常见术语

AVL树本质是二叉搜索树和二叉平衡树的结合，所以同时满足这两种树的性质：

  1. 节点高度

“节点高度”是指从该节点到它的最远叶节点的距离，即所经过的“边”的数量。这里我们让叶子节点的高度为0，把空节点的高度设置为-1。我们将根据这些性质来编写我们的数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct TreeNode{
    int val{};
    int height = 0;
    TreeNode* left{};
    TreeNode* right{};
    TreeNode() = default;
    explicit TreeNode(int x): val(x) {} 
};

// 获取高度
int height(TreeNode* node){
    return node == nullptr ? -1 : node->height;
}

// 更新节点高度
void updateHeight(TreeNode* node){
    // 当前节点的高度 = 最高子树高度 + 1
    node->height = max(height(node->left),height(node->right)) + 1;
}
  1. 节点的平衡因子

节点的平衡因子定义为节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为0。对于AVL树，我们要求树中任意节点的平衡因子-1<=f<=1，否则这个树就进入了失衡状态。我们可以写出以下函数：

1
2
3
int balance(TreeNode* node){
    return node == nullptr ? 0 : height(node->left) - height(node->right);
}

AVL树的旋转

AVL树的精髓就在于旋转操作，当我们的树中存在失衡节点时，我们可以通过“旋转”操作，在不影响中序遍历序列的前提下，使失衡的节点重新回到平衡的状态。

我们将|平衡因子| > 1的节点称为失衡节点，根据不同的失衡情况，我们有四种旋转操作：

右旋

image.png

结合这张图来看，从底至顶看，二叉树中首个失衡节点是“节点3”。我们关注以该失衡 节点为根节点的子树，将该节点记为 node ，其左子节点记为 child ，执行“右旋”操作。完成右旋后，子树 恢复平衡，并且仍然保持二叉搜索树的性质。

但是对于，当节点child有右节点（记作grand_child）的情况下，我们需在右旋中添加一步：将grand_child设置为node的左子节点。

image.png

我们可以通过修改节点指针的方法来实现：

1
2
3
4
5
6
7
8
9
10
11
TreeNode* rightRotate(TreeNode* node){
    TreeNode* child = node->left;
    TreeNode* grandChild = child->right;
    child->right = node;
    // 当grandChild为null时无影响
    node->left = grandChild;
    updateHeight(child);
    updateHeight(node);
    // 右旋后child作为左子树的根节点
    return child;
}

左旋

左旋作为右旋的镜像版本，对应右节点失衡的情况，同样是下面的两种情况：

image.png
image.png

我们可以写出：

1
2
3
4
5
6
7
8
9
TreeNode* leftRotate(TreeNode* node){
    TreeNode* child = node->right;
    TreeNode* grandChild = child->left;
    child->left = node;
    node->right = grandChild;
    updateHeight(child);
    updateHeight(node);
    return child;
}

先左旋后右旋

对于下面这种情况，我们需要先对child进行左旋，再对node进行右旋：

image.png

先右旋后左旋

这种情况依旧是上一种情况的镜像对称情况：

image.png

旋转的选择

讲完了四种旋转的操作，现在我们需要分析，在什么情况下需要对我们的树进行哪些操作了，这里的话我推荐看一个视频：平衡二叉树(AVL树)_哔哩哔哩_bilibili

我们的步骤总结如下：

  • 先检查失衡节点的子节点child的平衡因子，大于0则需要进行右旋操作，小于0则需要进行左旋操作。
  • 然后检查失衡节点node的平衡因子，大于1则需要进行右旋操作，小于1则需要左旋操作。
  • 最后比较对子节点chlid和失衡节点node的需要进行的操作，如果相同则合并，不同则先操作子节点后操作失衡节点。

我们也可以用一张表来进行这个判断：

image.png

现在我们可以写出AVL树的平衡函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
TreeNode* rotate(TreeNode* node){
    int _balanceFactor = balance(node);
    TreeNode* child = node->left;
    if(_balanceFactor > 1){
        // 右旋
        if(balance(child)<-1)
            // 先左旋
            child = leftRotate(child);
        return rightRotate(node);
    }else if(_balanceFactor < -1){
        // 左旋
        if(balance(child)>1)
            // 先右旋
            child = rightRotate(child);
        return leftRotate(node);
    }else{
        // 平衡
        return node;
    }
}

AVL树的常用操作

  1. 插入节点

AVL树的节点插入操作和二叉搜索树一样，只不过在AVL树插入节点之后，从这个节点到根节点的路径上可能会出现一系列的失衡节点。所以我们需要从这个节点开始，自底向上的执行平衡操作，知道所有的失衡节点都恢复平衡。我们的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode* _insert(TreeNode* node, int num){
    if(node==nullptr)
        return new TreeNode(num);
    if(num < node->val)
        node->left = _insert(node->left,num);
    else if(num > node->val)
        node->right = _insert(node->right,num);
    else 
        return node;
    
    updateHeight(node);
    return rotate(node);
}
  1. 删除操作

删除也是差不多，需要在删除的基础之上，从底部到顶部进行平衡操作，确保所有的失衡点都恢复平衡：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
TreeNode* _remove(TreeNode* node, int num){
    if(node==nullptr)
        return nullptr;
    if(num < node->val)
        node->left = _remove(node->left,num);
    else if(num > node->val)
        node->right =_remove(node->right,num);
    else{
        if(node->left==nullptr||node->right==nullptr){
            TreeNode* child = node->left==nullptr ? node->right : node->left;
            delete node;
            return child;
        }else{
            TreeNode* tmp = node->right;
            while(tmp->left !=nullptr)
                tmp = tmp->left;
            int val = tmp->val;
            node->right = _remove(node->right,tmp->val);
            node->val = val;
        }
    }
    updateHeight(node);
    return rotate(node);
}
  1. 查找操作

和二叉搜索树一样，没有变化