猪脚说第十三期

猪脚说第十三期

Diandian funny boy
  2023-07-14 22:51:36 2023-07-14 22:51:36 Created   2023-07-14 22:54:39 2023-07-14 22:54:39 Updated    3.5k Words  13 Mins  

大作业相关问题

常见问题 & 基本注意事项

  • 文件的读入：推荐大家使用以下方式读取hashvalue.txt的内容：
1
2
3
4
5
6
7
8
char Hash[10001][130];
FILE *fph;
fph = fopen("hashvalue.txt","rb");
int i;
for (i = 0; i < M; i++) {
  fscanf(fph, "%s", Hash[i]);
  Hash[i][N] = '\0';
}

如果大家在本地运行时样例输出完全正确（包括键盘输出和result.txt的输出），而提交小数据点时输出错误，不妨把读入article与sample的模式也改为"rb"，如果发现输出结果出现变化，大概率是因为你对于\r\n的处理不够仔细（大多是因为你对换行符进行了形如if (c == '\n')的特判）。

一种建议的修改方式即为将读入模式改为"rb"，这样就可以原封不动地得到txt文件中的所有数据。此时，你就可以将\r与\n看作独立的两个字符，分别进行特判即可。

  • 换页符只出现在文章与文章之间，最后一篇文章是没有\f的，有些同学把“读到换页符”这一条件作为读完一篇文章的标志，那么就需要检查最后一篇文章有没有被读入；
  • 换页符\f紧跟着的那一行不一定就是下一篇文章的标识号，有可能隔着很多空行，因此不能在读到\f后直接执行fgets()并把读到的内容作为文章标识号。以下代码作为正确读取文章标题的参考：
1
2
3
4
5
6
7
8
if (c == '\f') {
  // do something
  while (!isspace(c = fgetc(fp)))
      ; // 读到非空白字符为止，说明已经跳过所有空行
  ungetc(c, fp); // 将此时读进来的非空白字符 c 退回到 fp 指向的文件流中
  fgets(/* ... */); // 按行读入即为文章标识号
  // 删除读进来的换行符
}
  • 题目中没有任何一句话表明文章标识号的形式一定是XX-XXXX的数字形式，事实上任意字符串都可以是文章的标识号（包括空格，因此也请不要使用fscanf()等读不进来空格的函数），因此不要自作主张在输出时直接写成printf("1-%d", count);的形式；
  • 用fgetc()读入字符时，请一定要用int型的变量存储：
1
2
3
4
int c;
while (c = fgetc(fp)) {
  // do something
}
  • 数组的大小要仔细考量，保证读入的数据不会越界。相关数据范围参考课程群中给出的消息；
  • 检查数组存储下标的一致性。

优化

优化 I/O

  • printf、scanf改成getchar、putchar快读快写；
  • 先使用fread将文件内容整个读进内存，再对内存进行后续操作；
  • 尽可能减少重复读入，比如不要连续读多遍文件。

减少遍历次数

  • 不要写出如下形式的代码
1
2
3
4
5
6
7
8
while (c = fgetc(fp)) {
  // do something
  for (i = 0; i < strlen(s); i++){ // 不要出现
    // do something
  }
  // do something
  memset(/* ... */); // 不要出现
}

因为strlen与memset的原理就是对整个数组进行for循环，再把这样的函数放入循环里，时间复杂度一下就上去了。当然论效率memset还是相对较高的，在必要的初始化、“新的开始”之处，不要因为缺省了一些操作而导致错误。

压榨性能

  • 存储结构

    • 顺序存储（数组）？链式存储（指针）？
    • 一般情况下，访问数组的效率明显高于通过指针的间接访问

  • 查找方式

    • 二叉查找树？bsearch函数？trie树？
    • 如果使用trie树，请思考在建立树时是否一定需要把单词一起存储进去（浪费大量时间）？

  • 将逻辑简单的函数改写为宏，可以减少函数调用的时间，例如isalpha、tolower等；

  • 尽量少调用 C 库函数，一般建议只需使用stdio.h与stdlib.h即可；

  • 合理封装功能模块，例如把“获取一个单词”写成函数，它会被调用非常多次，则开销巨大；把“读取 article 并完成词频统计”封装成一个函数，在逻辑上较为清晰，且开销较小（当然只有一个main理论上最高效，但不建议写成一坨）；

  • 频繁访问的变量可以声明为register，“建议”编译器将这个变量存储在寄存器中，提供更高速的访问；

    注意，这种类型的变量只能是局部变量，并且通常用于循环变量，如在main的开头写register int i = 0;或者for循环的括号中写for (register int j = 0; j < n; j++)，切勿滥用！

  • 其他：内嵌汇编asm(...)、内联函数inline、编译优化（昵称“开火车”）#pregma GCC optimize("O3")等方法（想要把时间压缩到极致的同学，建议了解一下汇编语言）。

