Wdrażam równoległe DC3, algorytm PDC3 z tego artykułu: http: // algo2. iti.kit.edu/sanders/papers/kulsan06a.pdf.

Zobacz linię 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'')
"""

Jak będę wdrażać takie porównanie w Pythonie?

Przepraszam, że nie podałem tutaj pełnego obrazu. Ale pozwól mi wrócić kilka kroków i pokaż, jak wygląda S0-S2 w moim wdrożeniu:

Ostatnie kilka linii mojego kodu, w którym obliczę 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)

To jest przykładowe wyjście z mojego programu:

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)])

Tak, S0, S1 i S2 są w zasadzie rodzimych zestawów Pythona (przynajmniej na razie).

2
p0lAris 21 listopad 2013, 01:28

2 odpowiedzi

Najlepsza odpowiedź

Myślę, że mogę dać ci trochę ogólnego pomysłu.

Zakładając, że używasz Pythona 2.x

To będzie moje podejście do problemu:

    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)

Przeczytaj to http://docs.Python.org/3.3/howto/sorting.html Aby przekonwertować powyższy kod, aby uruchomić w Pythonie 3

1
Anthony Kong 20 listopad 2013, 22:02

Zasady, takie jak wyglądają wystarczająco łatwy, aby pomieścić w funkcji klucza

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

Ale nie widzę, jak te te mogą być tak łatwo zakwaterowane

(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′′)

Prawdopodobnie będziesz musiał wrócić do korzystania z funkcji porównawczej dla tego rodzaju

W Python2 możesz nadal używać nieostrożnego parametru {x0}}
W Python3 użyj functools.cmp_to_key i przekazać, że do parametru key=

0
John La Rooy 20 listopad 2013, 22:16