一道算法题引发的动态内存管理的思考 - skyli

友情链接

最新评论

1. re: 优先队列用法
评论内容较长,点击标题查看
--tanti
2. re: 优先队列用法
给力！！
--***
3. re: pow函数的性能测试
Pow 函数要处理各种非整数次幂情况，比如0.5就等于开根号了，0.2就等于开5次方了。当然比直接乘慢的多。
--YYX
4. re: istringstream用法[未登录]
@gong
cin是标准输入，在std中已经声明了。
--mm
5. re: istringstream用法[未登录]
您好，为什么这里的getline(cin, line）中的cin没有定义就直接使用了呢？
--gong

阅读排行榜

评论排行榜

一道算法题引发的动态内存管理的思考

在做PKU2762时，需要建邻接表。
于是按部就班写了下面一个插入边到邻接表中的函数：

const int VMAX = 1010;

typedef struct Graph

{

int vex;

Graph* next;

}Graph;

Graph ArcGraph[VMAX];

void insert(int u, int v)

{

Graph* t = new Graph;

Graph* p = ArcGraph[u].next;

t->vex = v;

t->next = p;

ArcGraph[u].next = t;

}

完成完整的程序提交上去，得到结果
Memory:25796K Time:375MS
Language:C++ Result:Accepted

再对比别人的程序
Memory:296K Time:109MS

无论是时间还是空间都相差很大。
于是就考虑怎么优化自己的程序。
第一个问题：规模只有1000，为什么会用那么多内存呢？
仔细一想数据是多case的，每次插入新节点时都要动态创建一个节点。
一来动态创建耗时间，二来每个case结束的邻接表中的节点没有释放，故耗费大量内存。
然后就想到了下面的算法，首先初始化一块内存Graph use[100*VMAX];这样每次需要新节点时，
就从use中获取。如果use使用完毕就再动态创建。

依此算法优化后，得到的结果比较满意
Memory:1000K Time:218MS
Language:C++ Result:Accepted

const int VMAX = 1010;

typedef struct Graph

{

int vex;

Graph* next;

}Graph;

Graph ArcGraph[VMAX];

Graph use[100*VMAX];

int size = 0;

void insert(int u, int v)

{

Graph* t;

if(size < 100*VMAX)

{

t = &use[size];

size++;

}

else t = new Graph;

Graph* p = ArcGraph[u].next;

t->vex = v;

t->next = p;

ArcGraph[u].next = t;

}

posted on 2007-08-13 00:29 beyonlin 阅读(1424) 评论(0) 编辑收藏引用所属分类: acm之路、C++之路

常用链接

留言簿(7)

随笔分类(66)

随笔档案(62)

文章分类(31)

文章档案(32)

友情链接

最新随笔

积分与排名

最新评论

阅读排行榜

评论排行榜

只有注册用户登录后才能发表评论。


相关文章: pow函数的性能测试一道算法题引发的动态内存管理的思考筛法求素数字符串hash函数插入排序泛型算法最大匹配匈牙利算法最小生成树Prim算法 itoa函数归并排序求逆序数单源最短路径Dijkstra算法

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理