Coding challenge: Optimise a custom string encoding

[Peter Otten]

Alex Willmer wrote:

> On Monday, 18 August 2014 21:16:26 UTC+1, Terry Reedy  wrote:
>> On 8/18/2014 3:16 PM, Alex Willmer wrote:
>> > A challenge, just for fun. Can you speed up this function?
>> 
>> You should give a specification here, with examples. You should perhaps
> 
> Sorry, the (informal) spec was further down.
> 
>> > a custom encoding to store unicode usernames in a config file that only
>> > allowed mixed case ascii, digits, underscore, dash, at-sign and plus
>> > sign. We also wanted to keeping the encoded usernames somewhat human
>> > readable.
> 
>> > My design was utf-8 and a variant of %-escaping, using the plus symbol.
>> > So u'alic EURO 123' would be encoded as b'alic+e2+82+ac123'.
> 
> Other examples:
>>>> plus_encode(u'alice')
> 'alice'
>>>> plus_encode(u'Bacon & eggs only $19.95')
> 'Bacon+20+26+20eggs+20only+20+2419+2e95'
>>>> plus_encode(u'üｎïｃｏԁë')
> '+c3+bc+ef+bd+8e+c3+af+ef+bd+83+ef+bd+8f+d4+81+c3+ab'
> 
>> You should perhaps be using .maketrans and .translate.
> 
> That wouldn't work, maketrans() can only map single bytes to other single
> bytes. To encode 256 possible source bytes with 66 possible symbols
> requires a multi-symbol expansion of some or all source bytes.

You can do the translation in unicode, but you have to cope with a big 
translation table and the speed-up doesn't seem to be worthwhile:

$ cat plus_encode.py
# -*- coding: utf-8 -*-
import string

charset = set(string.ascii_letters + string.digits + '@_-')
byteseq = [chr(i) for i in xrange(256)]
bytemap = {byte: byte if byte in charset else '+' + byte.encode('hex')
           for byte in byteseq}

def plus_encode(s):
    """Encode a unicode string with only ascii letters, digits, _, -, @, +
    """
    bytemap_ = bytemap
    s_utf8 = s.encode('utf-8')
    return ''.join([bytemap[byte] for byte in s_utf8])


import sys
from itertools import imap as map

MAXUNICODE = 9000 #should be sys.maxunicode
ucharset = set(c.decode("ascii") for c in charset)
xmap = [u if u in ucharset else 
        u"".join("+" + c.encode("hex") for c in u.encode("utf-8"))
        for u in map(unichr, xrange(MAXUNICODE))]

def plus_encode2(s):
    return s.translate(xmap).encode("ascii")

if __name__ == "__main__":
    sample = u"".join(map(unichr, range(MAXUNICODE))) + u"€"
    assert plus_encode(sample) == plus_encode2(sample)
$ python plus_encode.py
$ python -m timeit -s 'import plus_encode' 'plus_encode.plus_encode(u"""qwertyuiop1234567890!"£$%^&*()\n{EURO-SIGN}""")'
100000 loops, best of 3: 10.6 usec per loop
$ python -m timeit -s 'import plus_encode' 'plus_encode.plus_encode2(u"""qwertyuiop1234567890!"£$%^&*()\n{EURO-SIGN}""")'
100000 loops, best of 3: 3.74 usec per loop

A smaller table is possible, but costs time:

ymap = [u if u in ucharset else
        u"+" + u.encode("latin1").encode("hex").decode("ascii")
        for u in map(unichr, xrange(256))]
def plus_encode3(s):
    return s.encode("utf-8").decode("latin1").translate(ymap).encode("ascii")

$ python -m timeit -s 'import plus_encode' 'plus_encode.plus_encode3(u"""qwertyuiop1234567890!"£$%^&*()\n{EURO-SIGN}""")'
100000 loops, best of 3: 5.91 usec per loop