指针和数组,到底哪个快,顺便讨论写实验报告

1个月又10天以前,MYL同学给我看了2段代码,是C语言的字符串接接函数strcat的实现。一段代码用的方法是数组,另一段用的是指针。问题是,一般使用指针实现,而不用数组,是因为指针更快呢,还是仅仅出于习惯/习俗/惯用法。

代码大致是这样的。

用指针实现的 strcat,如下。
: void str_cat_pointer(char* from, char* to)
: {
:     while(*to != 0)
:         to++;
:     while(*from != 0)
:         *to++ = *from++;
:     *to=0;
:
: }

用数组实现的 strcat,如下。

void str_cat_array(char from[], char to[])
{
int i,j;
for(i=0; to[i]!= 0; i++)
;
for(j=0; from[j]!=0; i++,j++)
to[i] = from[j];
to[i]=0;
}

插叙:MYL同学的代码有bug,并且我没有问她要授权,所以不宜发布在这里。她的代码有小bug,逻辑错误,对于当前讨论的问题是个题外话,所以不讨论了。不过,对于写实验报告这个主题,这是个有意义的话题。在实验中,不能假设原材料是干净的,不能假设工具是可用的,也不能假设仪器是校准过的。需要在实验前先”测空白”。就像在哪吒闹海里,祭童男童女就下雨 这个论断,需要先测空白,即不祭童男童女就不下雨,然后再去尝试伪原论断。如果不祭童男童女也下雨呢,那么原论断就不知道真假了。MYL同学的代码有毛病,得改成能跑、跑得对,才能进一步讨论。

插叙:当晚我做了实验答复她,但是为什么花了一个多月才写这篇博客呢。这也是实验报告写作中的一个问题,那就是大家都不乐意写,懒。实验比报告有意思。不过,即使不写实验报告,也应该按实验报告的大纲和要求设计实验、做实验并保证结论严谨。

上述代码,学过C语言的同学都很熟悉。一般教材在这里会指出 *(p+i) 与 p[i]是”等价”的。

诉诸权威,用教材来回答当然也是个路线,这样就不必做实验了。不过,那样需要找到教材,查到原文。不然的话,万一对原文理解错误,小细节没记清楚,被追究到以后就说”哎呀,我没记清啊”,真是不严谨认真的人。这也是我不主动不积极回答同学们疑问的原因,特别是事涉人生发展的,因为真是累啊。也有的同学可能说,我对你的意见也不会那么重视,你为啥这么大压力呢。如果你不重视我的意见,还问我羞辱我干嘛,不如去扔个色子。

我当时手头刚好没教材,需要花点时间找。而且,找到教材,就有说服了么?在我的记忆里,教材里没有提到,这是习惯用法,还是效率就是高。即使教材提到”等价”,也是指在这样不同的语法下,二者的语义是等价的。语义在这里包括什么呢,非常可能,只包括函数映射意义上的执行结果,而不包括对效率的讨论。即使教材说”习惯上”这么写,我也会认为作者在瞎扯。

好了,所以,需要做个实验看看 二者的效率 是不是一样。如果效率一样,我们就可以继续假设 单单是习惯上的原因。

还有一种可能,你读到这里已经早已按捺不住拍案而起,”我知道,不就是……”这时,要么,我们需要证据和论证过程,而不是拍胸脯;要么,你是权威,我们诉诸你。写实验报告还不利索的同学,你不是权威。或者你是权威,但是早有一天,你会遇到不信你的人,得给出证据和论证过程。这就是学数学的时候,我们哭丧着脸说”我信,我信,我服了还不行么”也不行的原因。早晚有一天,会有不信的人,只有理性、逻辑、证据和论证过程方能说服。

实验是这样设计的。

1. 准备材料,两个数组/指针字符串。

:     char f[11]=”0123456789″;
:     char t[30]=”abcd”;

2. 操作

用其中一个函数拼接字符串,拼接 1000000 次。

:         for(int i=0; i<1000000L; i++)
:         {
:             strcpy(f, “0123456789”);
:             strcpy(t, “abcd”);
:             str_cat_pointer(f, t);
:             //printf(“\n%s\n”, t);
:         }

