以动态pythonic方式查找部分有序集中的最小元素
假设Os是一个部分有序的集合,并且在Os中给出任意两个对象O1和O2,如果O1大于O2,则F(O1,O2)将返回1,如果O1小于O2则返回-1,如果它们是无比的则为2,如果O1等于O2则为0。
我需要找到元素的子集Mn是最小的Os。对于Mn中的每个A,对于Os中的每个B,F(A,B)永远不等于1。
这并不难,但我确信它可以用更加pythonic的方式完成。
快速而肮脏的方式是:
def GetMinOs(Os):
Mn=set([])
NotMn=set([])
for O1 in Os:
for O2 in Os:
rel=f(O1,O2)
if rel==1: NotMn|=set([O1])
elif rel==-1: NotMn|=set([O2])
Mn=Os-NotMn
return Mn
特别是我对我基本上经历所有元素N ^ 2次的事实感到不满意。我想知道是否会有一种动态的方式。
通过“动态”我并不仅仅意味着快速,而且一旦被发现某事物是最不可能的,也许它可以被取消。并以pythonic,优雅的方式完成所有这些
没有找到相关结果
已邀请:
1 个回复
量华
,“动态”删除已知非最小的元素。它使用一个列表
,它以
的所有元素开头。 “指针”索引
指向列表"2ѭ的“结束”。当找到非最小元素时,其位置与
中的值交换,指针
递减,因此收缩effective2ѭ的有效长度。 这样做会删除非最小元素,因此不要再次检查它们。
假设
具有比较函数的正常属性:传递性,交换性等。 在下面的测试代码中,以梦想的
,我的timeit运行显示速度提高了54倍:
时间结果是:
PS。请注意:我没有彻底检查GetMinOs2中的算法,但我认为一般的想法是正确的。我在脚本的末尾进行了一些测试,显示它至少在样本数据上起作用
。