skyli
C++之夢

隨筆 - 62 文章 - 96 trackbacks - 0

2006年4月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

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

1

2

3

4

5

6

常用鏈接

留言簿(7)

隨筆分類(66)

隨筆檔案(62)

文章分類(31)

文章檔案(32)

友情鏈接

校內網

積分與排名

積分 - 237257
排名 - 108

閱讀排行榜

評論排行榜

一道算法題引發的動態內存管理的思考

在做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;