为什么拼接这么多次呢?别笑。确实有不止一位同学在做实验的问过我,为啥我测不出来呢。因为次数不够、速度太快、时间太短,所以没测到。我们如何称量1粒米的重量?准备1kg米,然后数有多少粒,用1kg除以米粒的数量。

所以要拼接 1000000 次,为了 明显地可观察到结果。如果你的机器格外快怎么办,再拼接几次。如果 i 的大小超过了整数64位宽,开始回卷了怎么办?好问题,请阅读 CSAPP。

在回到主线——如果 拼接 1000000 次 就可以测到——之前,有的同学可能会问,你怎么知道拼接 1000000 次就够呢。我不知道,我瞎编的,我测了一下。在我机器上40多毫秒,能测出来了。如果时间太长,我就准备减小这个数;如果时间短到测不出来,我就准备增加这个数。二猫他们有一套计算方法,能大致估算出迭代多少次的数量级,我不会,又没请教,所以就靠实验方法了。

3. 测量

在拼接操作之前,测一下时刻。

:     clock_t begin, duration;
:         begin = clock();

在拼接操作之后,再测一下时刻。求开始与结束的时刻之差,这段时间间隔,就
是拼接1000000次所花费的时间,是我们要测量的物理量。

:         duration = clock() – begin;
:         printf( “\n%d ms in str_cat_pointer.”, duration*1000 / CLOCKS_PER_SEC );

4. 多测几次

别笑。我确实见过不止一位同学,测了一次就给出结论。类似于,我看到过隔壁张大妈家小子从来不学习还能考上清华,因此我也能。计算机科学学生,误解了算法的可重现性。只有算法具有可重现性,算法在真实世界中的应用,其效率并不可重现,或者说是理论值的基础上叠加了噪音。即使在算法所应用于其上的数据是一致的,在CPU上跑的时候,运行的环境也*无法*保证一致。有没有别的进程,操作系统心情好么,CPU温度如何,对结果时间间隔这个物理量都有影响。

真实客观世界的物理量,如果测量与理论不符,那么就只能是理论错了。即使测量的方法有误,也是我们对测量的方法的理论理解有误。真实客观世界本身从来不会错。

所以外面套个循环,跑10次。

:     for(int k=0; k<10; k++)

5. 对比

跑10轮数组的版本,再跑10轮指针的版本。得到2*10组数据。

此外有图chart和表格table。

无优化

并且! 还要有结论啊同学们。经常有同学把数据拿出来,不给结论。那意思就是傲慢地说: 你看吧,结论多么显然。如果你没有看到这结论如此显然,就是你傻得如此显然。或者,那意思就是,尊敬的老师,证据我已经给出了,结论得由您才有资格尊贵地给出。

结论得写实验报告的人给。如果结论符合假设、实验目的,就把假设或实验目的再说一遍,并且说,实验证据支持 (事实上,波普尔说并不能证实)实验目的。如果实验证据与假设矛盾,就把实验目的再说一遍,然后说,证据与假设矛盾。

得说,明确说。

实验数据展示了,指针的写法比数组的写法 所花费的时间更短,即运行速度更快。拼接1000000次,重复10轮,每轮实验中指针版”大约”比数组版快5毫秒~9毫秒。我到这里就满意了,更严格的实验还应该给出误差范围和来源、方差分布、置信度什么的。

实验表明,在字符串拼写函数的实现中,指针的写法比数组的写法效率更高。结论是假设指针效率高,实验证据展示的是 (在这些特定的跑过的实验中) 指针的效率高,结论与证据间有联系——并且这一联系是否合理也公开出来接受别人的检验。

6. 反转

给出证据和结论,我顺手查了一下理论。是不是在语义上,指针和数组还是有微小的区别。请知道得受不了拍案而起的同学,把解释留在评论中供其他读者膜拜,在这里不是主线,我略过。

看这些资料时,我注意到有人提到 编译优化。我面无表情地做了个”吼”的表情,还是考虑不周。

