以動態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))上運行。