efficiently checking for string.maketrans conflicts?

[Saketh]

Hi everyone:

I'm using "translation" in the sense of string.maketrans here.

I am trying to efficiently compare if two string translations
"conflict" -- that is, either they differently translate the same
letter, or they translate two different letters to the same one. Here
are some examples:

# no conflict - equal
t1 = Translation('ab', 'cd')
t2 = Translation('ab', 'cd')

# no conflict - inverses
t1 = Translation('ab', 'cd')
t2 = Translation('cd', 'ab')

# conflict - same key, different value
t1 = Translation('ab', 'cd')
t2 = Translation('ab', 'ce')

# conflict - different key, same value
t1 = Translation('ab', 'cd')
t2 = Translation('xy', 'cd')

This conflict-checking is the bottleneck of my program, and the
obvious way to implement it -- looping through the translations and
explicitly checking for the above conditions -- is much slower than
I'd like.

Is there a more efficient, Pythonic way of checking if two
translations conflict?

Sincerely,
Saketh

 

[Peter Otten]

Hi everyone:

I'm using "translation" in the sense of string.maketrans here.

I am trying to efficiently compare if two string translations
"conflict" -- that is, either they differently translate the same
letter, or they translate two different letters to the same one. Here
are some examples:

# no conflict - equal
t1 = Translation('ab', 'cd')
t2 = Translation('ab', 'cd')

# no conflict - inverses
t1 = Translation('ab', 'cd')
t2 = Translation('cd', 'ab')

# conflict - same key, different value
t1 = Translation('ab', 'cd')
t2 = Translation('ab', 'ce')

# conflict - different key, same value
t1 = Translation('ab', 'cd')
t2 = Translation('xy', 'cd')

This conflict-checking is the bottleneck of my program, and the
obvious way to implement it -- looping through the translations and
explicitly checking for the above conditions -- is much slower than
I'd like.

Is there a more efficient, Pythonic way of checking if two
translations conflict?

Is the following a correct interpretation of your requirements?

class Translation(object):
def __init__(self, from_, to):
self.from_ = set(from_)
self.to_ = set(to)
self.map = dict(zip(from_, to))

def conflict(t1, t2):
a = t1.from_
b = t2.from_
ma = t1.map
mb = t2.map
if any(ma[x] != mb[x] for x in a & b):
return True
c = set(ma[x] for x in a - b)
d = set(mb[x] for x in b - a)
return c & d

Peter

 

[Michael Spencer]

Hi everyone:

I'm using "translation" in the sense of string.maketrans here.

I am trying to efficiently compare if two string translations
"conflict" -- that is, either they differently translate the same
letter, or they translate two different letters to the same one.

....

Another solution, similar to Peter's...


def conflicts(from1,to1,from2,to2):
'''returns True for 'conflicting translations'
False
'''
# forward translations
trans1 = dict(zip(from1,to1))
trans2 = dict(zip(from2,to2))

for char in set(trans1).intersection(trans2):
if trans1[char] != trans2[char]:
return True

# reverse translations
revtrans1 = dict(zip(to1,from1))
revtrans2 = dict(zip(to2,from2))

for char in set(revtrans1).intersection(revtrans2):
if revtrans1[char] != revtrans2[char]:
return True

return False

HTH
Michael

 

[Saketh]

Hi everyone:

I'm using "translation" in the sense ofstring.maketranshere.

I am trying to efficiently compare if two string translations
"conflict" -- that is, either they differently translate the same
letter, or they translate two different letters to the same one.

...

Another solution, similar to Peter's...

def conflicts(from1,to1,from2,to2):
     '''returns True for 'conflicting translations'

      >>> conflicts('ab','cd','ab','cd')
      False
      >>> conflicts('ab','cd','ab','ce')
      True
      >>> conflicts('ab','cd','xy','cd')
      True
      >>> conflicts('ab','cd','cd','ab')
      False
     '''
     # forward translations
     trans1 = dict(zip(from1,to1))
     trans2 = dict(zip(from2,to2))

     for char in set(trans1).intersection(trans2):
         if trans1[char] != trans2[char]:
             return True

     # reverse translations
     revtrans1 = dict(zip(to1,from1))
     revtrans2 = dict(zip(to2,from2))

     for char in set(revtrans1).intersection(revtrans2):
         if revtrans1[char] != revtrans2[char]:
             return True

     return False

HTH
Michael

Thank you, Peter and Michael, for your solutions! I think that
Michael's is what I was edging towards, but Peter's has demonstrated
to me how efficient Python's set functions are. I have a lot more to
learn about optimizing algorithms in Python...

 

[Michael Spencer]

Thank you, Peter and Michael, for your solutions! I think that
Michael's is what I was edging towards, but Peter's has demonstrated
to me how efficient Python's set functions are. I have a lot more to
learn about optimizing algorithms in Python...

You're welcome, Saketh

I'm curious how you apply this in your code i.e., if A and B are non-conflicting
translations according to this test, what can you do with them that would
otherwise not be possible?

Michael