巧用指针为复制数组加速

在OI中，经常要用到递推，有时候递推式可以转换为变量间的转换，比如Fibonacci数列。而当数据量提升时，就常常要用到高精度算法，也就将单个变量转化为数组，因此就用到了数组的复制。对于C/C++用户，可以使用memcpy函数；对于pascal用户，可以直接赋值；另一个通法则是用循环遍历并复制数组。但不管怎样终究是要复制数组，这一步需要额外O(n)的时间（n代表数组元素个数）。说是额外，因为这可以当作一个常量，并不算在算法的时间复杂度上。比方说我们一般认为计算Fibonacci数列的时间复杂度是O(n)。

那么有没有什么办法可以使得这一常量时间得到减小呢？我们不妨以计算Fibonacci数列为例，分析一下。 
f2 = 0
f3 = 1
for i=2 to n
  f1 = f2
  f2 = f3
  f3 = f1 + f2

可以看出f1,f2,f3是循环的。那么既然复制数组的时间很长，为什么我们不用指针呢？复制指针只需要O(1)的时间，说不定能大大的缩短程序运行的时间。下面分别是采用直接复制和复制指针的两个程序（pascal语言）：

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

//fib1.pas
const MAXLEN=6000;
type high=array[0..MAXLEN]of longint;
var n,i:longint;
    f1,f2,f3:high;
procedure plus(var c,a,b:high);
  var larger,x,i:longint;
  begin
    fillchar(c,sizeof(c),0);
    if a[0]>b[0] then larger:=a[0] else larger:=b[0];
    x:=0;
    for i:=1 to larger do begin
      x:=a[i]+b[i]+x div 10000;
      c[i]:=x mod 10000;
    end;
    if x>=10000 then begin
      c[larger+1]:=1;
      c[0]:=larger+1;
    end else c[0]:=larger;
  end;
begin
  assign(input,'fib.in');reset(input);
  assign(output,'fib.out');rewrite(output);
  fillchar(f1,sizeof(f1),0);
  fillchar(f2,sizeof(f2),0);
  f3[0]:=1;f3[1]:=1;
  readln(n);
  for i:=2 to n do begin
    f1:=f2;
    f2:=f3;
    plus(f3,f1,f2);
  end;
  write(f3[f3[0]]:4);
  for i:=f3[0]-1 downto 1 do begin
    if f3[i]<10 then write('000') else
    if f3[i]<100 then write('00') else
    if f3[i]<1000 then write('0');
    write(f3[i]);
    if (f3[0]-i+1)mod 10=0 then writeln;
  end;
  close(input);close(output);
end.
[pascal highlight=“6,27,28,31,32,33,34,35”] //fib2.pas const MAXLEN=6000; type high=array[0..MAXLEN]of longint; var n,i:longint; a,b,c:high; f1,f2,f3,bak:^high; procedure plus(var c,a,b:high); var larger,x,i:longint; begin fillchar(c,sizeof(c),0); if a[0]>b[0] then larger:=a[0] else larger:=b[0]; x:=0; for i:=1 to larger do begin x:=a[i]+b[i]+x div 10000; c[i]:=x mod 10000; end; if x>=10000 then begin c[larger+1]:=1; c[0]:=larger+1; end else c[0]:=larger; end; begin assign(input,‘fib.in’);reset(input); assign(output,‘fib.out’);rewrite(output); fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); f1:=@a;f2:=@b;f3:=@c; f3[0]:=1;f3[1]:=1; readln(n); for i:=2 to n do begin bak:=f1; f1:=f2; f2:=f3; f3:=bak; plus(f3,f1,f2^); end; write(f31:4); for i:=f32-1 downto 1 do begin if f33<10 then write(‘000’) else if f34<100 then write(‘00’) else if f35<1000 then write(‘0’); write(f36); if (f37-i+1)mod 10=0 then writeln; end; close(input);close(output); end. 
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

fib.in中给出的数据规模是100000。我们分别编译并测出两个程序的运行时间。

[bash highlight="10,23"]
jeff@ubuntu:~/test/fib$ fpc fib1.pas && time ./fib1
Free Pascal Compiler version 2.4.0-2ubuntu3.1 [2011/06/17] for x86_64
Copyright (c) 1993-2009 by Florian Klaempfl
Target OS: Linux for x86-64
Compiling fib1.pas
Linking fib1
/usr/bin/ld: warning: link.res contains output sections; did you forget -T?
43 lines compiled, 0.2 sec

real  0m16.237s
user   0m16.190s
sys    0m0.010s

jeff@ubuntu:~/test/fib$ fpc fib2.pas && time ./fib2
Free Pascal Compiler version 2.4.0-2ubuntu3.1 [2011/06/17] for x86_64
Copyright (c) 1993-2009 by Florian Klaempfl
Target OS: Linux for x86-64
Compiling fib2.pas
Linking fib2
/usr/bin/ld: warning: link.res contains output sections; did you forget -T?
47 lines compiled, 0.1 sec

real  0m15.506s
user   0m15.490s
sys    0m0.000s

可以看出，用指针的程序快了近1s。而当MAXLEN上升到10000，数据规模上升到150000时，这个时间差达到了2s。可见这中间的差距。

不过，对于OI来说，一个程序允许的时间一般是1s，在这1s中，两者的差距很难体现。当MAXLEN=1400，N=25000时，两者的时间分别为0m0.994s,0m0.972s。差距不大。因此在OI中使用指针来加速数组复制并不能取得很好的效果，除非数组元素非常多、复制次数也很多。OI要优化算法，还是应该从算法本身考虑（比如换用通项公式），这种常量级的优化只有在大量数据的基础上才有明显效果。但如果编程时间足够，思路清晰，可以试着使用此方法。

  1. f31↩

  2. 0↩

  3. i↩

  4. i↩

  5. i↩

  6. i↩

  7. 0↩

Comments