基础排序&编译原理&python实战

前言 🔗

随着.net学习进入了瓶颈，想操作一下python进行炼丹或爬虫相关的内容

恰巧，身边有一位能力极强的大佬，在其带领下粗略的学习到了一些从未学习过的知识

大佬原话：既然搞python要学习语法只要把几个排序算法写完就应该能理解

排序算法 🔗

冒泡排序 🔗

 1from random import shuffle
 2from timeit import timeit
 3def bubble_sort(arr):
 4    n = len(arr)
 5    for i in range(n - 1):
 6        for j in range(n - 1 - i):
 7            if arr[j] > arr[j + 1]:
 8                """
 9                temp = arr[j]
10                arr[j] = arr[j + 1]
11                arr[j + 1] = temp
12                """
13                # 交换数据，这里可以py的交换而不用类似.net那样需要个temp
14                arr[j], arr[j + 1] = arr[j + 1], arr[j]
15n = 1000
16a = [*range(n)]
17shuffle(a)
18t = timeit("bubble_sort(a)", globals=globals(), number=1)
19print(t)

时间复杂度 🔗

如果n改成10000，时间应该是差不多*100倍

现在差不多50毫秒改了后差不多5000毫秒，5秒左右

拿冒泡做例子举例 有n个数我们要挑出最大那个需要进行n-1次比较，对吧

要把这n个数进行完全排列就需要

第一轮循环，把n个数进行n-1次比较，找出最大数

第二轮循环，第一轮已经找出1个数了，对剩下n-1个数则需要进行n-2次比较，找出最大数

第三轮循环，第一、二轮已经找出2个数了，对剩下n-2个数则需要进行n-3次比较，找出最大数 依次类推

最后一轮，因为每轮循环都会排除掉一个最大数，目前只剩下最后两个数字，进行1次比较，整个列表排序完毕。

总共需要进行多少次比较就是把上面每轮的比较加起来，一共是

(n-1) + (n-2) + … + 1

其实也就是公差为1的自然数列求和

得

(n-1+1)(n-1)/2变形得到n(n-1)/2= (n^2-n)/2

如果当n取一个肥肠大的数的时候

相比起n的平方来n会显得非常微小，微小到足以忽略

比如n取10000的话，n就只有n^2的万分之一大小了，取10万更是只有十万分之一。

所以我们可以把n^2-n直接看成是n^2

这就是冒泡排序的复杂度估计

代入我们上面的例子

n一开始取1000，后面取了10000

比较两者

1000^2 (1000*10)^2

所以扩大的部分就是10^2=100倍

最终我们可以把冒泡的时间复杂度写成 O(n^2)，也叫做平方复杂度，数据扩大a倍的话小号时间就会扩大a^2倍，名字就是这么来的

选择排序 🔗

每轮循环开始，我们假定列表的第一个元素就是最小的，把这个元素的下标记录到变量比如说min_，然后从第二个元素开始和这个元素进行比较，如果小于，则把min_换成第二个元素的下标，不小于的话就不去动min_，然后扫第三个元素就这样进行下去，直到扫完整个列表，min_里保存的就是最小的那个元素的下标，然后把列表第一个元素和 min_ 位置的元素进行交换，这样列表的最前端就是最小的数，这个就是完整的一轮。

时间复杂度上看似和冒泡排序一样，但实际上会节约时间。原因可以这样想，虽然比较次数相同但是交换次数会很少很多，冒泡是不停的往后交换元素，选择排序是只在比较条件成立的情况下才会更新min_下标，并且在扫描完列表后，才进行一次交换

1def selection_sort(a):
2    for i in range(1, len(a)):
3        min_ = i - 1
4        for j in range(i, len(a)):
5            if a[j] < a[min_]:
6                min_ = j
7        a[min_], a[i - 1] = a[i - 1], a[min_]

插入排序 🔗

你往一个已经排序好了的列表尾部追加了一个元素，应该如何进行排序呢。

把列表想象成一个骨牌队列，首先，添加的元素和最后一个元素进行比较，如果添加的元素小于最后的元素，就让最后的元素往后靠一位。然后，再和倒数第二个元素比较，仍然小于的话就让倒数第二个元素也往后靠一位，重复这个过程，直到遇到不满足小于情况的，就把新加的元素插入进去。