时间度量

  • 可以使用本地操作系统的库以进行高精度的时间测量。（上网搜索：C 语言，时间，<time.h>等）

  • 使用 Visual Studio 自带的时间分析工具，可参考https://blog.csdn.net/tfb760/article/details/96900098

  • 可针对性地对某个函数、某个语句进行优化。

函数指针

这部分在本课程用处不大，但在以后很有用。

你想过吗，qsort函数的那个cmp到底是什么呢？

引入

我们有如下的观点

  • 指针变量是一种特殊的整型变量，用于存放地址值，地址就是一个整数
  • 通过指针可以间接访问一个普通变量、一个结构体、一个数组等
  • 地址和内存息息相关，地址就是某个内存中的存储单元的编号
  • 数组名就是指针

现在我们再提出以下观点

  • 函数也储存在内存中，函数也有“首地址”
  • 函数名就是指针，是指向该函数的指针，称为“函数指针”
  • 在函数指针后加上括号，表示对该函数的调用（call）；这里没有用*解引用的过程，这是 C 语言提供的便捷写法，事实上，要解引用也可以。

我们通过两个例子验证上述观点。

C 语言中，%p表示用十六进制输出一个地址值，指针中存放的地址值就可以用这种格式输出，当然，地址是一个整数，也可以用%d %ld %lld %u等形式输出，只是可能有 warning。

1
2
3
4
5
6
7
8
#include <stdio.h>

int main() {
	int a;
	printf("NULL: %p\n", NULL);
	printf("&a: %p\n", &a);
	return 0;
}

一种可能的输出是

1
2
NULL: 0x0
&a: 0x16b913578

当然，“可能”指的是a的地址，NULL必然是恒定的值 0，表示一个“无效地址”。

1
2
3
4
5
6
7
8
9
10
// 案例 1
#include <stdio.h>
void f() {
	// do nothing
}
int main() {
	printf("main: %p\n", main);
	printf("f: %p\n", f);
	return 0;
}

我们用地址的格式输出main函数和f函数的地址，得到的可能结果是

1
2
main: 0x1004c3f30
f: 0x1004c3f2c

显然，这两个函数在内存中都是有地址的，它们（的机器代码）就存放于内存中。

1
2
3
4
5
6
7
8
9
10
11
// 案例 2
#include <stdio.h>
void f(int i) {
	printf("The number is %d\n", i);
}
int main() {
	f(10);    // 函数指针加上括号实现调用
	(*f)(20); // 先给函数指针解引用得到“函数”，再调用
              // 调用的优先级高于解引用，所以前面加了括号
	return 0;
}

输出为

1
2
The number is 10
The number is 20

这说明函数名就是指针，是指向该函数的指针，函数指针也可以解引用，得到对应的函数后再进行调用，但没必要。

函数指针类型

通过上述两个案例，我们意识到，函数本身也是一个地址值，只要知道了函数的地址，就可以实现对该函数的调用。显然，函数名就是函数的地址；但是另一方面，地址也需要存储在一个指针变量中。

我们知道，指针是有类型的，指针值本身是一个整数，它指向什么类型的变量，则需要由指针的类型表示。换言之，地址值是一个整数，但是怎么解释、怎么访问那个地址处的内容，需要由指针的类型决定。

我们通过一个例子，探索函数指针的类型。

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>
void f(int i) {   
    // 函数 f，需要一个 int 作为参数，无返回值
	printf("i + 100 = %d\n", i + 100);
}
double sum(double a, double b) {
    // 函数 sum，需要两个 double 作为参数，返回值为 double 类型
	return a + b;
}
int main() {
	void (*ptr)(int) = f;
        // void 是函数的返回类型
        // ptr 是指针变量的名字
        // int 是该函数所需要的参数
        // 定义了一个名为 ptr 的函数指针，它指向一个返回类型 void、参数为一个 int 的函数
	ptr(20);     // 通过函数指针直接调用函数
	(*ptr)(30);  // 解引用得到“函数”，再调用（没必要这么写）

	double (*p_sum)(double, double) = sum;
    // 定义了一个名为 p_sum 的函数指针，它指向一个返回类型为 double、参数为两个 double 的函数
	printf("ans: %.2f\n", p_sum(3.14, 2));
    // 通过函数指针调用函数
	return 0;
}

上例输出为

1
2
3
i + 100 = 120
i + 100 = 130
ans: 5.14

这个简单的例子足以明确如何定义、如何使用函数指针，归结起来，函数指针的通用格式就是

1
[函数返回值类型] (*[函数指针变量名])(函数参数列表)

如此一来，我们再考察qsort函数，就会豁然开朗，这个函数的原型如下

1
2
3
4
void qsort(void *base,   // 数组首地址
           size_t n,     // 元素个数
           size_t width, // 单个元素的字节数
           int (*cmp)(const void *, const void *));

