程序下面给出了一个 BFS C 程序（其中子节点列表为连续内存形式）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| /*BFS sub routine*/
bool printtree(NODE* node, int target, int level) {
int i;
bool returnval=false;
if (target > level) {
for(i=0;i<CCOUNT;i++) if(printtree(node->child+i,target,level+1) ) returnval=true;
}
else {
printf("%c",(node->data));
if(node->child != NULL) returnval=true;
}
return returnval;
}
/*BFS routine*/
void printbfstree(NODE* root) {
if(root == NULL) return;
int target=0;
while(printtree(root,target++,0)) {
printf("\n");
}
}
|
实验数据 使用 -DSPACEDATA 选项提供编译空间数据，使用 -DTIMEDATA 选项提供编译时间数据，使用 -DLPRINT 编译行打印，使用 -DNOPRINT 则不打印数据。 请注意：‘---------------’ 行之间的行是命令和它生成的输出。
子节点级别数为 7 且树深度为 3 的两种类型的正常打印1
2
3
4
5
6
7
8
9
| ---------------
>a.out -l3 -c7
queue based, allocated for queue size 50 ,each node size 4 bytes
printing queue based
a0123456ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG
printing stack based
a0123456ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG
printing done
---------------
|
打印基于堆栈的 BFS 方法的逐行输出1
2
3
4
5
6
7
8
9
10
11
12
| ----------------
>gcc -DLPRINT -lm stackbasedBFS.c
>./a.out -l3 -c7
queue based, allocated for queue size 50 ,each node size 4 bytes
printing queue based
a0123456ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG
printing stack based
a
0123456
ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG
printing done
----------------
|
打印空间数据和时间数据1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| ---------------
>./a.out -l5 -c2
queue based, allocated for queue size 17 ,each node size 4 bytes
printing queue based
a01ABABabababab0101010101010101
queue based, queue usage size 16
diff time 0 sec 26 micro
printing stack based
a01ABABabababab0101010101010101
stack used 128
diff time 0 sec 14 micro
printing done
---------------
|
空间和时间分析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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| --------------
> cc -DNOPRINT -DSPACEDATA -DTIMEDATA -lm stackbasedBFS.c
> ./a.out -l10 -c10
queue based, allocated for queue size 1000000001 ,each node size 4 bytes
> ./a.out -l10 -c9
queue based, allocated for queue size 387420490 ,each node size 4 bytes
printing queue based
Segmentation fault
> ./a.out -l9 -c10
queue based, allocated for queue size 100000001 ,each node size 4 bytes
printing queue based
queue based, queue usage size 100000000
diff time 28 sec 490083 micro
printing stack based
stack used 256
diff time 1 sec 469060 micro
printing done
> ./a.out -l5 -c10
queue based, allocated for queue size 10001 ,each node size 4 bytes
printing queue based
queue based, queue usage size 10000
diff time 0 sec 2891 micro
printing stack based
stack used 128
diff time 0 sec 164 micro
printing done
> ./a.out -l10 -c7
queue based, allocated for queue size 40353608 ,each node size 4 bytes
printing queue based
queue based, queue usage size 40353607
diff time 11 sec 874163 micro
printing stack based
stack used 288
diff time 0 sec 788580 micro
printing done
> ./a.out -l20 -c2
queue based, allocated for queue size 524289 ,each node size 4 bytes
printing queue based
queue based, queue usage size 524288
diff time 0 sec 333929 micro
printing stack based
stack used 608
diff time 0 sec 40476 micro
printing done
> ./a.out -l25 -c2
queue based, allocated for queue size 16777217 ,each node size 4 bytes
printing queue based
queue based, queue usage size 16777216
diff time 10 sec 635081 micro
printing stack based
stack used 768
diff time 1 sec 482634 micro
printing done
> ./a.out -l30 -c2
queue based, allocated for queue size 536870913 ,each node size 4 bytes
allocation failed, exiting
> ./a.out -l28 -c2
queue based, allocated for queue size 134217729 ,each node size 4 bytes
allocation failed, exiting
> ./a.out -l27 -c2
queue based, allocated for queue size 67108865 ,each node size 4 bytes
printing queue based
queue based, queue usage size 67108864
diff time 43 sec 22479 micro
printing stack based
stack used 832
diff time 5 sec 773319 micro
printing done
-----------------
|
在空间分析中，我们可考虑最糟糕的场景，也就是 9 级和 10 个子节点。这里，基于队列的方法所使用的节点数量为 100,000,000，如果每个节点 4 个字节，累计内存大小为 100000000*4=400 MB(arr)。基于堆栈的方法使用的内存为 256 字节。在此程序中，它仅计算 8 级，而不是 9 级。对于 9 级，合计为 (9/8)*256=288，也就是每级 288/9=32 字节。在下一节中，我们将证明理想情况下这一数据为 20 字节（其中没有局部变量）。
在时间分析中，我们可考虑最糟的场景，也就是 27 级和 2 个子节点。基于队列的方法花费的时间为 42 秒和 22,479 微秒。基于堆栈的方法花费的时间为 5 秒和 773,319 微秒。
在这里，我们将讨论一下树的每个级别所用的 32 字节。
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| ----------------
> gdb
GNU gdb 6.3
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB. Type "show warranty" for details.
This GDB was configured as "i686-pc-linux-gnu".
(gdb) file a.out
Reading symbols from /home/pravinsi/a.out...done.
Using host libthread_db library "/lib/tls/libthread_db.so.1".
(gdb) b printtree
Breakpoint 1 at 0x8048802: file stackbasedBFS.c, line 79.
(gdb) run
Starting program: /home/pravinsi/a.out
queue based, allocated for queue size 50 ,each node size 4 bytes
printing queue based
a0123456ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG
queue based, queue usage size 49
diff time 0 sec 82 micro
printing stack based
Breakpoint 1, printtree (node=0x804b008, target=0, level=0) at stackbasedBFS.c:79
79 __asm__("movl %%ebp, %0;" : "=r" ( i));
(gdb) c
Continuing.
Breakpoint 1, printtree (node=0x804b008, target=1, level=0) at stackbasedBFS.c:79
79 __asm__("movl %%ebp, %0;" : "=r" ( i));
(gdb) bt
#0 printtree (node=0x804b008, target=1, level=0) at stackbasedBFS.c:79
#1 0x080488d6 in printbfstree (root=0x804b008) at stackbasedBFS.c:99
#2 0x08048f51 in main (argc=1, argv=0xbffff894) at stackbasedBFS.c:216
(gdb) c
Continuing.
Breakpoint 1, printtree (node=0x804b018, target=1, level=1) at stackbasedBFS.c:79
79 __asm__("movl %%ebp, %0;" : "=r" ( i));
(gdb) bt
#0 printtree (node=0x804b018, target=1, level=1) at stackbasedBFS.c:79
#1 0x0804886c in printtree (node=0x804b008, target=1, level=0) at stackbasedBFS.c:84
#2 0x080488d6 in printbfstree (root=0x804b008) at stackbasedBFS.c:99
#3 0x08048f51 in main (argc=1, argv=0xbffff894) at stackbasedBFS.c:216
(gdb) f 1
#1 0x0804886c in printtree (node=0x804b008, target=1, level=0) at stackbasedBFS.c:84
84 for(i=0;i<CCOUNT;i++) if(printtree(node->child+i,target,level+1) ) returnval=true;
(gdb) info reg ebp
ebp 0xbffff7a8 0xbffff7a8
(gdb) f 0
#0 printtree (node=0x804b018, target=1, level=1) at stackbasedBFS.c:79
79 __asm__("movl %%ebp, %0;" : "=r" ( i));
(gdb) info reg ebp
ebp 0xbffff788 0xbffff788
(gdb) x/10x 0xbffff788
0xbffff788: 0xbffff7a8 0x0804886c 0x0804b018 0x00000001
0xbffff798: 0x00000001 0x08048d5b 0x000490cf 0x00000000
0xbffff7a8: 0xbffff7c8 0x080488d6
(gdb) x 0x0804886c
0x804886c <printtree+112>: 0x8410c483
(gdb) x 0x08048d5b
0x8048d5b <BFS+413>: 0xc910c483
-----------------
|
可以看到，两个连续基址指针（也就是 0xbffff7a8 和 0xbffff788）之间的内存区域为：
1
2
3
| 0xbffff788: 0xbffff7a8 0x0804886c 0x0804b018 0x00000001
0xbffff798: 0x00000001 0x08048d5b 0x000490cf 0x00000000
0xbffff7a8: 0xbffff7c8
|
一个基址指针 (0xbffff7a8) 与下一个基址指针 (0xbffff788) 之间相差 32 字节。其中两个是局部变量 0x00000000('i') 和 0x000490cf('returnval')，一个是缓存的数据 0x08048d5b。如果我们删除实现细节，仅查看一般内存使用，那么结果为每个级别 8-3=5. 5*4=20 字节。 |
