用动态pythonic方法寻找偏序集中的最小元素
用动态pythonic方法寻找偏序集中的最小元素
提问于 2010-11-07 13:13:53
假设Os是一个偏序集，给定Os中的任意两个对象O1和O2，如果O1大于O2，F( O1，O2)将返回1，如果O1小于O2，返回1，如果O1小于O2，则返回2，如果O1等于O2，则返回0。
我需要找到元素的子集Mn是最小的Os。对于Mn中的每个A和Os中的每个B，F(A，B)永远不等于1。
这是不难做到的，但我相信，这可以用一种更仿生的方式。
快速而肮脏的方式是：
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次。我想知道是否会有一种动态的方式。我所说的“动态”并不是指仅仅是快速，而是指一旦发现某物在最小程度上是不可能的，也许它就可以起飞。所有这一切都是用一种悠扬优雅的方式
回答 1
Stack Overflow用户
回答已采纳
发布于 2010-11-07 13:37:07
在下面的GetMinOs2中，“动态”删除了已知的非最小元素。它使用一个列表Ol，它以Os的所有元素开始。“指针”索引l指向列表Ol的“结束”。当发现一个非极小元素时，它的位置与Ol[l]中的值交换，指针l被减少，从而缩短了Ol的有效长度。这样做可以删除非最小元素，这样就不会再次检查它们。
GetMinOs2假设f具有比较函数的正规性质:传递性、交换性等。
在下面的测试代码中，使用了一个梦想的f，我的时间运行显示了在速度上提高了54倍：
def f(O1,O2):
if O1%4==3 or O2%4==3: return 2
return cmp(O1,O2)
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
def GetMinOs2(Os):
Ol=list(Os)
l=len(Ol)
i=0
j=1
while i<l:
while j<l:
rel=f(Ol[i],Ol[j])
if rel==1:
l-=1
Ol[i]=Ol[l]
j=i+1
break
elif rel==-1:
l-=1
Ol[j]=Ol[l]
else:
j+=1
else:
i+=1
j=i+1
return set(Ol[:l])
Os=set(range(1000))
if __name__=='__main__':
answer=GetMinOs(Os)
result=GetMinOs2(Os)
assert answer==result它的结果是：
% python -mtimeit -s'import test' 'test.GetMinOs2(test.Os)'
1000 loops, best of 3: 22.7 msec per loop
% python -mtimeit -s'import test' 'test.GetMinOs(test.Os)'
10 loops, best of 3: 1.23 sec per loopPS。请注意:我还没有彻底检查GetMinOs2中的算法，但我认为总的想法是正确的。我在脚本的末尾进行了一些测试，这表明它至少可以在示例数据set(range(1000))上工作。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4117859
复制相关文章
相似问题
腾讯云开发者
