PTT數位生活區 / C_and_CPP (C/C++)

[問題] 檔案深度搜尋 BFS / DFS

看板C_and_CPP (C/C++)作者 (閉上眼的魚)時間13年前 (2012/11/02 15:37), 編輯推噓3(3推 0噓 28→)
留言31則, 7人參與, 最新討論串1/1
檔案搜尋這問題有點老了，只是 聽說 通常 BFS 效率較 DFS 為佳， (有誤的話請指正)，故拿來做 DFS / BFS 練習與比較。 練習中有另外一個衍生問題，請不吝指教。 ---------------- 衍生問題 : Macro Comment #define NO_OUTPUT #ifdef NO_OUTPUT #define printf // #define puts // #endif 上面這段 code 是因在 travel 時方便切換是否要輸出， 但我 "印象" 在以前有點年代的 C 書籍裡面似乎有提到， 不能將一些函式 re-define 成 comment， 妙的是手邊 vc / gcc 都可以吃這種東西， 不知這個是否合法？ ---------------- 掃資料夾問題 先附上完整程式碼，http://codepad.org/SGj2ihfk 下面是概述流程，最後有提問( 效能上問題 ) DFS 上流程大概是 void DFS(const char * Path , const char * Filter) { char FullPath[MAX_PATH] ; /* sprintf(FullPath, "%s\\%s",Path,Filter); */ WIN32_FIND_DATA FileData; HANDLE hHandle = FindFirstFile(....); do{ /* sprintf(FullPath, "%s\\%s", Path, FileData.cFileName); 輸出 FileData.cFileName 若 FileData 是資料夾，且非 "." ".." 則進行 DFS(FullPath, Filter) */ }while(FindNextFile(....)); FindClose(hHandle); } BFS 小弟寫的流程大概如下 void BFS(const char* Path, const char* Filter) { char FullPath[MAX_PATH] ; /* sprintf(FullPath, "%s\\%s",Path,Filter */ WIN32_FIND_DATA FileData; HANDLE hHandle = FindFirstFile(....); char Folder[][MAX_PATH] ; /* 儲存 Path 底下之資料夾 */ do{ /* sprintf(FullPath, "%s\\%s", Path, FileData.cFileName); If ( IsFolder(FileData) ) FileData 加入 Folder; else 輸出 FullPath */ }while(FindNextFile(....)); for(i=0; i< FolderCnt; ++i) { 輸出 Folder[i] BFS(Folder, Filter) } FindClose(hHandle); } ------------- 為了測時，所以把輸出拿掉，避免 compiler opt 沒跑函式，所以沒加優化。 測試結果，BFS 反而較慢一點， 請問是否為我對 BFS / DFS 效能認知上有所誤失？ 還是我 BFS 根本是寫錯的？ 最後謝謝各位細心閱讀、耐心指導， 小弟感激不盡。 -- 就算把新鮮的肝拿回去，還是一樣寫碼到禿頭，加班到天亮。 你是不是想這麼做？是的話你就拿回去~ 拿啊！！ 九世宅男 : 下輩子不要再讓我幹工程師了 ~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.76.161
→
11/02 15:46, , 1F
看起來 DFS 和 BFS 好像反了？
11/02 15:46, 1F
→
11/02 15:49, , 2F
ret = printf(...); 編譯不過
11/02 15:49, 2F
→
11/02 15:50, , 3F
疑！有反嗎？DFS 不是找到路就鑽進去嗎？
11/02 15:50, 3F
→
11/02 15:50, , 4F
@@ 真的是寫反了.
11/02 15:50, 4F
→
11/02 15:52, , 5F
@linotwo:編譯不過指的是連結 code 沒過嗎？這裡很順 @@
11/02 15:52, 5F
→
11/02 15:53, , 6F
方便給個錯誤訊息嗎？謝謝。
11/02 15:53, 6F
→
11/02 15:55, , 7F
我看懂 linotwo 推文了,指的是 macro 那段, 謝謝提點 :)
11/02 15:55, 7F
→
11/02 16:04, , 8F
實測結果DFS 334，BFS 322
11/02 16:04, 8F
→
11/02 16:07, , 9F
#define printf // 跟 #define printf 是同樣意思
11/02 16:07, 9F
→
11/02 16:08, , 10F
另一筆測資DFS 1818，BFS 155 ，應該和測資有關
11/02 16:08, 10F
→
11/02 16:12, , 11F
@linotwo : 謝謝提點,我再想一下有沒有辦法做 NO_OUTPUT.
11/02 16:12, 11F
→
11/02 16:13, , 12F
@kiedeian : 謝謝您協助測試.解惑不少. :)
11/02 16:13, 12F
推
11/02 16:19, , 13F
preprocessor 不認識 printf 是函式，只有 compiler 才懂
11/02 16:19, 13F
一開始真的完全忽略它是函式所帶來之 slide effect .
→
11/02 16:25, , 14F
11/02 16:25, 14F
→
11/02 16:28, , 15F
要印出訊息的時候把 //#define DEBUG_MSG Uncomment 掉
11/02 16:28, 15F
→
11/02 16:28, , 16F
fclose(stdout); //不知道會不會有bug, orz...
11/02 16:28, 16F
fclose(stdout) 在這篇文章應沒出現，想請教是否是我漏看了？
推
11/02 16:57, , 17F
comment 那個改成 #define printf(...) 0 這樣應該可行
11/02 16:57, 17F
→
11/02 16:57, , 18F
preprocessor 會把 printf 連括號裡面一堆全部換成 0 這樣
11/02 16:57, 18F
→
11/02 16:58, , 19F
不過話說我在 VC 好像類似的手法行不通 (那時是要拿掉 cerr)
11/02 16:58, 19F
→
11/02 16:58, , 20F
後來是用 #define cerr /##/ 才搞定
11/02 16:58, 20F
→
11/02 16:59, , 21F
已經忘記當初是怎麼想到的這個 hack 了 XD
11/02 16:59, 21F
→
11/02 17:08, , 22F
char char *Path ...
11/02 17:08, 22F
已修正，謝謝指正。
→
11/02 17:57, , 23F
#define cerr /##/ 如果遇到 } 在同一行的話可能就不行了
11/02 17:57, 23F
感謝 LPH66、linotwo 給的建議，後來查一下網路，原來 macro 那段已不算小事， 再擴充下去大概會討論到 dprintf 吧，和原題意相差有點遠了， 或許再開主題做技術性的討論會較恰當。 另想請教的是 #define cerr /##/ 是什麼 ？？ 初步猜測 /##/ 最後相黏會變 // 吧？是用在 C++ 部份嗎？ cerr << "Hello, world!!" 謝謝各位熱心的賜教 ※ 編輯: EdisonX 來自: 180.177.76.161 (11/02 19:28)
→
11/02 19:57, , 24F
搞錯問題了…不要理我……
11/02 19:57, 24F
→
11/03 14:32, , 25F
#define printf(...) 0 // 這樣寫可以嗎?
11/03 14:32, 25F
推
11/06 00:18, , 26F
唔, 過了好幾天才想到來回...我那個是 C++ 在用的沒錯
11/06 00:18, 26F
→
11/06 00:18, , 27F
如同上面所言直接 #define xxx // 在 preprocessor 裡會先把
11/06 00:18, 27F
→
11/06 00:18, , 28F
// 拿掉 所以就只是 #define xxx 這樣而已 因此才用/##/
11/06 00:18, 28F
→
11/06 00:20, , 29F
讓 preprocessor 強迫把 cerr 代換成 // 兩個字再來處理
11/06 00:20, 29F
→
11/06 00:21, , 30F
所以要限制 debug 的東西全部要在同一行且沒有其他東西
11/06 00:21, 30F
→
11/06 00:46, , 31F
謝謝 LPH66 細心回答 *^_^*
11/06 00:46, 31F
‣ 更多 EdisonX 的文章
文章代碼(AID): #1GatXDkl (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 EdisonX 的文章
文章代碼(AID): #1GatXDkl (C_and_CPP)