efficiently checking for string.maketrans conflicts?

Peter Otten __peter__ at web.de
Mon Apr 20 20:27:39 CEST 2009


Saketh wrote:

> 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



More information about the Python-list mailing list