因为这个列表已经是排序好了的，所以前面的元素也不用比较了，这种方法就是插入排序

我们假定列表的第一个元素已经是排序好了的列表，第二个元素是新加的，按照上面的方法，就得到了一个长度为2的顺序列表，再把第3个元素看成新加的元素，往这个排序好的列表里插入，得到了一个长度3的顺序列表

再把第4个元素往这个长度3的顺序列表里插入，最终得到长度4的顺序列表

1def insertion_sort(a):
2    for i in range(1, len(a)):
3        j = i
4        k = a[i]
5        while (j := j - 1) >= 0 and a[j] > k:
6            a[j + 1] = a[j]
7        a[j + 1] = k

快速排序 🔗

快排也是用到了和归并的类似思路，能理解归并快排问题就不大。

它的主要是思路是这样的。

从列表中选取一个元素作为分割用的【轴】

从头开始扫描列表的元素 将小于【轴】的元素交换到列表左侧 将大于等于【轴】的元素交换到列表右侧

扫描结束后，列表被分成【前半】和【后半】两个部分 【前半】里都是小于【轴】的元素 【后半】里都是大于等于【轴】的元素

这时候有个问题，就是【前半】和【后半】的组内仍然是乱序的

比如说以5为轴，进行交换后列表可能长这样

[2, 1, 5, 9, 7]

列表的前半 2, 1 是无序的 列表的后半 5, 9, 7 也是无序的

所以需要对列表的前半和后半递归调用上面的过程，直到分组长度为1，那么就说明排序完成了

 1def quick_sort(a):
 2    def quick_sort(a, start, end):
 3        if start < end:
 4            k = partition(a, start, end)
 5            quick_sort(a, start, k - 1)
 6            quick_sort(a, k, end)
 7
 8    def partition(a, start, end):
 9        pivot = a[start] # 选择最左侧的元素作为轴
10        i = start
11        j = end
12        while i <= j:
13            while i <= end and a[i] < pivot:  # 从左开始扫描小于轴的元素
14                i += 1
15            while j >= start and a[j] >= pivot: # 从右开始扫描大于等于轴的元素
16                j -= 1
17            if i > j:  # 如果下标发生交错，则认为已经扫描完毕
18                break
19            a[i], a[j] = a[j], a[i] # 没扫描完的情况下我们需要交换元素，确保小于轴的元素最终都会位于大于等于轴的元素的左侧
20            i += 1
21            j -= 1
22        if i == start:  # 防止轴为最小元素时不进行分割的情况
23            i += 1
24        return i

归并排序 🔗

 1def merge_sort(a):
 2    if (len_ := len(a)) > 1:
 3        half = len_ // 2
 4        a1 = a[:half]
 5        a2 = a[half:]
 6        merge_sort(a1)
 7        merge_sort(a2)
 8        merge(a, a1, a2)
 9
10
11def merge(a, a1, a2):
12    i = j = 0
13    for k in range(len(a)):
14        if i >= len(a1) or (j < len(a2) and a2[j] <= a1[i]):
15            a[k] = a2[j]
16            j += 1
17        else:
18            a[k] = a1[i]
19            i += 1

归并排序你应该感觉出来了，数组不断分裂，长度不停地在除2，必然复杂度和 log2(n) 有关

它的复杂度是 n log2(n)，所以哪怕数据扩大10倍，耗时放大也只是1x倍多一点点（乘对数）

你可以看看用归并排序10万个元素和百万个元素

编译原理 🔗

计算机の相关知识 🔗

按理说内存的写入也是占用极低的

内存操作比起CPU来说慢太多了。

CPU主频是G，也就是10^9这个数量级，一次访存操作要花费几十到上百个时钟周期，其计算算类指令只要个位数个指令周期

同样架构的一个6G主频的CPU比起一个3G主频的CPU能把排序时间缩短一半吗？答案是并不能，原因就在memory IO瓶颈,你运算可以加快一倍，访存可由不得你，被内存卡死了

