python – 这个数据结构有一个友好的名称吗?
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – 这个数据结构有一个友好的名称吗?,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2141字,纯文字阅读大概需要4分钟。
内容图文
![python – 这个数据结构有一个友好的名称吗?](/upload/InfoBanner/zyjiaocheng/802/367c58d372e742fb849623f8405dd23e.jpg)
在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)
我的输入结果是元组{2}的列表,而组是列表.请注意,我的代码在这里不一定有效;它仅用于说明目的.
我的数据结构group具有以下属性:
>对于每个(jthName,kthName):
>如果在任何包含的集合中都找不到(jthName,kthName)的元素,则在集合列表中创建set((jthName,kthName)).
>如果在一个包含的集合中找到(jthName,kthName)中的一个,则将unfound元素合并到该集合中.
>如果(jthName,kthName)的每个元素都在另一个集合中找到,则将两个引用的集合并为一个集合.
>循环不变量:jthName和kthName不能包含在多个集合中.
我对这种数据结构的理由是创建一组未知连通节点图的平面分解,其中每个唯一元素名称是一个节点,每个唯一对是一个边.我的理由是我的图表不完整,我要求这个视图只选择每个图形的已知成员,以提供一个算法,该算法将regressively determine图形连通性和边缘的方向性(即DAGs表示的完整集合)数据).但是,我离题了.
变量组表示的数据结构是否有友好名称?如果是,或者如果没有,是否有更多时间或空间效率的方法来执行此分解?
解决方法:
我认为你所寻找的东西叫做Disjoint-set data structure.
它经常在做Kruskal时使用,因为如果你用路径压缩实现不相交的数据结构,它允许你在分摊的nlog * n(实际上小于那个)时间内进行n次查找.
这是非常合理的实现,我认为维基页面伪代码非常适合python.如果您需要更多帮助,this SO question might help.
如果您使用了不相交的数据结构,那么您的代码将如下所示:
for t in results:
(jName, kName) = t
union(jName, kName)
内容总结
以上是互联网集市为您收集整理的python – 这个数据结构有一个友好的名称吗?全部内容,希望文章能够帮你解决python – 这个数据结构有一个友好的名称吗?所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。