Re: [問題] 不固定子個數的Tree
看板C_and_CPP (C/C++)作者karaokstar (卡拉歐科史達)時間13年前 (2013/02/05 15:11)推噓0(0推 0噓 9→)留言9則, 3人參與討論串2/2 (看更多)
※ 引述《karaokstar (卡拉歐科史達)》之銘言：
: 開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
: Microsoft Visual Studio 2010
: 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
: #include<vector>
: 問題(Question)：
: 大家好,
: 小弟現在想要實作一個每個節點無固定個數子的樹
: 想法是這樣的話class Node的結構裡面必須要有個可以動態成長連結child的pointer
: vector<Node> *children, 一個pointer指向一個vector, vector儲存Node
: vector<Node*> children, 這Node本身有一個Vector, 裡面存放著pointer to Node
: 想請問一下這兩種實作上哪種比較好，或者說比較符合我的需求
: 還是說有更好的實作方法可以提示一下, 因為我只有想到這兩種
: 小弟想要實作出的樹狀結構如右圖 http://ppt.cc/BHrX
: 謝謝大家!
: 餵入的資料(Input)：
: 預期的正確結果(Expected Output)：
: 錯誤結果(Wrong Output)：
: 程式碼(Code)：(請善用置底文網頁, 記得排版)
: 補充說明(Supplement)：
大家好,
小弟後來我有實作出來這個Tree, 但是效率與預期的差很多
這棵樹的資料結構和演算法我是照著paper上的敘述來作的
但實驗數據用類似的測資時間卻差很多, 一個100000筆的測資, paper的數據是100秒內
我的程式卻要跑10000多秒, 原因的話我想可能是我implement出來的程式效率太差
因為測資雖然不是完全一樣但類似, 然後CPU和RAM差異也不大
主要在建tree的時候都是會call到class tree內的insert function
我想瓶頸可能也是卡在這
http://ideone.com/GiiSap insert function
http://ideone.com/lzDtgQ class Node and class tree
因為整個程式碼貼上來可能幫助不大, 所以我先貼insert的function以及資料結構的部分
我要insert的資料長相大概是像
item : value
1 : 0.5
2 : 0.3
不知道這樣的資訊是否足夠，如果不夠我可能再把整份code貼上來
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.213
→
02/05 15:30, , 1F
02/05 15:30, 1F
→
02/05 15:30, , 2F
02/05 15:30, 2F
是用Debug/Win32 Build出來的.exe 然後在cmd底下吃三個參數跑
>a.exe database.txt profit.txt 0.1
類似上面這樣執行
※ 編輯: karaokstar 來自: 140.112.28.213 (02/05 15:37)
→
02/05 15:40, , 3F
02/05 15:40, 3F
用同個數據跑
Release mode: build tree cost 30.5 sec, total cost 695.812 sec
Debug mode: build tree cost 262.515 sec, total cost 301.656 sec
在建tree的時候Release mode快很多, 但是建完之後的處理是
對於item的某個值只要超過門檻, 就建item的conditional tree
我是會call recursive的function, 不知道為何會在後面步驟release比debug花時間
※ 編輯: karaokstar 來自: 140.112.28.213 (02/05 16:38)
Visual Studio 我動到最佳化的設定
結果現在跑的exe檔都無法出現正確答案, 不知道怎麼辦 囧
※ 編輯: karaokstar 來自: 140.112.28.213 (02/05 17:03)
→
02/05 17:02, , 4F
02/05 17:02, 4F
→
02/05 17:03, , 5F
02/05 17:03, 5F
→
02/05 17:03, , 6F
02/05 17:03, 6F
→
02/05 17:07, , 7F
02/05 17:07, 7F
剛剛以為動到最佳化設定有出問題, 結果是Build Release剛好把其中一行註解掉
耍白癡了.
不過還是不知道為何在最後步驟反而release mode會比debug mode還來得慢
至於變數初始值應該都沒問題
※ 編輯: karaokstar 來自: 140.112.28.213 (02/05 17:12)
不過好消息是, 原本Debug mode要跑10000多秒的測資+參數
Release mode total cost 只要622.109秒
前面的數據是我用比較高的門檻值, 需要花費的時間會比較少, 想說先比較看看
正常來說Release mode會跑比較快是因為有最佳化嗎 ?
會不會因為程式的特性導致程式的某些地方最佳化後反而會跑得比原本慢
但大部分還是比原本快 ?
※ 編輯: karaokstar 來自: 140.112.28.213 (02/05 17:37)
→
02/05 18:53, , 8F
02/05 18:53, 8F
→
02/05 18:54, , 9F
02/05 18:54, 9F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
