CODEWITHSUNDEEP
pythonalgorithmsortingcomparison
p0lAris
p0lAris

Reputation: 4820

Implementing a particular comparison function

I am implementing the parallel DC3, pDC3 algorithm from this paper: http://algo2.iti.kit.edu/sanders/papers/KulSan06a.pdf.

See line 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'')
"""

How will I be implementing such a comparison in Python?

Sorry I haven't given the complete picture here. But let me go back a few steps and show what S0-S2 look like in my implementation:

The last few lines of my code where I compute 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)

This is the sample output from my program:

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

So, S0, S1 and S2 are basically native Python sets (at least for now).

Upvotes: 2

Views: 118

Answers (2)

John La Rooy
John La Rooy

Reputation: 304147

Rules like this look easy enough to accomodate in a key function

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

But I don't see how these ones can be accomodated so easily

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

You'll probably have to fall back to use a comparison function for the sort

in Python2, you can still use the deprecated cmp= parameter
in Python3, use functools.cmp_to_key and pass that to the key= parameter

Upvotes: 0

Anthony Kong
Anthony Kong

Reputation: 40634

I think I can give you some general idea here.

Assuming you are using python 2.x

It will be my approach to the problem:

    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)

Read this http://docs.python.org/3.3/howto/sorting.html to convert the above code to run in python 3

Upvotes: 1

Related Questions