用动态python方法求偏序s中的最小元素

Question

设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。在

这不难做到，但我相信可以用一种更具Python式的方式来完成。在

快速而肮脏的方法是：

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次。我想知道是否有一个动态的方法。 我所说的“动态”并不仅仅是指快速，而是指一旦发现某件事在最小程度上是不可能的，也许它可以被取消。以一种优雅的方式来完成这一切

Answer 1

GetMinOs2下面，“动态”删除已知的非最小元素。它使用一个列表Ol，它以Os的所有元素开头。 “指针”索引l指向列表Ol的“结尾”。当找到一个非最小元素时，它的位置与Ol[l]中的值交换，并且指针l减少，因此{}的有效长度被缩小。 这样做会删除非最小元素，因此不会再次检查它们。在

GetMinOs2假设{}具有比较函数的正常性质：传递性、交换性等

在下面的测试代码中，使用dreamt upf，我的time it run显示速度提高了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

结果的时间是：

^{pr2}$

请注意：我还没有彻底检查GetMinOs2中的算法，但我认为总体思路是正确的。我在脚本的末尾做了一个小测试，测试结果表明它至少对示例数据set(range(1000))起作用。在