以动态pythonic方式查找部分有序集中的最小元素

Question

假设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,优雅的方式完成所有这些

Answer 1

GetMinOs2下面，“动态”删除已知非最小的元素。Ol它使用一个以 的所有元素开头的列表Os。“指针”索引 l指向列表的“末尾” Ol。当找到非最小元素时，其位置将与 in 的值交换Ol[l]，并且指针会递减，从而缩小l的有效长度。Ol这样做会删除非最小元素，因此您无需再次检查它们。

GetMinOs2假设f具有比较函数的正常属性：传递性、交换性等。

在下面的测试代码中，使用 dreamt-up 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

附言。请注意：我还没有彻底检查 GetMinOs2 中的算法，但我认为总体思路是正确的。我在脚本末尾进行了一些测试，表明它至少适用于示例数据set(range(1000))。