“Dev can be one of the ways to create everything for you, which will come with a great sense of achievement.”
🥳MAN！ 作为一名Dev手，学会查找并浏览官方文档 是非常重要的能力。本题要求你初步学会使用linux系统自带的一个功能强大的文档：man 。(实际上是manual 的英文缩写）
CH1 首先，你要在电脑上配置一个虚拟环境，这里列出几个方案:
在windows环境下可以使用wsl（比较推荐）
或者可以配置虚拟机
或者有条件可以找一台云服务器或者买另一台实体机。
双系统（步骤比较复杂）
当我们有了linux环境后，不妨在linux环境下使用gcc编译一个自己写的”Hello World!”并运行！
CH2 linux有一个很有意思的指令：strace。同时，linux中的指令(command)， 系统调用(system call)和库函数(library function) 基本都可以用man 1 [name], man 2 [name] man 3 [name]来了解他们的用法。
假设你在CH1中的程序名为hello。在同目录下运行strace ./hello。结合你看到的man上对strace的阐述，简单解释下运行结果。
In the simplest case strace runs the specified command until it exits. It intercepts and records the system calls which are called by a process and the signals which are received by a process. The name of each system call, its arguments and its return value are printed on standard error or to the file specified with the -o option.
输出展示了程序的执行过程。
execve调用hello_world，传递了PATH、参数和42个环境变量；返回0，成功执行。brk查询程序数据段末尾位置，返回值是当前内存分配位置，用于管理内存。mmap为程序分配一块内存，返回分配的内存地址，用于读写操作。access在检查是否存在ld.so.preload文件，返回错误，没有找到。openat打开共享库缓存文件，查找程序依赖的共享库；当前程序依赖的libc库被打开，程序返回3。read、mmap和close表示从库中读取需要的数据。arch_prctl设置线程本地存储，为多线程环境提供支持。（不懂）set_tid_address和set_robust_list用于线程的初始化、设置线程的标识地址，防止线程被意外中断。（也不懂）mprotect保护内存页面的权限，设置某些内存区域为只读。（大的要来了）write(1, "hello_world\n", 12) = 12，通过write系统调用向文件描述符1即标准输出写入12个字节的字符串。
exit_group顾名思义，结束并正常退出。+++ exited with 0 +++
CH3 运行 man 3 exec。你能写一个运用到了库函数exec的C程序吗？
The exec() family of functions replaces the current process image with a new process image.
写程序调用execve来替换当前的进程。CH2的第一个调用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <stdio.h> #include <stdlib.h> #include <unistd.h> extern char **environ; int main () { char *program = "/bin/ls" ; char *args[] = {"ls" , NULL }; if (execve(program, args, environ) == -1 ) { perror("execve met problems." ); exit (EXIT_FAILURE); } return 0 ; }
编译和运行这个程序。
1 2 3 4 5 $ gcc -o execve_exp execve_exp.c $ ./execve_exp execve_exp execve_exp.c hello_world test.c $ ls execve_exp execve_exp.c hello_world test.c
😶🌫️Oop Loop 学习c语言的数组部分时，想出了三种遍历二维数组的方法，并想办法测量了这三种方法所使用的时间。”这三种方法都访问了同样数量 的数组元素，因此他们所耗费的时间一定是差不多的。“但事情远没有这么简单：
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 #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/time.h> #include <fcntl.h> #define UNIT_GAP 1000000.0 void M_gettimeofday (struct timeval *tv) { int result = gettimeofday(tv, NULL ); if (result != 0 ) { perror("gettimeofday st\n" ); exit (1 ); } return ; } #define ArrSize 15000 int arr1[ArrSize][ArrSize];int arr2[ArrSize][ArrSize];int arr3[ArrSize][ArrSize];int main () { struct timeval tv_st ; M_gettimeofday(&tv_st); for (int i = 0 ; i < ArrSize; i++) { for (int j = 0 ; j < ArrSize; j++) { arr1[i][j] += 1 ; } } struct timeval tv_ed ; M_gettimeofday(&tv_ed); double time_gap1 = (double ) (tv_ed.tv_sec - tv_st.tv_sec) + ((double ) (tv_ed.tv_usec - tv_st.tv_usec) / UNIT_GAP); M_gettimeofday(&tv_st); for (int i = 0 ; i < ArrSize; i++) { for (int j = 0 ; j < ArrSize; j++) { arr2[j][i] += 1 ; } } M_gettimeofday(&tv_ed); double time_gap2 = (double ) (tv_ed.tv_sec - tv_st.tv_sec) + ((double ) (tv_ed.tv_usec - tv_st.tv_usec) / UNIT_GAP); M_gettimeofday(&tv_st); for (int i = 0 ; i < ArrSize; i++) { int cap = (ArrSize / 3 ) * 3 ; for (int j = 0 ; j < cap; j+=3 ) { arr3[i][j] += 1 ; arr3[i][j + 1 ] += 1 ; arr3[i][j + 2 ] += 1 ; } for (int j = cap; j < ArrSize; j++) { arr3[i][j] += 1 ; } } M_gettimeofday(&tv_ed); double time_gap3 = (double ) (tv_ed.tv_sec - tv_st.tv_sec) + ((double ) (tv_ed.tv_usec - tv_st.tv_usec) / UNIT_GAP); printf ("time spent for time_gap1: %lf seconds\n" , time_gap1); printf ("time spent for time_gap2: %lf seconds\n" , time_gap2); printf ("time spent for time_gap3: %lf seconds\n" , time_gap3); }
事实上，这三种遍历方式使用的时间有明显的差别。
CH1 发现每次程序的运行结果差别都很大，因此需要反复运行程序很多次才能找出不同遍历模式下的时间规律。请你帮他修改程序，让程序的运行结果随机性更小，这样就能找出更加可信的结论了！
实践出真知，跑一下看看。Oops，感觉1和3的随机性很强，2几乎是最慢的，不过也有少数例外。为了减少随机性，我们可以多次跑代码取平均值。
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 #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/time.h> #include <fcntl.h> #define UNIT_GAP 1000000.0 #define ArrSize 15000 #define NUM_RUNS 5 void M_gettimeofday (struct timeval *tv) { int result = gettimeofday(tv, NULL ); if (result != 0 ) { perror("gettimeofday failed\n" ); exit (1 ); } } int arr1[ArrSize][ArrSize];int arr2[ArrSize][ArrSize];int arr3[ArrSize][ArrSize];int main () { double total_time1 = 0.0 , total_time2 = 0.0 , total_time3 = 0.0 ; for (int run = 0 ; run < NUM_RUNS; run++) { struct timeval tv_st , tv_ed ; M_gettimeofday(&tv_st); for (int i = 0 ; i < ArrSize; i++) { for (int j = 0 ; j < ArrSize; j++) { arr1[i][j] += 1 ; } } M_gettimeofday(&tv_ed); double time_gap1 = (double ) (tv_ed.tv_sec - tv_st.tv_sec) + ((double ) (tv_ed.tv_usec - tv_st.tv_usec) / UNIT_GAP); total_time1 += time_gap1; M_gettimeofday(&tv_st); for (int i = 0 ; i < ArrSize; i++) { for (int j = 0 ; j < ArrSize; j++) { arr2[j][i] += 1 ; } } M_gettimeofday(&tv_ed); double time_gap2 = (double ) (tv_ed.tv_sec - tv_st.tv_sec) + ((double ) (tv_ed.tv_usec - tv_st.tv_usec) / UNIT_GAP); total_time2 += time_gap2; M_gettimeofday(&tv_st); for (int i = 0 ; i < ArrSize; i++) { int cap = (ArrSize / 3 ) * 3 ; for (int j = 0 ; j < cap; j += 3 ) { arr3[i][j] += 1 ; arr3[i][j + 1 ] += 1 ; arr3[i][j + 2 ] += 1 ; } for (int j = cap; j < ArrSize; j++) { arr3[i][j] += 1 ; } } M_gettimeofday(&tv_ed); double time_gap3 = (double ) (tv_ed.tv_sec - tv_st.tv_sec) + ((double ) (tv_ed.tv_usec - tv_st.tv_usec) / UNIT_GAP); total_time3 += time_gap3; } printf ("Average time spent for time_gap1: %lf seconds\n" , total_time1 / NUM_RUNS); printf ("Average time spent for time_gap2: %lf seconds\n" , total_time2 / NUM_RUNS); printf ("Average time spent for time_gap3: %lf seconds\n" , total_time3 / NUM_RUNS); return 0 ; }
嗯，看起来有规律多了：$2>>1>3$。
CH2 试回答不同遍历模式下运行时间的差别，并解释为什么会产生这些差别。
1是行优先遍历，这与C中行主序 存储数组的方式一致。根据局部性，CPU可以有效地读取连续的内存块，减少缓存未命中次数，提高访问速度。
而2是列优先遍历，与1相反，这种访问模式导致大量缓存未命中、效率低。
关于原理解释那一部分，只靠cpu缓存其实不太能解释 第三个pattern 耗时比第一个pattern小的问题qwq——Shiver
3则使用了循环展开 优化。每次处理三个元素，减少了每次更新迭代的控制开销，在大规模进行数组遍历时，会累积成明显的性能提升。
另外由于数组元素是每三个访问的，更容易预取更多数据到缓存 中，进一步减少了缓存未命中的损失。
流水线 优化：现代处理器使用流水线技术来提高指令执行的效率。3通过减少循环次数和增加每次循环内处理的数据量，减少了其它分支指令，使处理器流水线更顺畅。这可以减少流水线停顿，从而提高整体执行速度。
分支预测 ：循环的检查条件变少了，分支预测错误的概率也降低了。
可能存在的向量化 优化？编译器可以自动将这种每次操作多个相邻元素转换为SIMD指令。这意味着处理器可以在一个指令周期内对多个数据进行相同的操作，提升运算速度。
连续访问多个元素更有可能保持内存对齐，从而减少额外的内存操作开销。
由于循环体内操作相互独立，处理器可以并行处理多个操作，进一步提升速度。
♿造轮子
Git 是一个分布式版本控制系统，用于跟踪代码或文件的更改，并支持多人协作开发。
你可以在这里看到git的源代码: https://github.com/git/git
Shiver想要在自己的电脑上安装git。
以前，他是通过系统的软件包管理器来安装git的。例如，在ubuntu系统中就可以使用这两行命令来安装git：
1 2 $ sudo apt update $ sudo apt install git
但今天，它想换点新花样。他想要通过源代码来编译git！
git的源代码很多地方都有，这里比较推荐使用github上的代码仓库，并通过git clone下载。（不要吐槽为什么电脑上已经有git了为为什么还要下载git源码）
同时，Shiver还通过修改源代码实现了修改git调用版本信息后的输出。
总的来说，Shiver想要你实现如下的操作：
在自己的电脑上编译 git 程序，并在提交文档中简单阐述自己在编译过程中遇到的问题与自己是怎么解决这些问题的。
修改 git 的源代码，使其在输出版本信息时会有额外的 <-- CNSS --> 提示（你也可以添加自己喜欢的信息）并截图提交。（这可能需要你具有一定的代码阅读能力）
Hints：
怎么编译？要不先从文档开始，比如源代码中的README.md，INSTALL文件？
什么是cmake？
A）编译需要依赖，在GPT的帮助下怒装依赖项。
1 sudo apt install -y make libssl-dev libcurl4-gnutls-dev libexpat1-dev gettext
B）获取Git的源码并编译Git程序：
1 2 3 4 git clone git@github.com:git/git.git make configure ./configure --prefix=/usr/local make
C）遇到报错信息：
1 2 3 4 5 6 7 8 9 10 /usr/bin/ld: libgit.a(utf8.o): in function `reencode_string_iconv': /home/aununo/CNSS/git/utf8.c:498:(.text+0x10dd): undefined reference to `libiconv' /usr/bin/ld: libgit.a(utf8.o): in function `reencode_string_len': /home/aununo/CNSS/git/utf8.c:593:(.text+0x121d): undefined reference to `libiconv_open' /usr/bin/ld: /home/aununo/CNSS/git/utf8.c:603:(.text+0x1252): undefined reference to `libiconv_close' /usr/bin/ld: /home/aununo/CNSS/git/utf8.c:593:(.text+0x129e): undefined reference to `libiconv_open' /usr/bin/ld: /home/aununo/CNSS/git/utf8.c:603:(.text+0x12c9): undefined reference to `libiconv_close' /usr/bin/ld: /home/aununo/CNSS/git/utf8.c:598:(.text+0x136b): undefined reference to `libiconv_open' collect2: error: ld returned 1 exit status make: *** [Makefile:2842: git-daemon] Error 1
大概是说缺少 libiconv 库的引用。libiconv 是一个用于字符编码转换的库，而 Git 在处理字符集转换时依赖于它。我们使用命令
1 2 3 $ ldconfig -p | grep libiconv libiconv_hook.so.1 (libc6,x86-64) => /lib/x86_64-linux-gnu/libiconv_hook.so.1 libiconv_hook.so (libc6,x86-64) => /lib/x86_64-linux-gnu/libiconv_hook.so
系统上有 libiconv_hook.so，而不是标准的 libiconv.so。由于 libiconv_hook 并没有提供 libiconv.so 的标准接口，导致了编译和测试时出现错误。创建符号链接：
1 sudo ln -s /lib/x86_64-linux-gnu/libiconv_hook.so.1 /lib/x86_64-linux-gnu/libiconv.so.2
让系统中的 libiconv_hook.so 模拟 libiconv.so.2，验证一下：
1 2 3 4 5 $ ldconfig -p | grep libiconv libiconv_hook.so.1 (libc6,x86-64) => /lib/x86_64-linux-gnu/libiconv_hook.so.1 libiconv_hook.so (libc6,x86-64) => /lib/x86_64-linux-gnu/libiconv_hook.so libiconv.so.2 (libc6,x86-64) => /usr/local/lib/libiconv.so.2 libiconv.so (libc6,x86-64) => /usr/local/lib/libiconv.so
然后进行make编译成功！再复现一遍。
Git 的版本信息由 git --version 命令生成，输出git version，下面我们进行查找：
把大量输出喂给GPT发现：
1 2 3 ./help.c: * with external projects that rely on the output of "git version" . ./help.c: strbuf_addf(buf, "git version %s\n" , git_version_string); ./help.c: N_("git version [--build-options]" ),
Here it is! 在vscode中查找并编辑help.c文件，修改输出即可。
1 2 strbuf_addf(buf, "git version %s\n" , git_version_string); => strbuf_addf(buf, "<-- CNSS --> git version %s I l0v3 Sh1v3r~\n" , git_version_string);
重新make一下，输出时发现后面多了一个dirty。是修改了help.c却没提交更改的缘故。
可以看到输出<-- CNSS --> git version 2.46.2.628.g6258f68c3c.dirty I l0v3 Sh1v3r~
⚒️Dig and Dig
ssg是一名资深的Minecraft玩家，平时最喜欢的就是在MC的辽阔土地上寻找珍贵的矿石。
CH1 从原版到整合包，从我的世界到泰拉瑞亚，ssg挖矿的足迹分布在各个领域。
有一天，他突然好奇想挖挖看 C语言程序，于是他写下了这段代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <stdio.h> #include <stdlib.h> int depth;void Dig (int digging) { if (digging < 0 ) { return ; } int where_are_we; printf ("In depth %d, we are at %p \n" , (depth - digging), (void *) &where_are_we); Dig(digging - 1 ); } int main () { printf ("Today we will dig: " ); scanf ("%d" , &depth); printf ("Let begin!\n" ); Dig(depth); }
他决定先向下面挖掘 10 个函数的深度，于是他将depth 变量设置为了 10 并得到了这样的结果：
Today we will dig: 10
看起来不错，于是他决定继续向下挖，但不知道为什么，当 depth 足够大时，程序就终止运作了！
因此 ssg 找到你，想请你帮他解决这些问题：
尝试修改程序，使ssg的这个程序能统计他 总共 能够向下挖掘多少个 Byte。多次运行这个程序，每次能向下挖的Byte是固定的吗？
运行初始程序看看depth的最大值，发现每次运行得到的最大深度相近但不同。比如：
1 2 3 4 5 6 7 8 9 10 11 12 $ ./dig Today we will dig: 1000000 Let begin! ... In depth 174513, we are at 0x7ffcccda07a4 [1] 2146 segmentation fault ./dig In depth 174450, we are at 0x7ffda0d677a4 [1] 2165 segmentation fault ./dig In depth 174576, we are at 0x7ffc72f5f7a4 [1] 2688 segmentation fault ./dig
第一次运行，程序在174513处崩溃，而第二次运行在174450处崩溃，操作系统为进程分配的栈空间每次可能会略有不同，因此这些深度值并不完全一致。segmentation fault的段错误发生在程序试图访问未被允许访问的内存区域时。
[1] 是Linux系统为每个后台任务分配的作业号，1表示这是当前会话的第一个后台进程。
2146和2165是进程ID，是系统为每个运行程序分配的唯一标识符。
记录一下初始地址，用where_are_we减初始地址得到所在深度：
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 #include <stdio.h> #include <stdlib.h> int depth;void *initial_address = NULL ;void Dig (int digging) { if (digging < 0 ) { return ; } int where_are_we; if (initial_address == NULL ) { initial_address = &where_are_we; } int current_depth_bytes = abs ((char *) initial_address - (char *) &where_are_we); printf ("In depth %d, we are at %p, depth in bytes: %d \n" , (depth - digging), (void *) &where_are_we, current_depth_bytes); Dig(digging - 1 ); } int main () { printf ("Today we will dig: " ); scanf ("%d" , &depth); printf ("Let begin!\n" ); Dig(depth); return 0 ; }
运行一下程序：
1 2 3 4 5 6 7 $ ./dig Today we will dig: 100 Let begin! In depth 0, we are at 0x7ffdd7afae10, depth in bytes: 0 In depth 1, we are at 0x7ffdd7afade0, depth in bytes: 48 ... In depth 100, we are at 0x7ffdd7af9b50, depth in bytes: 4800
发现每次能向下挖的字节数是固定的48字节。
尝试解释为什么depth足够大时程序会停止运行。
递归深度过深，发生了栈溢出。函数的递归调用会在栈上分配内存，而栈的大小是有限的。当递归深度超出系统分配给程序的栈内存时，程序就会发生栈溢出，从而导致程序崩溃。
尝试解释为什么每次层数的间隔都为 48Byte, 这48Byte里面都包含了些什么？
函数调用过程中的栈帧结构，说明这个函数中一个栈帧大小为48byte。包含：函数的返回地址，局部变量，函数参数等。
比如将函数内部的局部变量where_are_we类型改为long时，层数间隔会变为64byte。
CH2 ssg在挖矿的时候是左右手交替进行的，因此他想记录下自己在挖掘每一层时使用的是左手还是右手，于是他写下了这段代码：
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 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> int depth;char * WhichHand (bool hand) { return hand ? "left hand" : "right hand" ; } bool Dig1 (int digging) { if ( digging < 0 ) { return 0 ; } bool now_hand = !Dig1(digging - 1 ); printf ("In depth %d, we use %s \n" , (depth - digging), WhichHand(now_hand)); return now_hand; } bool Dig2 (int digging, bool hand) { if ( digging < 0 ) { return hand; } printf ("In depth %d, we use %s \n" , (depth - digging), WhichHand(hand)); return Dig2(digging - 1 , !hand); } int main () { printf ("Today we will dig: " ); scanf ("%d" , &depth); printf ("Let begin!\n" ); Dig1(depth); }
Dig1和Dig2是他编写的两个不同版本但是效果相似的函数，看起来运行的不错：
Today we will dig: 10
但ssg发现了一个很严重的问题，当他使用 O2 优化 (即在gcc编译时添加-O2指令)分别编译运行了两个不同版本的函数后，有一个版本的函数，无论他将深度设置为多大，都可以正常运行！
他现在想考考你:
哪个版本的函数无论设置多大的深度都可以正常运行？
dig2函数。我们来跑一下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 $ gcc -O2 -o dig1 dig1.c dig1.c: In function ‘main’: dig1.c:34:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 34 | scanf("%d" , &depth); | $ ./dig1 Today we will dig: 1000000 Let begin! [1] 1727 segmentation fault ./dig $ ./dig2 Today we will dig: 1000000 Let begin! ... In depth 999999, we use left hand In depth 1000000, we use right hand
为什么？
dig1函数仍然是使用了普通递归的方式，即使开O2优化编译，栈空间的限制依然存在。
而dig2函数使用尾递归，大多数编译器，比如这里的gcc中，开了O2尾递归可以被优化为普通循环实现，每次递归不需要额外占用栈帧，只需将函数参数改变再调用一次，就不会触发栈溢出。
谈一谈这道题对你在实际项目开发中的启发。
用递归，深度较大时，警惕栈溢出；
合理使用尾递归；
了解编译器和语言的优化能力，有助于提高程序的运行效率；
developers应当编写健壮的代码，做好代码测试，关注边界条件。
🧮Primes 香肠非常痴迷于筛法求素数表，大致原理如下
于是他先用 JavaScript 编写了下面这样的代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 function * iota (i, n ) { while (i < n) yield i++ } function * filter (g, p ) { for (x of g) { if (x % p) yield x } } g = iota (2 , 100 ) while (true ) { var {value, done} = g.next () if (done) break g = filter (g, value) console .log (value) }
程序成功打印了 100 以内的所有素数。
为了让更多人理解这段代码，他又编写了 Python 版本
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def iota (i, n ): while i < n: yield i i += 1 def filter (g, p ): for x in g: if x % p: yield x g = iota(2 , 100 ) try : while True : value = next (g) g = filter (g, value) print (value) except StopIteration: pass
程序虽然正确，但 IDE 给出了警告：用户定义的 filter 函数隐藏了 Python 内置的 filter 函数。
说来也是，为什么不直接使用更泛化的内置 filter 函数呢？于是他又把程序改成了这样。
1 2 3 4 5 6 7 8 9 10 11 12 13 def iota (i, n ): while i < n: yield i i += 1 g = iota(2 , 100 ) try : while True : value = next (g) g = filter (lambda incoming: incoming % value, g) print (value) except StopIteration: pass
很遗憾的是，程序输出的结果不再正确。到底是哪里出了问题？
在调试的过程中，香肠觉得不能光调 Python 代码，JavaScript 的也不能放过。
考虑到 Python 采用了更泛化 filter 函数，于是他把原 JavaScript 代码也改成了这样。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 function * iota (i, n ) { while (i < n) yield i++ } function * filter (g, p ) { for (x of g) { if (p (x)) yield x } } g = iota (2 , 100 ) while (true ) { var {value, done} = g.next () if (done) break g = filter (g, incoming => console .log (value) }
竟然出现了和第二份 Python 代码一样的错误输出结果。这是巧合吗？
本题筛素数的协程叫什么协程？你能简单描述一下这样筛素数的过程吗？
在JavaScript或Python中，利用惰性求值的生成器，可以逐步生成一个序列，并能在筛选过程中动态修改序列，避免占用过多计算资源。
1 2 3 4 5 6 7 g = iota (2 , 100 ) while (true ) { var {value, done} = g.next () if (done) break g = filter (g, value) console .log (value) }
核心思想是埃拉托斯特尼筛法（Sieve of Eratosthenes）。生成器iota生成一个从2到99的整数序列g，每次调用g中的值并通过生成器filter筛掉素数value的倍数，输出value，再移动到下一个数进行循环。
两者的问题不一样。
Python是和其延时绑定 的机制有关。Python在真正执行函数（如lambda）的时候才会查找变量的值，而不是在定义函数时。
1 g = filter (lambda incoming: incoming % value, g)
而在同一个作用域下，value的值始终针对同一个变量在变化，而不是每次循环都创建一个新变量。因此，所有的lambda中引用的value都会使用最新的值。
可以采用默认参数 的方法解决这个问题。
1 2 3 4 5 6 7 8 9 10 11 12 13 def iota (i, n ): while i < n: yield i i += 1 g = iota(2 , 100 ) try : while True : value = next (g) g = filter (lambda incoming, value=value: incoming % value, g) print (value) except StopIteration: pass
这样，参数只会初始化一次，而在之后的循环中保持不变。
手动即时捕获。
1 2 3 4 5 6 7 8 9 10 11 12 13 def iota (i, n ): while i < n: yield i i += 1 g = iota(2 , 100 ) try : while True : value = next (g) g = filter ((lambda value: lambda incoming: incoming % value)(value), g) print (value) except StopIteration: pass
而JavaScript是与var的作用域规则有关。var在JavaScript中的作用域是函数作用域，而不是块作用域。循环体中每次声明的value实际上会在整个函数的作用域中共享，lambda函数捕获的是对同一个变量的引用，所以value会在每次循环后更新。
可以使用 let 代替 var。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 function * iota (i, n ) { while (i < n) yield i++ } function * filter (g, p ) { for (x of g) { if (p (x)) yield x } } g = iota (2 , 100 ) while (true ) { let {value, done} = g.next () if (done) break g = filter (g, incoming => console .log (value) }
因为 let 是块作用域，在每次循环中会为 value 绑定一个新的变量，这样每个 lambda 函数都能捕获到当前循环中的 value，而不是共享的全局变量。
⭐数数
计算机往往不够聪明（或者太过聪明），以至于他只会完全按照你的指令办事，尽管有时候你自己都不知道自己的指令是什么含义
CH1 这道题目并不难，你要做的只是让计算机学会数数而已。
比如：
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 #include <pthread.h> #include <stdio.h> #include <stdlib.h> int work_load;void *worker (void *counter_ptr) { for (int i = 0 ; i < work_load; i++) { (* (int *)counter_ptr) += 1 ; } return NULL ; } int main () { printf ("give the workload per thread: " ); scanf ("%d" , &work_load); int counter; worker(&counter); worker(&counter); printf ("Totally count: %d\n" , counter); return 0 ; }
十分简单对吧？但是柳苏明却认为，让同一个 worker函数运行两遍效率太低了。为什么不雇佣两个 worker， 让他们同时工作呢？换句话说，他决定使用 多线程 ！
于是他十分好心的给了你两份代码：
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 #include <pthread.h> #include <stdio.h> #include <stdlib.h> int work_load;void *worker (void *counter_ptr) { for (int i = 0 ; i < work_load; i++) { (* (int *)counter_ptr) += 1 ; } return NULL ; } int main () { printf ("give the workload per thread: " ); scanf ("%d" , &work_load); pthread_t thread1, thread2; int counter1, counter2; pthread_create(&thread1, NULL , worker, &counter1); pthread_create(&thread2, NULL , worker, &counter2); pthread_join(thread1, NULL ); pthread_join(thread2, NULL ); printf ("Totally count: %d\n" , counter1 + counter2); return 0 ; } #include <pthread.h> #include <stdio.h> #include <stdlib.h> int work_load;void *worker (void *counter_ptr) { for (int i = 0 ; i < work_load; i++) { (* (int *)counter_ptr) += 1 ; } return NULL ; } int main () { printf ("give the workload per thread: " ); scanf ("%d" , &work_load); pthread_t thread1, thread2; int counter; pthread_create(&thread1, NULL , worker, &counter); pthread_create(&thread2, NULL , worker, &counter); pthread_join(thread1, NULL ); pthread_join(thread2, NULL ); printf ("Totally count: %d\n" , counter); return 0 ; }
但问题出现了，尽管第一份代码可以正常运行，但第二份代码在 输入值很大 时总是出现奇怪的偏差。
尝试运行测试这两段代码，回答：
为什么两份相似的代码会有不同的输出结果？
V1中每个线程独立地操作各自的counter1和counter2，互不干扰，最终把两个计数器的结果加和得到答案。
V2中通过多线程并发地对同一变量counter进行修改，这种操作存在竞争条件。意味着两个线程可能同时读写共享变量counter，导致计数不准确，尤其是在工作负荷较大的时候。
在编写多线程代码时，如何避免这种错误？
引入同步机制，使用互斥锁来保证线程的独立访问，确保在同一时刻只有一个线程可以操作变量，避免竞争条件。
尝试只修改 worker 函数来使第二份代码输出正确。
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 #include <pthread.h> #include <stdio.h> #include <stdlib.h> int work_load; pthread_mutex_t lock; void *worker (void *counter_ptr) { for (int i = 0 ; i < work_load; i++) { pthread_mutex_lock(&lock); (* (int *)counter_ptr) += 1 ; pthread_mutex_unlock(&lock); } return NULL ; } int main () { printf ("give the workload per thread: " ); scanf ("%d" , &work_load); pthread_t thread1, thread2; int counter; pthread_mutex_init(&lock, NULL ); pthread_create(&thread1, NULL , worker, &counter); pthread_create(&thread2, NULL , worker, &counter); pthread_join(thread1, NULL ); pthread_join(thread2, NULL ); pthread_mutex_destroy(&lock); printf ("Totally count: %d\n" , counter); return 0 ; }
运行一下，对比更改前后：
1 2 3 4 5 6 7 $ ./count give the workload per thread: 1000000000 Totally count: 1007291379 $ ./count give the workload per thread: 1000000000 Totally count: 2000000000
CH2 了解”互斥锁”这个概念，思考：
两个线程都同时访问了同一个变量：互斥锁
对于互斥锁的访问难道不会产生数据竞争吗？
回答:
为什么访问互斥锁不会产生数据竞争？
请尝试自己编写一个互斥锁(额外加分)
【操作系统】锁的实现
当一个线程获取互斥锁时，其他线程尝试获取必须等待，直到当前线程释放锁。互斥锁的实现由底层硬件或操作系统支持，通常通过某种原子操作，当一个线程访问其他线程持有的锁时，会被 OS 调度为阻塞状态（休眠），直到锁被释放后，再唤醒一个休眠的线程。
（另外，自旋锁是一种忙等待锁。它在锁被其他线程持有时不会阻塞当前线程，而是不断地尝试获取锁，直到锁可用为止。这种忙等待的行为称为“自旋”。）
使用了原子操作来实现互斥锁的加锁和解锁逻辑。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 typedef struct { atomic_int lock_flag; } my_mutex_t ; void my_mutex_init (my_mutex_t *mutex) { atomic_store (&mutex->lock_flag, 0 ); } void my_mutex_lock (my_mutex_t *mutex) { while (atomic_exchange(&mutex->lock_flag, 1 ) == 1 ) { sched_yield() } } void my_mutex_unlock (my_mutex_t *mutex) { atomic_store (&mutex->lock_flag, 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 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 #include <pthread.h> #include <stdio.h> #include <stdlib.h> #include <stdatomic.h> #include <sched.h> typedef struct { atomic_int lock_flag; } my_mutex_t ; void my_mutex_init (my_mutex_t *mutex) { atomic_store (&mutex->lock_flag, 0 ); } void my_mutex_lock (my_mutex_t *mutex) { while (atomic_exchange(&mutex->lock_flag, 1 ) == 1 ) { sched_yield(); } } void my_mutex_unlock (my_mutex_t *mutex) { atomic_store (&mutex->lock_flag, 0 ); } int work_load;my_mutex_t my_mutex;void *worker (void *counter_ptr) { for (int i = 0 ; i < work_load; i++) { my_mutex_lock(&my_mutex); (*(int *)counter_ptr) += 1 ; my_mutex_unlock(&my_mutex); } return NULL ; } int main () { printf ("give the workload per thread: " ); scanf ("%d" , &work_load); pthread_t thread1, thread2; int counter = 0 ; my_mutex_init(&my_mutex); pthread_create(&thread1, NULL , worker, &counter); pthread_create(&thread2, NULL , worker, &counter); pthread_join(thread1, NULL ); pthread_join(thread2, NULL ); printf ("Totally count: %d\n" , counter); return 0 ; }
📟Bitter CH1 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 #include <stdio.h> #include <stdlib.h> #define BOARD_SIZE 8 int upper_lim = 1 ;int count = 0 ;void solve_problem (int row ,int ld, int rd) { if ( row == upper_lim) { count += 1 ; return ; } int current = upper_lim & (~ (row | ld | rd)); int buffer = current; while (buffer) { int valid = buffer & (-buffer); buffer -= valid; solve_problem(row|valid, (ld|valid)<<1 , (rd|valid)>>1 ); } } void find_n_th_queen (int board_size ) { upper_lim = (1 << board_size) - 1 ; solve_problem(0 , 0 , 0 ); } int main () { find_n_th_queen(BOARD_SIZE); printf ("Answer: %d" , count); }
CH2 用位来标记数组元素的状态。
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 solve (nums ): n = len (nums) states = 1 << n max_sum = 0 for state in range (states): valid = True curr_sum = 0 for i in range (n): if state & (1 << i): curr_sum += nums[i] if i > 0 and (state & (1 << (i - 1 ))): valid = False break if valid: max_sum = max (max_sum, curr_sum) return max_sum nums = [1 , 15 , 3 , 7 , 12 , 10 , 19 , 8 , 5 , 17 , 2 , 6 , 11 , 9 , 4 , 14 , 13 , 18 , 16 , 20 ] print (solve(nums))''' 130 [Done] exited with code=0 in 0.965 seconds '''
动态规划可以显著降低时间。
加密算法：AES中存在行移位，哈希算法会使用位移、异或操作，提供安全性
快速运算：位移操作快速计算，奇偶判断，节约时间，bitset筛素数可节省空间
文件权限：使用位运算可以方便地开启或关闭某些标志位
并行计算：位运算可以快速地启用或禁用某个线程或者检查某个线程的状态
🎩顺手牵羊 要求： 使用C语言实现一个自己的抓包软件
使用libpcap库实现抓包。
程序应该实现：判断并输出每个包的类型，包的长度，以及包的源地址和目的地址。
如果你能实现对于TCP包的捕获，可以获得70%的分数。如果你能实现至少三种包的分析捕获，可以获得剩下30%的分数。
简单阐述下你对抓包的实现原理的理解，最高可得额外的20%分数。
hint： 要不下载一个wireshark体验下抓包？
题解：
在C语言中使用libpcap库来进行抓包操作。
安装libpcap库；
1 sudo apt install libpcap-dev
实现对TCP包的捕获；
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 #include <pcap.h> #include <stdio.h> #include <stdlib.h> #include <arpa/inet.h> #include <netinet/ip.h> #include <netinet/tcp.h> void packet_handler (u_char *user_data, const struct pcap_pkthdr *pkthdr, const u_char *packet) { struct ip *ip_header =struct ip *)(packet + 14 ); struct tcphdr *tcp_header =struct tcphdr *)(packet + 14 + ip_header->ip_hl * 4 ); printf ("<--------- New Packet Arrived! --------->\n" ); printf ("Total packet available: %d bytes\n" , pkthdr->len); printf ("Expected packet size: %d bytes\n" , pkthdr->len); printf ("IP header length (IHL) in bytes: %d\n" , ip_header->ip_hl * 4 ); printf ("Source Address: %s\n" , inet_ntoa(ip_header->ip_src)); printf ("Destination Address: %s\n" , inet_ntoa(ip_header->ip_dst)); printf ("TCP header length in bytes: %d\n" , tcp_header->th_off * 4 ); printf ("Size of all headers combined: %d bytes\n" , ip_header->ip_hl * 4 + tcp_header->th_off * 4 ); printf ("Payload size: %d bytes\n" , pkthdr->len - (ip_header->ip_hl * 4 + tcp_header->th_off * 4 )); printf ("---------------------------------------\n" ); } int main () { char errbuf[PCAP_ERRBUF_SIZE]; pcap_if_t *alldevs; pcap_if_t *device; pcap_t *handle; if (pcap_findalldevs(&alldevs, errbuf) == -1 ) { fprintf (stderr , "Error finding devices: %s\n" , errbuf); return 1 ; } device = alldevs; printf ("Using device: %s\n" , device->name); handle = pcap_open_live(device->name, BUFSIZ, 1 , 1000 , errbuf); pcap_loop(handle, 0 , packet_handler, NULL ); pcap_freealldevs(alldevs); pcap_close(handle); return 0 ; }
编译运行上述代码，打开firefox，捕获到数据包：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 $ gcc -o packet_sniffer packet_sniffer -lpcap $ sudo ./packet_sniffer Using device: loopback0 <--------- New Packet Arrived! ---------> Total packet available: 1514 bytes Expected packet size: 1514 bytes IP header length (IHL) in bytes: 20 Source Address: 127.0.0.1 Destination Address: 127.0.0.1 TCP header length in bytes: 32 Size of all headers combined: 52 bytes Payload size: 1462 bytes --------------------------------------- ......
这些数据包是在 WSL 2 内部通过 loopback 接口进行的本地通信，源头和目的地都是127.0.0.1。查找网络接口：
1 2 3 4 5 6 7 8 9 10 $ ip addr ... 4: loopback0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP group default qlen 1000 link /ether 00:15:5d:78:40:b2 brd ff:ff:ff:ff:ff:ff 5: eth2: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP group default qlen 1000 link /ether e0:2e:0b:08:09:53 brd ff:ff:ff:ff:ff:ff inet 192.168.0.144/24 brd 192.168.0.255 scope global noprefixroute eth2 valid_lft forever preferred_lft forever inet6 fe80::66a7:f661:86e5:c634/64 scope link nodad noprefixroute valid_lft forever preferred_lft forever
发现eth2是当前唯一状态为 UP 且配置了 IP 地址的接口，是WSL主要用于与外部网络通信的接口。修改代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int main () { ... for (device = alldevs; device != NULL ; device = device->next) { if (strcmp (device->name, "eth2" ) == 0 ) { found = 1 ; break ; } } if (!found) { printf ("Device eth2 not found. Make sure you have the necessary permissions.\n" ); pcap_freealldevs(alldevs); return 1 ; } ... }
编译运行结果如下：
1 2 3 4 5 6 7 8 9 10 11 <--------- New Packet Arrived! ---------> Total packet available: 66 bytes Expected packet size: 66 bytes IP header length (IHL) in bytes: 20 Source Address: 192.168.0.144 Destination Address: 34.107.243.93 TCP header length in bytes: 32 Size of all headers combined: 52 bytes Payload size: 14 bytes --------------------------------------- ...
实现对TCP、UDP和ICMP三种包的捕获：
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 93 94 95 96 97 98 99 100 101 102 103 104 105 #include <pcap.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <netinet/ip.h> #include <netinet/tcp.h> #include <netinet/udp.h> #include <netinet/ip_icmp.h> void packet_handler (u_char *user_data, const struct pcap_pkthdr *pkthdr, const u_char *packet) { struct ip *ip_header =struct ip *)(packet + 14 ); int ip_header_length = ip_header->ip_hl * 4 ; printf ("<--------- New Packet Arrived! --------->\n" ); printf ("Total packet available: %d bytes\n" , pkthdr->len); printf ("Expected packet size: %d bytes\n" , pkthdr->len); printf ("IP header length (IHL) in bytes: %d\n" , ip_header_length); printf ("Source Address: %s\n" , inet_ntoa(ip_header->ip_src)); printf ("Destination Address: %s\n" , inet_ntoa(ip_header->ip_dst)); switch (ip_header->ip_p) { case IPPROTO_TCP: { struct tcphdr *tcp_header =struct tcphdr *)(packet + 14 + ip_header_length); int tcp_header_length = tcp_header->th_off * 4 ; printf ("Protocol: TCP\n" ); printf ("TCP header length in bytes: %d\n" , tcp_header_length); printf ("Size of all headers combined: %d bytes\n" , ip_header_length + tcp_header_length); printf ("Payload size: %d bytes\n" , pkthdr->len - (ip_header_length + tcp_header_length)); break ; } case IPPROTO_UDP: { struct udphdr *udp_header =struct udphdr *)(packet + 14 + ip_header_length); int udp_header_length = 8 ; printf ("Protocol: UDP\n" ); printf ("UDP header length in bytes: %d\n" , udp_header_length); printf ("Size of all headers combined: %d bytes\n" , ip_header_length + udp_header_length); printf ("Payload size: %d bytes\n" , ntohs(udp_header->len) - udp_header_length); break ; } case IPPROTO_ICMP: { struct icmphdr *icmp_header =struct icmphdr *)(packet + 14 + ip_header_length); int icmp_header_length = 8 ; printf ("Protocol: ICMP\n" ); printf ("ICMP header length in bytes: %d\n" , icmp_header_length); printf ("Size of all headers combined: %d bytes\n" , ip_header_length + icmp_header_length); printf ("Payload size: %d bytes\n" , pkthdr->len - (ip_header_length + icmp_header_length)); break ; } default : printf ("Protocol: Other\n" ); break ; } printf ("---------------------------------------\n" ); } int main () { char errbuf[PCAP_ERRBUF_SIZE]; pcap_if_t *alldevs; pcap_if_t *device; pcap_t *handle; int found = 0 ; if (pcap_findalldevs(&alldevs, errbuf) == -1 ) { fprintf (stderr , "Error finding devices: %s\n" , errbuf); return 1 ; } for (device = alldevs; device != NULL ; device = device->next) { if (strcmp (device->name, "eth2" ) == 0 ) { found = 1 ; break ; } } if (!found) { printf ("Device eth2 not found. Make sure you have the necessary permissions.\n" ); pcap_freealldevs(alldevs); return 1 ; } printf ("Using device: %s\n" , device->name); handle = pcap_open_live(device->name, BUFSIZ, 1 , 1000 , errbuf); if (handle == NULL ) { printf ("Could not open device %s: %s\n" , device->name, errbuf); pcap_freealldevs(alldevs); return 1 ; } pcap_loop(handle, 0 , packet_handler, NULL ); pcap_freealldevs(alldevs); pcap_close(handle); return 0 ; }
运行代码抓包：
1 2 3 4 5 6 7 8 9 10 11 12 <--------- New Packet Arrived! ---------> Total packet available: 90 bytes Expected packet size: 90 bytes IP header length (IHL) in bytes: 20 Source Address: 185.125.190.57 Destination Address: 192.168.0.144 Protocol: UDP UDP header length in bytes: 8 Size of all headers combined: 28 bytes Payload size: 48 bytes --------------------------------------- ...
首先找到可用的网络接口，确保抓包工具监听到指定网络接口上的所有数据包；打开网络接口，置于混杂模式（1），以便捕获所有经过该接口的数据包；循环捕获包，调用回调函数，解析IP包头的字段，判断包所使用的传输层协议等等。
libpcap通过操作系统的网络驱动从链路层捕获数据包，将其暂存在内核缓冲区中，然后将数据包传递到用户空间供应用程序分析。
参考内容：
C语言如何做抓包
👿busin的野心 要求： 请你写个程序，自动检测排行榜的变化。具体有如下两个需求：
招新网站的排行榜包含10个招新相关方向以及一个总分方向。如果这11个类别中的任意一个排行的前十名 发生了变化，程序就会打印：1.新的前十名排行 2.哪一个人掉出了前十名 3.哪一个人进入了前十名。
程序应该监测特定的题目（使用动态容器的题目可以不被监测）。当有人通过了这个题目后，程序会按照f"passer: {user_name}, task: {task_name}, time: {passing_time}"打印出这条信息。
将程序部署在服务器上实现24h运行，并能通过社交软件/邮箱/其他能从移动设备上接收到更新信息的方式，将信息发送到你的移动设备上，实现可视化的管理界面。 (ps:这可能需要一点SA的知识）
题解： 首先编写程序rank.py实现打印排名变化情况。
在https://recruit.cnss.io/#/rank上，刷新页面在浏览器控制台网络中找到了fullrank，其通过XHR获取数据，说明排行榜的数据可能是通过该请求动态加载的。于是我们模拟浏览器的请求，**由于Token在随着时间变化，于是添加手动输入Token的部分： **
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 import requestsimport jsondef fetch (url, token ): headers = { "Accept" : "application/json, text/plain, */*" , "Accept-Encoding" : "gzip, deflate, br, zstd" , "Accept-Language" : "zh-CN,zh;q=0.9,en;q=0.8" , "Connection" : "keep-alive" , "Host" : "recruit.cnss.io:8443" , "Origin" : "https://recruit.cnss.io" , "Referer" : "https://recruit.cnss.io/" , "Sec-CH-UA" : '"Google Chrome";v="129", "Not=A?Brand";v="8", "Chromium";v="129"' , "Sec-CH-UA-Mobile" : "?0" , "Sec-CH-UA-Platform" : '"Windows"' , "Sec-Fetch-Dest" : "empty" , "Sec-Fetch-Mode" : "cors" , "Sec-Fetch-Site" : "same-site" , "User-Agent" : "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/129.0.0.0 Safari/537.36" , "Token" : token } try : response = requests.get(url, headers=headers) if response.status_code == 200 : return response.json() else : print (f"Failed to fetch rankings. HTTP Status Code: {response.status_code} " ) print (f"Response content: {response.text} " ) return None except requests.exceptions.RequestException as e: print (f"Error fetching rankings: {e} " ) return None
主函数流程，记录old_rankings.json文件，fetch得到new_rankings，对新旧排行进行比较，打印信息，更新old_rankings。
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 def main (): url = "https://recruit.cnss.io:8443/v1/fullrank" token = input ("Please enter your access token: " ).strip() if not token: print ("Your Token cannot be NULL." ) return try : with open ("old_rankings.json" , "r" ) as file: old_rankings = json.load(file) except FileNotFoundError: old_rankings = {} new_rankings = fetch(url, token) if new_rankings: changes = compare(old_rankings, new_rankings) print_changes(changes) with open ("old_rankings.json" , "w" , encoding='utf-8' ) as file: json.dump(new_rankings, file, ensure_ascii=False , indent=4 ) if __name__ == "__main__" : main()
下面是compare和print函数
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 def compare (old_rankings, new_rankings ): changes = {} for direction, new_top10 in new_rankings.items(): old_top10 = old_rankings.get(direction, []) old_top10_users = [item['Name' ] for item in old_top10[:10 ] if 'Name' in item] new_top10_users = [item['Name' ] for item in new_top10[:10 ] if 'Name' in item] entered = set (new_top10_users) - set (old_top10_users) dropped = set (old_top10_users) - set (new_top10_users) order_changed = old_top10_users != new_top10_users if entered or dropped or order_changed: changes[direction] = { 'new_top10' : [{'Name' : item['Name' ], 'Score' : item['Score' ]} for item in new_top10[:10 ] if 'Name' in item], 'entered' : list (entered), 'dropped' : list (dropped), 'order_changed' : order_changed } return changes def print_changes (changes ): if not changes: print ("排名未发生变化。" ) return for direction, details in changes.items(): print (f"\n方向: {direction} " ) print ("新的前十名排行:" ) for rank, user in enumerate (details['new_top10' ], start=1 ): print (f" 名次 {rank} : {user['Name' ]} (得分: {user['Score' ]} )" ) if details['entered' ]: print (f"进入前十名的人: {', ' .join(details['entered' ])} " ) else : print ("没有新进入前十名的人。" ) if details['dropped' ]: print (f"掉出前十名的人: {', ' .join(details['dropped' ])} " ) else : print ("没有掉出前十名的人。" ) if details['order_changed' ]: print ("前十名内部顺序发生了变化。" )
运行一下，得到输出。
接下来我们编写task.py程序。以一道题为例，我的思路是先在题目tasks那个页面，捕获特定题目的pass_number，当通过人数发生变化时，遍历用户，在passrecord寻找该题的通过者，异步化 代码实现如下
Python异步网络编程利器——详解aiohttp的使用教程
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 import aiohttpimport asyncioimport jsonfrom datetime import datetimeTASK_URL = "https://recruit.cnss.io:8443/v1/tasks/534" PASSRECORD_URL_TEMPLATE = "https://recruit.cnss.io:8443/v1/passrecord/{}" TARGET_TASK_TITLE = "👿busin的野心" USER_ID_RANGE = range (530 , 535 ) SLEEP_INTERVAL = 6 previous_pass_number = None user_submissions = {} token = "" async def fetch_pass_number (session ): headers = { "Accept" : "application/json, text/plain, */*" , "Accept-Encoding" : "gzip, deflate, br, zstd" , "Accept-Language" : "zh-CN,zh;q=0.9,en;q=0.8" , "Connection" : "keep-alive" , "Host" : "recruit.cnss.io:8443" , "Origin" : "https://recruit.cnss.io" , "Referer" : "https://recruit.cnss.io/" , "Sec-CH-UA" : '"Google Chrome";v="129", "Not=A?Brand";v="8", "Chromium";v="129"' , "Sec-CH-UA-Mobile" : "?0" , "Sec-CH-UA-Platform" : '"Windows"' , "Sec-Fetch-Dest" : "empty" , "Sec-Fetch-Mode" : "cors" , "Sec-Fetch-Site" : "same-site" , "User-Agent" : "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/129.0.0.0 Safari/537.36" , "Token" : token } try : async with session.get(TASK_URL, headers=headers) as response: response.raise_for_status() data = await response.json() tasks = data.get('dev' , []) for task in tasks: if task.get('title' ) == TARGET_TASK_TITLE: return task.get('pass_number' ) except aiohttp.ClientError as e: print (f"获取任务数据时发生异常: {e} " ) except Exception as e: print (f"处理任务数据时发生异常: {e} " ) return None async def fetch_user_submission (session, user_id ): headers = { "Accept" : "application/json, text/plain, */*" , "Accept-Encoding" : "gzip, deflate, br, zstd" , "Accept-Language" : "zh-CN,zh;q=0.9,en;q=0.8" , "Connection" : "keep-alive" , "Host" : "recruit.cnss.io:8443" , "Origin" : "https://recruit.cnss.io" , "Referer" : "https://recruit.cnss.io/" , "Sec-CH-UA" : '"Google Chrome";v="129", "Not=A?Brand";v="8", "Chromium";v="129"' , "Sec-CH-UA-Mobile" : "?0" , "Sec-CH-UA-Platform" : '"Windows"' , "Sec-Fetch-Dest" : "empty" , "Sec-Fetch-Mode" : "cors" , "Sec-Fetch-Site" : "same-site" , "User-Agent" : "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/129.0.0.0 Safari/537.36" , "Token" : token } url = PASSRECORD_URL_TEMPLATE.format (user_id) try : async with session.get(url, headers=headers) as response: response.raise_for_status() return await response.json() except aiohttp.ClientError as e: print (f"获取用户 {user_id} 的数据时出错: {e} " ) except Exception as e: print (f"处理用户 {user_id} 的数据时出错: {e} " ) return None
整个函数的逻辑是这样的：通过fetch初始化每个用户（这里是530到535）的提交内容，记录下来，然后每6秒去监测特定题目的通过人数有没有发生变化，一旦发生变化，调用check函数遍历比对，打印出信息。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 async def main (): global token token = input ("请输入Token: " ).strip() if not token: print ("Token不能为空。" ) return user_ids = USER_ID_RANGE async with aiohttp.ClientSession() as session: await initialize_user_records(session, user_ids) while True : await monitor_pass_number(session, user_ids) await asyncio.sleep(SLEEP_INTERVAL) if __name__ == "__main__" : try : asyncio.run(main()) except KeyboardInterrupt: print ("\n程序已手动终止。" )
下面我们完善遍历用户，进行初始化用户的提交内容：
1 2 3 4 5 6 7 8 9 10 async def initialize_user_records (session, user_ids ): global user_submissions tasks = [fetch_user_submission(session, user_id) for user_id in user_ids] submissions = await asyncio.gather(*tasks) for user_id, submission in zip (user_ids, submissions): if submission is not None : user_submissions[user_id] = submission print (f"初始记录已保存用户 {user_id} 。" ) else : print (f"未能获取用户 {user_id} 的初始记录。" )
接着监测特定题目人数并在变化时遍历：
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 async def monitor_pass_number (session, user_ids ): global previous_pass_number current_pass_number = await fetch_pass_number(session) if current_pass_number is not None : if previous_pass_number is None : previous_pass_number = current_pass_number print (f"初始 pass_number: {current_pass_number} " ) elif current_pass_number > previous_pass_number: print (f"pass_number 增加了！新的 pass_number: {current_pass_number} " ) await check_user_submission_changes(session, user_ids) previous_pass_number = current_pass_number else : print (f"当前 pass_number: {current_pass_number} " ) else : print ("无法获取 pass_number" ) async def check_user_submission_changes (session, user_ids ): global user_submissions tasks = [fetch_user_submission(session, user_id) for user_id in user_ids] submissions = await asyncio.gather(*tasks) for user_id, new_submission in zip (user_ids, submissions): if new_submission is None : continue previous_submission = user_submissions.get(user_id, []) new_tasks = {task['TaskID' ]: task for task in new_submission} old_tasks = {task['TaskID' ]: task for task in previous_submission} for task_id, new_task in new_tasks.items(): old_task = old_tasks.get(task_id) if not old_task or old_task.get('Score' ) != new_task.get('Score' ): if new_task.get('TaskTitle' ) == TARGET_TASK_TITLE: user_name = f"User {user_id} " task_name = new_task.get('TaskTitle' ) passing_time = datetime.now().strftime("%Y-%m-%d %H:%M:%S" ) print (f"passer: {user_name} , task: {task_name} , time: {passing_time} " ) user_submissions[user_id] = new_submission
运行上述代码，得到输出结果。速度有明显提升。
🤖GPT2 目标： 你可能已经发现了，你的程序可能并没有我演示的跑的那么快（神机请忽略）。
你的目标就是优化该程序的性能，在保证结果不变的情况下更快的完成文本的补全。
我会使用一些测试点来评测你的程序的正确性和执行时间。期待更高的效率和更多样的优化方案。
此外，请在 wp 中回答下面的问题：
什么是阿姆达尔定律？根据阿姆达尔定律，我们应该把优化的重点放在哪里？
你的优化方案和思路是什么？优化的效果受到哪些因素影响？
题解： 按照指示完成GPT2，make运行一下，发现需要20多秒。
阿姆达尔定律是一个经验法则，代表处理器并行运算之后效率提升的能力。在并行计算中，使用多个处理器的程序的加速比受限制于程序串行部分
$s(n):$ 固定负载下，理论上的加速比
$B:$ 串行工作部分所占比例，取值0~1
$n:$ 并行线程数，并行处理节点个数
可以看出，即使我们增加处理器数量，只能对并行部分产生影响，而对非并行部分没有任何影响。因此随着处理器数量增加，整体性能的提升会趋于平缓。
根据阿姆达尔定律，应该将优化重点放在最小化串行部分，同时最大化可并行部分 。
浏览源gpt.c代码中注意到，存在矩阵乘法、注意力机制和涉及大量计算的循环，可以进行并行计算，将任务分配到多个处理器上，使用OpenMP并行化矩阵乘法、前馈神经网络层等。
具体操作是在matmul_forward和attention_forward函数循环前添加代码：
1 2 #include <omp.h> #pragma omp parallel for collapse(2)
同时，在MakeFile中开启编译选项-fopenmp。
1 2 3 4 5 release: cc gpt.c -lm -O3 -fopenmp -Wno-unused-result -Wno-unused-value -Wno-unused-variable -o gpt debug: cc gpt.c -lm -O1 -g -fopenmp -Wno-unused-result -Wno-unused-value -Wno-unused-variable -o gpt
前后对比一下
在保证结果不变的情况下更快的（5~6秒)完成了文本的补全。
优化效果受影响的因素：
串行部分：总加速比会受到制约
硬件资源：可用处理器的数量和硬件的性能
编译器的优化程度
并行化的开销。
