最近上演算法學到union-find的資料結構 看到有這個現成套件可以使用 但發現有個問題。 union find結構主要就兩種操作：union和find find主要是cycle check使用 union會合併兩個不相交的集合 例如原本有[1,2,3] [4,5,6] 同時1為[1,2,3]的父節點，4為[4,5,6]的父節點，7為[7,8]的父節點 這時使用這個套件： union(1,5) 應該是要得到[1,2,3,4,5,6][7,8] 但實際得到的是：[1,2,3,4] [5,6][7,8] 再執行union(1,5)一次的話，會得到[1,2,3,4,5][6][7,8]這個結果 而且再做幾次union(1,5)都一樣。有點奇怪，但後面會講更怪的。 如果在初始狀態下： union(2,4) 也是應該得到[1,2,3,4,5,6][7,8] 但實際上會得到 [1,2,3,4] [5,6][7,8] 同樣的，不管執行相同指令幾次，都不會再改變 簡單說就是子孫去跟別人合併，父節點會先跑，而且會丟包他的子孫 但再執行一次相同指令，原本代表合併的子孫也會跑去合併， 然而其他子孫都會被丟包。 but, 就是這個but，如果其他的子孫之後再跟別人合併： 一樣從初始狀態執行union(2,4)後得到[1,2,3,4][5,6][7,8] 之後執行union(5,7)，這時5會'突然想到'他被丟包了，應該要去1那邊 變成[1,2,3,4,5,7][6][8] 7作為原本[7,8]的父節點，依然會丟包8。但同理之後如果8又跟別人合併，它還是會 想起他應該去1那邊。 官方documentation是說union()可以餵多個參數，但這樣等於我還是要手動loop ，一個個合併。 有人用過這個套件，可以分享一下該怎麼正確使用嗎？ Stanford U.在Coursera上的演算法課程，第三節第二週作業第二題 要實作hamming code的k-means clustering 作業的size是200000個node。github有人提供較小的test cases。 如果不處理上述問題的話，結果會是錯的，但5秒左右就有結果。 手動loop處理的話，根據github上size為16384個node的樣本，結果正確 但僅16384 nodes就需要跑兩分鐘，作業的20萬個節點要跑一天吧(我試跑2分鐘就放棄了 跟網路上說數秒的時間差太多了。 -- http://i.imgur.com/14uTDR7.jpg http://i.imgur.com/QYen80N.jpg http://i.imgur.com/IbG6oNJ.jpg http://i.imgur.com/LSp63St.jpg http://i.imgur.com/opW8stk.jpg http://i.imgur.com/T7XrJC2.jpg --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.121.3 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1601713521.A.0C9.html ※ 編輯: kiwistar (223.137.121.3 臺灣), 10/03/2020 16:27:20 ※ 編輯: kiwistar (223.137.121.3 臺灣), 10/03/2020 16:27:40