[問題] 產生過多的冗餘組合

看板C_and_CPP (C/C++)作者willyhsu (wi)時間15年前 (2011/03/22 21:39)推噓2(2推 0噓 2→)

留言4則, 2人參與討論串1/1

開發平台(Platform): (Ex: VC++, GCC, Linux, ...) Code::Block 8.02 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 問題(Question)： 3/24更新之前曾在板上問過，計算交易出現次數的問題。當時測的時候是只用少數幾種屬性，結果都正確。現在改測交易屬性多一些時就會莫名奇妙的當掉，或是跑超級無敵久。因為程式要處理的交易數量會超過10萬筆以上，交易的屬性也會超過1000，所以現在不知道該怎麼做才好.. 好像原因是出在建樹、拜訪樹的過程花太多成本。目前建樹的方式並不是有效率的建樹方法，每一次建樹都要從Root開始。 (我是用binary tree去模擬Prefix Tree) 因此，在建樹時或更新節點時，我都要重新的traverse到正確建樹的位置。 Blink 為兄弟關係 Dlink 為父子關係舉例來說：建樹的結點依序為{A}, {B}, {A,B}, {C}, {A,C}, {B,C}, {A,B,C} Root = null 欲建立{A}時，先找Root，Root=null，create A，Root 指向A。 Root -> A 接著建{B}時，B > A，所以往Blink走，建在A的下面。 Root -> A \ (Blink) B 欲建立{A,B}時，又重新先走了A(visit())，再走B(update())，再建立AB。 Root -> A (Dlink) / \ B B 因此A的部分會被重複多走了一遍。(我都是從Root開始走) 建立{C}時建立{AC}時還是先visit A再建C Root-> A Root-> A / \ / \ B B B B \ \ \ C C C 接著{B,C}時也是從Root A 先visit B 再建C Root-> A / \ B B \ / \ C C C 最後{A,B,C} Root-> A / \ B B / \ / \ C C C C 餵入的資料(Input)： test.dat.log 共20筆交易(第一筆為0 1 3 4 7 8第二筆2 8…) http://codepad.org/et81tm1r 預期的正確結果(Expected Output)：將Input的data所有的組合正確產生以及計算出現次數錯誤結果(Wrong Output)： Process returned -1073741819 (0xC0000005) execution time : 120.359 s (當attributes超過20後就會跑不太出來?) 程式碼(Code)：(請善用置底文網頁, 記得排版) http://codepad.org/ywzkF8G1 補充說明(Supplement)： 489行將test.dat.log資料讀進來後，以屬性去產生排列組合以計算出現次數。 496行 - 排列組合方式是採用#1DV9kDDa 的產生方式 (超集集合產生前要確定所有子集都產生) 360-420 為排列組合 355行將產生的組合建成結構自已的想法與試的結果：除了樹的更新建立這邊問題之外，原本在425行 run() , run2(), recur() function會將所有屬性去做遞迴產生所有組合，但是會產生很多不必要的集合。比方屬性0根本沒出現，就不需要考慮產生含0的超集如 01, 02, 03..。因此，在buffer將資料讀進來時，就用array去算每個屬性i累計出現的次數(Heap[i]) 427行 – 將出現次數低於0次也就是Heap[i]低於0就排除，不去產生跟i有關的排列組合，但是在run2 function的遞迴還是會產生不必要的集合 = =.. 目前修改後的版本是利用一個newA陣列只將高於threshold的項目存下來。所以可以減少產生一些陣列，似乎有快一點。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.120.14.204