實現特定的比較功能

Question

我正在實施本文中的並行DC3，pDC3算法：http://algo2.iti.kit.edu/sanders/papers/KulSan06a.pdf。

見第12行：

""" 
Sort S0 U S1 U S2 using the comparison function: 
    (c, ...) in S1 U S2 <= (d, ...) in S1 U S2 <=> c <= d 
    (t, t', c', c'', i) in S0 <= (u, u', d', d'', j) in S0 <=> (t, c') <= (u, d') 
    (t, t', c', c'', i) in S0 <= (d, u,  d', j) in S1 <=> (t, c') <= (u, d') 
    (t, t', c', c'', i) in S0 <= (d, u, u', d'', j) in S2 <=> (t, t', c'') <= (u, u', d'') 
""" 

我將如何實現在Python這樣的比較？

對不起，我還沒有在這裏給出完整的圖片。但是，讓我回去了幾步，顯示什麼S0-S2的樣子在我的實現：

我的代碼的最後幾行，我計算S0-S2：

s0 = computeS0(indexSortedRankIndexPairs, text, paddedText) 
print 'Set0:       ' + str(s0) 

s1 = computeS1(indexSortedRankIndexPairs, text, paddedText) 
print 'Set1:       ' + str(s1) 

s2 = computeS2(indexSortedRankIndexPairs, text, paddedText) 
print 'Set2:       ' + str(s2) 

這是樣本輸出從我的程序：

Text       yabbadabbado 
Padded Text     yabbadabbado00 
Trituples:      set([('ada', 4), ('bba', 7), ('abb', 1), ('o00', 11), ('do0', 10), ('bad', 8), ('bba', 2), ('dab', 5)]) 
Sorted Trituples:    [('abb', 1), ('ada', 4), ('bad', 8), ('bba', 7), ('bba', 2), ('dab', 5), ('do0', 10), ('o00', 11)] 
Rank Index Pairs:    [(1, 1), (2, 4), (3, 8), (4, 7), (4, 2), (5, 5), (6, 10), (7, 11)] 
Sorted Rank Index Pairs:  [(1, 1), (2, 4), (4, 7), (6, 10), (4, 2), (5, 5), (3, 8), (7, 11)] 
Index Sorted Rank Index Pairs: [(1, 1), (4, 2), (2, 4), (5, 5), (4, 7), (3, 8), (6, 10), (7, 11)] 
Set0:       set([('a', 'd', 6, 7, 9), ('y', 'a', 1, 4, 0), ('a', 'b', 4, 3, 6), ('b', 'a', 2, 5, 3)]) 
Set1:       set([(2, 'a', 5, 4), (1, 'a', 4, 1), (4, 'b', 3, 7), (6, 'd', 7, 10)]) 
Set2:       set([(7, 'o', '0', 0, 11), (3, 'b', 'a', 6, 8), (5, 'd', 'a', 4, 5), (4, 'b', 'b', 2, 2)]) 

所以，S0，S1和S2基本上是本地Python集（至少現在）。

Answer 1

我想我可以在這裏給你一些總體想法。

假設你正在使用Python 2.x的

這將是我的問題解決辦法：

Set0 = set([('a', 'd', 6, 7, 9), ('y', 'a', 1, 4, 0), ('a', 'b', 4, 3, 6), ('b', 'a', 2, 5, 3)]) 
    Set1 = set([(2, 'a', 5, 4), (1, 'a', 4, 1), (4, 'b', 3, 7), (6, 'd', 7, 10)]) 
    Set2 = set([(7, 'o', '0', 0, 11), (3, 'b', 'a', 6, 8), (5, 'd', 'a', 4, 5), (4, 'b', 'b', 2, 2)]) 


    def make_s0(s): 
     # add an element to the tuple to 'tag' the set 
     return [('s0', a, b, c, d, e) for (a, b, c, d, e) in s] 

    def make_s1(s): 
     return [('s1', a, b, None, d, e) for (a, b, d, e) in s] 

    def make_s2(s): 
     return [('s2', a, b, c, d, e) for (a, b, c, d, e) in s] 

    def cmp_elem(l, r): 
     # you need to complete the implementation here 
     # based on the first element of the tag to carry out comparsion 
     if l[0] == 's0' and r[0] == 's0': 
      (_, t, tdash, cdash, cdashdash, i) = l 
      (_, u, udash, ddash, ddash, j) = r 
      return cmp((t, cdash), (u, ddash)) 
     elif (l[0] == 's1' and r[0] == 's2') or (l[0] == 's2' and r[0] == 's1'): 
      (_, c, _, _, _, _) = l 
      (_, d, _, _, _, _) = r 
      return cmp(c, d) 
     return 0 

    if __name__ == "__main__": 
     l = make_s0(Set0) + make_s1(Set1) + make_s2(Set2) 
     print sorted(l, cmp=cmp_elem) 

閱讀本http://docs.python.org/3.3/howto/sorting.html轉換上面的代碼在Python運行3個

Answer 2

規則像這樣看起來很容易容納在一個關鍵功能

(c, . . .) ∈ S1 ∪ S2 ≤ (d,. . .) ∈ S1 ∪ S2 ⇔ c ≤ d 
(t, t′ , c′ , c′′, i) ∈ S0 ≤ (u, u′ , d′, d′′, j) ∈ S0 ⇔ (t, c′) ≤ (u, d′) 

但我怎麼看不到這些的，可以這麼容易accomodated

(t, t′, c′, c′′, i) ∈ S0 ≤ (d, u,  d′, j) ∈ S1 ⇔ (t,c′) ≤ (u, d′) 
(t, t′, c′, c′′, i) ∈ S0 ≤ (d, u, u′, d′′, j) ∈ S2 ⇔ (t,t′, c′′) ≤ (u, u′, d′′) 

你可能不得不退回到使用比較函數用於排序

在Python2，你仍然可以使用棄用cmp=參數
在Python3，使用functools.cmp_to_key並傳遞到key=參數