代码之家 › 专栏 › 技术社区 › Pietro Speroni

用动态pythonic方法求偏序集中的最小元素

math algorithm python

Pietro Speroni · 技术社区 · 14 年前

设Os是半序集,给定Os中的任意两个对象O1和O2,如果O1大于O2,F(O1,O2)将返回1;如果O1小于O2,F(O1,O2)将返回1;如果O1不可比,F(O1,O2)将返回1;如果O1等于O2,F(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 回复 | 直到 11 年前

unutbu 14 年前

GetMinOs2 在下面,“动态”删除已知为非最小的元素。它使用一个列表 Ol 从所有的元素开始 Os . l 指向列表的“结尾” 奥尔 . 当找到一个非最小元素时,它的位置将与 Ol[l] 一 奥尔 缩水了。

获取minos2 f 具有比较函数的一般性质:传递性、交换性等。

在下面的测试代码中 f型 ,我的timeit 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

% 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