再快比起CPU都不值一提 CPU的时钟频率是G，也就是10的9次方，用你熟悉的文字描述就是十亿起，3G就30亿 3G主频意味着CPU内部的时钟每秒会跳30亿次，每一次跳动我们称为一个时钟周期 衡量一个指令的执行速度可以看它会在几次跳动内完成（即在多少时间周期内完成

CPU与GPU的比较

CPU可以进行复杂的执行流程控制，分支预测，跳转，投机执行，乱序执行等等

GPU没这个能力，GPU处理的是高度对齐的数据，所以它可以通过大面积晶体管换来不断提高的执行速度，因为它只要算就行了，也就是说两个字——傻快。

CPU则要处理各种复杂的执行逻辑，接触各种各样的数据，在CPU的晶体管面积中，用于控制的比单纯用于计算的还要快

CPU的工作方式就是一个大学生做高数。 GPU的工作方式十万个小学生做四则运算。

终究，它们是为了面向不同的任务设计的

cpu这种东西的时钟周期，是不是在不同架构上的表现是不一样的，例如精简arm会比x86_64快？

时钟周期就是时钟周期，这东西只是用来说明客观上一秒有多少次，换啥平台都一样。

只是不同平台架构不一样，实现一个相同功能的指令的方式也不一样，因而需要花费的时钟周期也不一样

耗电不耗电看晶体管密度，指令集架构。哪怕你主频10g火力全开执行的全是nop指令也很省电

具体还得看电路设计工作方式，这些就扯远了和主频无关,哪怕它跳无穷多次你呆在原地啥都不干照样节能

CPU缓存是不是只记录内存地址

不是，是记录内存里的内容，只有这样才能加速。利用程序的【时间局部性】和【空间局部性】两个基本属性。

【时间局部性】（temporal locality）是指如果你访问了变量x，那么很可能接下来马上又会再次访问x，对应的情况就是：从变量x取出值，进行一定计算，把结果写入x，或者再几步后再次访问x。 这些连续的访问同一个值在时间分布上是很靠近的，反映出了一种紧凑型。

【空间局部性】（spatial locality）就更典型了，你访问了元素a[i]，接下来马上可能就会访问a[i+1]或者a[i+n]，也就是说你访问了一个元素后，相邻的元素也有很大几率会被访问到，对于结构体和其他数据结构也是一样的。这反映出了空间上的紧凑性。

如果把程序整体的执行时间划分成若干个小段，你会惊奇地发现在每个小段时间内，程序的访存行为基本上都复合以上两个属性，这就是为什么缓存明明这么小却能非常有效的原因，主要还是因为你程序本质上在一小段时间内就访问那么一丁丁数据，哪怕对于整体上要处理很大数据的程序来说也一样，在一小段时间可能就是在访问相对集中的那么一小部分数据

Python的一些奇技淫巧 🔗

1.用ctypes结构体读二进制文件

 1from ctypes import Structure, sizeof
 2from ctypes.wintypes import DWORD, LONG, WORD
 3from sys import argv
 4
 5
 6class BITMAPFILEHEADER(Structure):
 7    _pack_ = 1
 8    _fields_ = [
 9        ("bfType", WORD),
10        ("bfSize", DWORD),
11        ("bfReserved1", WORD),
12        ("bfReserved2", WORD),
13        ("bfOffBits", DWORD),
14    ]
15
16
17class BITMAPINFOHEADER(Structure):
18    _pack_ = 1
19    _fields_ = [
20        ("biSize", DWORD),
21        ("biWidth", LONG),
22        ("biHeight", LONG),
23        ("biPlanes", WORD),
24        ("biBitCount", WORD),
25        ("biCompression", DWORD),
26        ("biSizeImage", DWORD),
27        ("biXPelsPerMeter", LONG),
28        ("biYPelsPerMeter", LONG),
29        ("biClrUsed", DWORD),
30        ("biClrImportant", DWORD),
31    ]
32
33
34if __name__ == "__main__":
35    with open(argv[1], "rb") as f:
36        bmp_file_hdr = BITMAPFILEHEADER()
37        dib_hdr = BITMAPINFOHEADER()
38
39        f.readinto(bmp_file_hdr)
40        if bmp_file_hdr.bfType.to_bytes(2, "little") != b"BM":
41            raise TypeError
42
43        f.readinto(dib_hdr)
44        if dib_hdr.biSize != sizeof(BITMAPINFOHEADER):
45            raise NotImplementedError
46
47        print(
48            f"""
49文件信息
50------------------
51大小：{bmp_file_hdr.bfSize} 字节
52尺寸-宽：{dib_hdr.biWidth} 像素
53尺寸-高：{dib_hdr.biHeight} 像素
54颜色深度：{dib_hdr.biBitCount} 比特
55            """
56        )
57        input("...")

bmp文件的格式是一个 bmp文件头跟一个dib信息头，后面是数据,你只要定义这两个头然后把文件数据读进去就可以

2.python与C#互操

pythonnet

python的模块有两类，一个是纯py写的，另一个是c写的pyd（也不一定要是c写的，提供c abi接口的动态库都行）

编译原理（初级） 🔗

编译器是不管符号解析的（就是把函数名替换成具体的内存地址）

一个项目几十文件编译成几十个模块，先后都被没办法保证啊，你怎么能确保你调用的那个模块，已经先全都编译好了，如果强行解析引用，可能还会搞出菱形引用之类的问题

所以编译器是不会管符号解析的，它只管把源码编译成汇编而已。

碰到函数调用就编译成call 0x00000000，然后往重定位表里加一条表示这里有个地址要进行替换，这就完了，编译器要做的就这么多，符号解析什么的是链接器来做的

汇编器编译出来的都是.o文件啊，包含了一些信息（重定位表啊）和机器指令的二进制，但这些文件离可被系统加载执行还很远，起码你得把他搞成系统可以加载的exe格式（PE格式），还有一堆工作要做呢，根据信息来生成PE头啊，设置各种信息啊，按照可以被系统加载器识别的规则，一个个设置好。

一个exe文件是由若干个.o文件拼接出来的，因为你不可能吧所有代码都写在一个.c文件里，而是根据功能分成不同的文件，编译完会生成多个.o

对于静态链接来说，因为所有需要的.o文件和静态库都会被编译进最终的产成品二进制文件中，所以在结合的过程中链接器就能算出地址进行替换，最后生成的.exe里已经把call 0x00000000替换成call 0xXXXXXXXX 实际地址了，动态链接就不行了，动态库为了防止冲突啊什么的，不可能加载到一个固定的位置，实际加载到什么位置都是执行加载exe时，把dll也都加载进来，然后按需看情况，看看内存哪里哪里空着没被占用，就加载到那里（其实是有一套很细致的规则，比如会有最低地址的规定，不过这些你目前听不懂），那你程序里对动态库的调用，显然也不可能写死啊，生成的exe文件里，还是保留着 call 0x00000000，同时，exe头部会有个符号重定位表，记载了这些call 0x00000000的位置，以及要把这些call置换成哪些相应符号。对于动态链接库就是在exe运行加载的时候，由动态链接器对进行符号重定位，大致就是根据exe里的重定位表，在dll里的导出表里找到符号，并找到符号的地址（其实就是函数首指令的地址），把符号地址写到exe的对应的call 0x00000000里，这就是符号解析和重定位的基本原理，当然为了让你能听懂，我简化了太多步骤了，比如Linux下的ld.so是lazy loading的，只有函数调用实际发生的时候（第一次调用），才会查表并替换，这需要好几张表一起协同工作，.plt、.plt.got、.got .reloc 等等好几个section的信息都要用到，在程序加载时就一次性替换的话可能性能开销会比较大才采用了这种策略

当运行到这条call 0x00000000 时，才会进行符号解析和替换，当然地址其实不是0x00000000，也不是符号的地址，而是指向某.plt的chunk的地址,跳到这chunk后，会有一些挺trick的操作，最终这条call的地址会被改成实际的符号地址

你给库打个patch，等于对所有使用该库的程序都打了patch。

dll的.text section可以被加载到EXE&RO的内存页，映射到不同进程的内存空间，而不用每个程序都自己加载一份dll，实现了内存节约。

以及，一些对象是不能跨越dll boundary的，要用静态链接就只能全静态链接了，对于那些依赖引用链条非常长的程序很不方便，他们的所有依赖，依赖的依赖，都要静态编译进去,很多情况是不现实的