按下述两种编译参数分别编译了代码跑一遍,发现故事有反转。

: “c:\Program Files (x86)\CodeBlocks\MinGW\bin\mingw32-gcc.exe” point.c

: “c:\Program Files (x86)\CodeBlocks\MinGW\bin\mingw32-gcc.exe” -O2 point.c

此外有图chart和表格table。

有优化

由于优化,代码运行的速度更快了。还是这些数据,还是这些代码,材料和工具都没变,测量方法也没变。原来35毫秒的指针,跑到了10毫秒,快了3倍有余。

更吸引我们注意的是,原来的数组版本受到优化的正面影响更大。数组版本跑到9毫秒,由优化前比指针版本慢一跃达到比指针版本更快了。

往上看,不仅要有图,还要有对图的解读。

优化以前,指针更快;优化以后,数组更快。所以,之前的结论是错的,也许写成指针,只是习惯吧。或者当年尚不能这样优化的时候,指针曾经更快过。

7. 未尽事项

实验”大致”得出了结论,至少比原始的猜测要更深入了。但是,还有些遗留问题,只是通常对结论没有影响,我们就没有讨论。这与”我的证据是假的”但是不影响我的结论不同。而是即使深入讨论,我们也已经准备好了答辩的应对。

比如,在指针和数组实验中,计时都包括了 strcpy 的时间。我们假设,strcpy的效率是稳定的,因此在1000000次计数中,我们可以剃除这部分时间。

诸如这类的假设还有很多,例如我们假设拼接更长或更短的字符串,不影响我们的结论。甚至可能进一步假设接接所花的时间会随字符串之一的长度成线性增长。我们假设 后++ 与 前++ 所花费时间区别不大,因此没有做 前++ 的实验。我们假设传参的时候用数组还是指针对时间没有影响。我们假设先做数组还是先做指针版的拼接,对于结果没有影响。

就像我们假设了物理定律的在宇宙中是普适的,我们假设材料各向同性。

这些假设可能被其他人指出”是错误的假设”,或者这些假设并不总成立,或者假设成立是有条件的。我们的结论就要再修正。

公开实验证据,公开实验设计和实验数据;明确说明论证过程,明确给出结论和证据间的逻辑联系。期待别人指出其中的失误。如果暂时没有人指出,要么咱们暂时继续假设结论是对的吧,要么做的东西不值得讨论,不值得别人花时间否定。

全部代码是这样的。

/*
>”c:\Program Files (x86)\CodeBlocks\MinGW\bin\mingw32-gcc.exe”  point.c

>”c:\Program Files (x86)\CodeBlocks\MinGW\bin\mingw32-gcc.exe”  -O2 point.c
*/

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>

void str_cat_pointer(char* from, char* to)
{
while(*to != 0)
to++;
while(*from != 0)
*to++ = *from++;
*to=0;

}

void str_cat_array(char from[], char to[])
{
int i,j;
for(i=0; to[i]!= 0; i++)
;
for(j=0; from[j]!=0; i++,j++)
to[i] = from[j];
to[i]=0;
}

int main()
{
clock_t begin, duration;

char f[11]=”0123456789″;
char t[30]=”abcd”;

for(int k=0; k<10; k++)
{
//—————————
begin = clock();
for(int i=0; i<1000000L; i++)
{
strcpy(f, “0123456789”);
strcpy(t, “abcd”);
str_cat_pointer(f, t);
//printf(“\n%s\n”, t);
}
duration = clock() – begin;
printf( “\n%d ms in str_cat_pointer.”, duration*1000 / CLOCKS_PER_SEC );
}

for(int k=0; k<10; k++)
{
//—————————
begin = clock();
for(int i=0; i<1000000L; i++)
{
strcpy(f, “0123456789”);
strcpy(t, “abcd”);
str_cat_array(f, t);
//printf(“%s\n”, t);
}
duration = clock() – begin;
printf( “\n%d ms in str_cat_array.”, duration*1000 / CLOCKS_PER_SEC );
}

return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *