在为Python中的机器学习算法编写功能选择器时,我生成了一个包含以下代码的数据结构:
# Perform set partitioning on the results
groups = []
for t in results:
(jthName,kthName) = t
jthGroup = -1
kthGroup = -1
# Just a simple list of hashes with online merging
for idx,group in enumerate(groups):
if jthName in group:
jthGroup = idx
if kthName in group:
kthGroup = idx
if jthGroup == kthGroup:
if jthGroup == -1: # Implicit: "and kthGroup == -1"
groups.append(set((jthName,kthName)))
elif jthGroup != kthGroup:
if kthGroup == -1:
# Merge kthName into jthGroup
groups[jthGroup].add(kthName)
elif jthGroup == -1:
# Merge jthName into kthGroup (redundant if naturally-ordered)
groups[kthGroup].add(jthName)
else:
# Merge jthGroup and kthGroup, since we have a connecting pair
merged = set()
merged.update(groups[jthGroup])
merged.update(groups[kthGroup])
groups.remove(groups[jthGroup])
groups.remove(groups[kthGroup])
groups.append(merged)
其中,我的输入results
是元组{2}的列表,groups
是集合的列表。请注意,我的代码在这里并不一定有效;它仅用于说明目的。在
我的数据结构groups
具有以下属性:
对于每个(jthName,kthName)
:
(jthName,kthName)
元素,请在集合列表中创建{(jthName,kthName)
中的一个,请将未找到的元素合并到该集合中。在(jthName,kthName)
的每个元素都在不同的集合中找到,则将两个被引用的集合合并为一个集合。在循环不变量:jthName
和{
我对这种数据结构的理由是创建一组未知的连接节点图的平面分解,其中每个唯一的元素名是一个节点,每个唯一的对是一个边。我的基本原理是我的图是不完整的,我要求这个视图只选择每个图的已知成员,将其输入到一个算法中,该算法将regressively determine图的连通性和边的方向性(即,由数据表示的DAGs的完整集合)。但是,我离题了。在
变量groups
表示的数据结构是否有友好名称?如果是,或者不是,是否有更节省时间或空间的方法来执行这种分解?在
我想你要找的是一种叫做Disjoint-set data structure的东西。在
在执行Kruskal时经常使用它,因为如果您使用路径压缩实现不相交的set数据结构,它允许您在摊余nlog*n(实际上少于这个时间)内进行n次查找。在
这是相当合理的实现,我认为wiki页面伪代码很适合python。如果您需要更多帮助,this SO question might help。在
如果使用不相交的集合数据结构,则代码如下所示:
相关问题 更多 >
编程相关推荐