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

Question

设Os是一个部分有序集合，并且给定Os中的任意两个对象O1和O2，如果O1大于F1，O2（）将返回1 O2，-1如果O1小于O2，如果它们不可比，则为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的“结尾”。当找到非最小元素时，其位置与Ol[l]中的值交换，并且指针l递减，因此Ol的有效长度收缩。 这样做会删除非最小元素，因此您不会再检查它们。

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 

使用timeit结果是：

% 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))上运行。