第四个参数cmp就是一个函数指针，它指向一个返回值为int、参数为两个const void *的函数。显然qsort内部并不会把排序时元素比较的规则写死：if (a[i] < a[i + 1])，而是通过调用cmp函数从而实现用户自定义规则的比较

1
2
3
4
5
if (cmp(&a[i], &a[i + 1]) > 0) {
    // 把 a[i] 放到 a[i + 1] 后面
} else if (cmp(&a[i], &a[i + 1]) < 0) {
    // 把 a[i] 放到 a[i + 1] 前面
} // 没有规定相等时谁前谁后

以上一段只是形象说明，实际上，为了容纳任意类型的数组，qsort采用了**void*通用指针的手段，并要求传入单个元素大小width。事实上，内存中的[base, base + width)这一段空间对应数组首元素，[base + width, base + 2 * width)对应第二个元素，以此类推。在交换元素时，并不是简单的赋值，而是用memcpy、memset等方法修改内存**。另一方面，正因为如此，cmp函数的两个参数也都是通用指针，我们在实现cmp时必须强转类型，从而实现对某一特定类型数据的比较。

函数指针数组

函数指针是单个变量，一堆函数指针就是一个数组。函数指针数组在操作系统内核代码中十分常见，我们用一个简单的例子，模拟一个情形：用户不停发来请求，操作系统根据请求的不同，调用不同的处理函数（handler），响应用户请求。

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
#include <stdio.h>
void handler0(const char *s) {
	printf("[%s]handling request 0\n", s);
}
void handler1(const char *s) {
	printf("[%s]handling request 1\n", s);
}
void handler2(const char *s) {
	printf("[%s]handling request 2\n", s);
}
void (*handlers[3])(const char *) 
	= { handler0, handler1, handler2 };
// 含有三个函数指针的函数指针数组，数组名为 handlers
// 每一个指针都指向一个返回值为 void，需要一个 const char * 参数的函数

int main() {
	int request;
	while (1) {
		scanf("%d", &request);    // 输入请求号
		if (request == -1) break; // 如果是 -1 就结束
		handlers[request]("This is kernel");
           // 调用对应的处理函数
           // handlers 是处理函数的数组
           // request 表示请求号，handlers[request] 表示对应的处理函数的指针
           // 函数指针后直接加括号，放入参数，即可调用
           // 当然这里如果输入大于 2 的数程序就崩溃了
	}
	return 0;
}

返回函数指针的函数（雾）

函数指针是一种指针，是一个整数，一个函数当然可以返回一个指针，这个指针当然可以是函数指针。写着比较套娃，直接看例子，这种情况一般不会用到，但是在有的地方可能会看到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
double solve(int r) {
    // 这是一个求圆的面积的普通函数，参数为一个 int，返回值是 double
	return 3.14 * r * r; // 整数遇上浮点数，都转化为浮点数计算，别忘了！
}

double (*return_func_ptr(void))(int) {
    // 这是一个返回函数指针的函数
    // 函数名是 return_func_ptr
    // 函数本身不需要参数，所以参数列表写 void，也可以留空
    /* 函数的返回值是一个函数指针，
            这个函数指针指向一个返回值为 double、需要一个 int 作为参数的函数 */
	return solve; // 函数名就是函数指针，所以返回了 solve 函数
}
int main() {
	printf("ans: %2.f\n", return_func_ptr()(10));
    // 调用 return_func_ptr 函数对应的是 `return_func_ptr()`
    // 调用后的返回值是一个函数指针，可以继续调用，所以后面直接跟上了 `(10)`
    // 如果写的是 `(*((*return_func_ptr)()))(10)` 可以吗（?）
	return 0;
}

如果你能理解这段奇怪的代码，说明你对函数指针的认识到位啦！

Author: diandian, Riccardo

  • Title: 猪脚说第十三期
  • Author: Diandian
  • Created at : 2023-07-14 22:51:36
  • Updated at : 2023-07-14 22:54:39
  • Link: https://cutedian.github.io/2023/07/14/猪脚说第十三期/
  • License: This work is licensed under CC BY-NC-SA 4.0.
推荐阅读
猪脚说第二期 猪脚说第二期 猪脚说第一期 猪脚说第一期 猪脚说第五期 猪脚说第五期
推荐阅读
猪脚说第二期 猪脚说第二期 猪脚说第一期 猪脚说第一期
Comments
On this page
猪脚说第十三期
  1. 1. 大作业相关问题
    1. 1.1. 常见问题 & 基本注意事项
    2. 1.2. 优化
      1. 1.2.1. 优化 I/O
      2. 1.2.2. 减少遍历次数
      3. 1.2.3. 压榨性能
    3. 1.3. 时间度量
  2. 2. 函数指针
    1. 2.1. 引入
    2. 2.2. 函数指针类型
    3. 2.3. 函数指针数组
    4. 2.4. 返回函数指针的函数（雾）