以动态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,优雅的方式完成所有这些     
已邀请:
GetMinOs2
,“动态”删除已知非最小的元素。它使用一个列表
Ol
,它以
Os
的所有元素开头。 “指针”索引
l
指向列表"2ѭ的“结束”。当找到非最小元素时,其位置与
Ol[l]
中的值交换,指针
l
递减,因此收缩effective2ѭ的有效长度。 这样做会删除非最小元素,因此不要再次检查它们。
GetMinOs2
假设
f
具有比较函数的正常属性:传递性,交换性等。 在下面的测试代码中,以梦想的
f
,我的timeit运行显示速度提高了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 loop
PS。请注意:我没有彻底检查GetMinOs2中的算法,但我认为一般的想法是正确的。我在脚本的末尾进行了一些测试,显示它至少在样本数据上起作用
set(range(1000))
。     

要回复问题请先登录注册