最近上演算法学到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/cn.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