程序优化技巧

大榕树 \ Pascal语言 \ 算法与技巧

程序优化技巧

原文链接：http://www.mydrs.org/program/list.asp?id=101
1 时间优化[/b]
很大的课题啊！我在这里抛砖引玉了，呵呵。
我只准备讲时间优化和空间优化，其他的就...
1.时间优化
本来有三个方面：
a.数据结构优化
b.算法优化
c.编码优化
d.空间换时间
因为a我将在数据结构的选择这一部分较详细的描述，b我将在剪枝这一部分作一个讨论，
这里我只是讲第三种，针对的是PASCAL语言
1.快速操作。
有：inc,dec,include,exclude。大家可以看看TP的HELP
2.赋值的问题
假设：
s:shortint;
i:integer;
l:longint;
以下语句执行10^8次。
l:=s; 3.46s
i:=s; 2.80s
s:=s; 2.42s
l:=i; 3.19s
i:=i; 2.42s
l:=l; 2.91s
l:=s比l:=l还要慢...
记住一句话：不要做没用的事，不要做重复的事。看起来简单，但以后你们会体会到它的作用。
介绍一篇英文文章(PDF)：Optimization
[b]2 空间优化
这里我们简单的讨论一下空间优化。
1)充分的利用空间
2)只储存必要的信息
3)时间换空间
[例子1]
时间换空间的例子：
NOI98第一题《个人所得税》,测试数据很大，一次读完根本不可能，就需要
多次读文件，一次处理5000个人（或1个月的数据）
[例子2]
数据结构的例子：
对于二元坐标，如果0<=x<=10, 0<=y<=10,就储存成一个数z,
x=z div 11; y=z div 11;
这样：一个坐标数据的大小就减少了一半。
[例子3]
指针占4个字节，所以链表的开销实际上很大，如果把指针改成索引就...
NOI2000的《单词查找树》就可以这么做。

作者：SRbGa
来源：OIBH
时间：2001-07-07

上一篇：程序测试技巧
下一篇：基本程序结构和几个概念