[問題] Networkx的並查集套件(UnionFind)
最近上演算法學到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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.121.3 (臺灣)
※ 文章網址: https://www.ptt.cc/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
→
10/04 13:21,
4年前
, 1F
10/04 13:21, 1F
→
10/04 13:22,
4年前
, 2F
10/04 13:22, 2F
Python 近期熱門文章
PTT數位生活區 即時熱門文章
