三つの木を巡る方法
37754 ワード
ツリーの概念は開発において重要な部分であり、xmlのドキュメントオブジェクトモデル(DOM)はツリーであり、フォルダファイルの構造もツリーである.木を遍歴するのは開発の中でいつも出会う1つの問題で、例えば、DOMの中のimgタグの個数を探して、1株のDOM木を遍歴します.ファイルがあるかどうかを調べるためには、このディレクトリを巡回する必要があります.ここでは、ファイルを巡回することを例にとって、ツリーを巡回する3つの基本的な方法を説明します.再帰的深さ優先アルゴリズム、非再帰的深さ優先アルゴリズム、非再帰的広さ優先アルゴリズムです. これらのアルゴリズムはプロジェクトの中でよく繰り返されるアルゴリズムです.プログラムを書いて以来、私が作ったほとんどのアルゴリズムは大学二年生のデータ構造を使っています.時には、アルゴリズムをいくつか変えただけで、いくつかのアルゴリズムを統合しただけです.おそらくこれはデータ構造のこの本のような重要な原因です.コードを先に見ます
----------------Test run for rec_リスト.files()…Finished:1868 files
Max memory for rec_リスト.files():496.93 kbytes Running time for rec_リスト.files():9.231678 s-----------------------
Test run for deep_first_リスト.files()…Finished:1868 files
Max memory for deep_first_リスト.files():432.41 kbytes Running time for deep_first_リスト.files():3.940216 s-----------------------
Test run for breeadth_first_files()…Finished:1868 files
Max memory for bredth_first_files():432.55 kbytes Running time for bredth_first_files():3.749125 s
第二の方法と第三の方法の効率とメモリの消耗はあまり違いませんが、第一の再帰的な呼び出しによって消費されるメモリと時間は大きくなります.
本文はCSDNブログから来ました.転載は出所を明記してください.http://blog.csdn.net/niniwzw/archive/2008/06/28/2594877.aspx.
1
define
(
'
DS
'
,
DIRECTORY_SEPARATOR);
2
function
rec_list_files(
$from
=
'
.
'
) {
3
if
(
!
is_dir
(
$from
)) {
4
return
array
();
5
}
6
$files
=
array
();
7
if
(
$dh
=
opendir
(
$from
)) {
8
while
(
false
!==
(
$file
=
readdir
(
$dh
))) {
9
if
(
$file
==
'
.
'
||
$file
==
'
..
'
) {
10
continue
;
11
}
12
$path
=
$from
.
DS
.
$file
;
13
if
(
is_file
(
$path
)) {
14
$files
[]
=
$path
;
15
}
16
$files
=
array_merge
(
$files
,
rec_list_files(
$path
));
17
}
18
closedir
(
$dh
);
19
}
20
return
$files
;
21
}
22
23
function
deep_first_list_files(
$from
=
'
.
'
) {
24
if
(
!
is_dir
(
$from
)) {
25
return
false
;
26
}
27
$files
=
array
();
28
$dirs
=
array
(
$from
);
29
while
(
NULL
!==
(
$dir
=
array_pop
(
$dirs
))) {
30
if
(
$dh
=
opendir
(
$dir
)) {
31
while
(
false
!==
(
$file
=
readdir
(
$dh
))) {
32
if
(
$file
==
'
.
'
||
$file
==
'
..
'
) {
33
continue
;
34
}
35
$path
=
$dir
.
DS
.
$file
;
36
if
(
is_dir
(
$path
)) {
37
$dirs
[]
=
$path
;
38
}
else
{
39
$files
[]
=
$path
;
40
}
41
}
42
closedir
(
$dh
);
43
}
44
}
45
return
$files
;
46
}
47
48
function
breadth_first_files(
$from
=
'
.
'
) {
49
$queue
=
array
(
rtrim
(
$from
,
DS)
.
DS);
//
normalize all paths
50
$files
=
array
();
51
while
(
$base
=
array_shift
(
$queue
)) {
52
if
((
$handle
=
opendir
(
$base
))) {
53
while
((
$child
=
readdir
(
$handle
))
!==
false
) {
54
if
(
$child
==
'
.
'
||
$child
==
'
..
'
) {
55
continue
;
56
}
57
if
(
is_dir
(
$base
.
$child
)) {
58
$combined_path
=
$base
.
$child
.
DS;
59
array_push
(
$queue
,
$combined_path
);
60
}
else
{
61
$files
[]
=
$base
.
$child
;
62
}
63
}
64
closedir
(
$handle
);
65
}
//
else unable to open directory => NEXT CHILD
66
}
67
return
$files
;
//
end of tree, file not found
68
}
69
70
function
profile(
$func
,
$trydir
) {
71
$mem1
=
memory_get_usage();
72
echo
'
<pre>----------------------- Test run for
'
.
$func
.
'
()
'
;
73
flush
();
74
$time_start
=
microtime
(
true
);
75
$list
=
$func
(
$trydir
);
//
print_r($list);
76
$time
=
microtime
(
true
)
-
$time_start
;
77
echo
'
Finished :
'
.
count
(
$list
)
.
'
files</pre>
'
;
78
$mem2
=
memory_get_peak_usage();
79
printf
(
'
<pre>Max memory for
'
.
$func
.
'
() : %0.2f kbytes Running time for
'
.
$func
.
'
() : %0.f s</pre>
'
,
(
$mem2
-
$mem1
)
/
1024.0
,
$time
);
80
return
$list
;
81
}
82
83
profile(
'
rec_list_files
'
,
"
D:\www\server
"
);
84
profile(
'
deep_first_list_files
'
,
"
D:\www\server
"
);
85
profile(
'
breadth_first_files
'
,
"
D:\www\server
"
);
86
87
----------------Test run for rec_リスト.files()…Finished:1868 files
Max memory for rec_リスト.files():496.93 kbytes Running time for rec_リスト.files():9.231678 s-----------------------
Test run for deep_first_リスト.files()…Finished:1868 files
Max memory for deep_first_リスト.files():432.41 kbytes Running time for deep_first_リスト.files():3.940216 s-----------------------
Test run for breeadth_first_files()…Finished:1868 files
Max memory for bredth_first_files():432.55 kbytes Running time for bredth_first_files():3.749125 s
第二の方法と第三の方法の効率とメモリの消耗はあまり違いませんが、第一の再帰的な呼び出しによって消費されるメモリと時間は大きくなります.
本文はCSDNブログから来ました.転載は出所を明記してください.http://blog.csdn.net/niniwzw/archive/2008/06/28/2594877.aspx.