TLE in CENCRY

[daft_wullie]

Hi,

the following code is too slow to get accepted in CENCRY although I use a dict of precalculated values. Can someone give me some hints to speed it up?

Thanks in advance
Daft
[bbone=python,434]""" 7696. Encryption. Problem code: CENCRY """
import sys
import collections

import psyco

psyco.full()

def encrypt(word, encs):
ccount = collections.defaultdict(int)
result = [''] * len(word)
for pos, c in enumerate(word):
ccount[c] += 1
k = ccount[c]
result[pos] = encs[c][1][(k-1) % encs[c][0]]
return ''.join(result)

def main():
encs = {
'a': (21,'bhntzgmsyflrxdkqwcjpv'),
'e': (21,'cjpvbhntzgmsyflrxdkqw'),
'i': (21,'dkqwcjpvbhntzgmsyflrx'),
'o': (21,'flrxdkqwcjpvbhntzgmsy'),
'u': (21,'gmsyflrxdkqwcjpvbhntz'),
'b': (5,'aeiou'),
'c': (5,'eioua'),
'd': (5,'iouae'),
'f': (5,'ouaei'),
'g': (5,'uaeio'),
'h': (5,'aeiou'),
'j': (5,'eioua'),
'k': (5,'iouae'),
'l': (5,'ouaei'),
'm': (5,'uaeio'),
'n': (5,'aeiou'),
'p': (5,'eioua'),
'q': (5,'iouae'),
'r': (5,'ouaei'),
's': (5,'uaeio'),
't': (5,'aeiou'),
'v': (5,'eioua'),
'w': (5,'iouae'),
'x': (5,'ouaei'),
'y': (5,'uaeio'),
'z': (5,'aeiou'),
}
cases = sys.stdin.read().split('\n')
results = []
for line in cases[1:-1]:
result = encrypt(line, encs)
results.append(result)
sys.stdout.writelines ('\n'.join(results))
sys.stdout.write('\n')

if name == 'main':
main()[/bbone]

[daft_wullie]

hm, maybe I should try to get rid of collections.defaultdict which does not work well on SPOJ and or with psyco...

First: This may be interesting: http://www.spoj.pl/forum/viewtopic.php?f=20&t=9859

[numerix]

Changing defaultdict to dict will not solve the time-problem. According to my experiments I can tell you the following:
- I will be hard to get a runtime of a pure Python solution (i.e. without psyco) below 3 s, even if well optimized.
- Your code will have an expected runtime of approx. 1.6 s using psyco
- If you do some (accelerating) modifications in your encrypt()-function - without changing the rest of your code - you can reach a runtime near to the TL of 1 s, maybe slighly below.

[daft_wullie]

Thanks a lot for your hints. I will try to find some optimizations. Having not intalled a local psyco instance yet, I will do some tests without psyco on IDEONE first.

[daft_wullie]

a bunch of modifications and tests didn't reveal the optimizations needed - at least not on IEDEONE with Python 2.7 sigh.

These variations[bbone=Python,453] def encrypt_ori(word, encs):
ccount = {}
result = [''] * len(word)
for pos, c in enumerate(word):
if c in ccount:
ccount[c] += 1
else:
ccount[c] = 1
k = ccount[c]
result[pos] = encs[c][1][(k-1) % encs[c][0]]
return ''.join(result)
encrypt = encrypt_ori

def encrypt_nojoin(word, encs):
ccount = {}
result = ''
for c in word:
if c in ccount:
ccount[c] += 1
else:
ccount[c] = 1
k = ccount[c]
result += encs[c][1][(k-1) % encs[c][0]]
return result

def encrypt_inidic(word, encs):
ccount = dict(zip(list(string.lowercase), [0]*26))
result = [''] * len(word)
for pos, c in enumerate(word):
ccount[c] += 1
k = ccount[c]
result[pos] = encs[c][1][(k-1) % encs[c][0]]
return ''.join(result)

def enc_list(word, encs):
ccount = [0] * 26
result = [''] * len(word)
for pos, c in enumerate(word):
i = ord(c)-97
ccount[i] += 1
k = ccount[i]
result[pos] = encs[c][1][(k-1) % encs[c][0]]
return ''.join(result)

def encrypt_nok(word, encs):
ccount = {}
result = [''] * len(word)
for pos, c in enumerate(word):
if c in ccount:
ccount[c] += 1
else:
ccount[c] = 1
result[pos] = encs[c][1][(ccount[c]-1) % encs[c][0]]
return ''.join(result)

def enc_noini(word, encs):
ccount = {}
result = []
for pos, c in enumerate(word):
if c in ccount:
ccount[c] += 1
else:
ccount[c] = 1
k = ccount[c]
result.append(encs[c][1][(k-1) % encs[c][0]])
return ''.join(result)

def enc_inidictemp(word, encs):
ccount = dict(zip(list(string.lowercase), [0]*26))
result = [''] * len(word)
for pos, c in enumerate(word):
ccount[c] += 1
k = ccount[c]
charlist = encs[c][1]
result[pos] = charlist[(k-1) % encs[c][0]]
return ''.join(result)

def enc_global(word, dummy):
ccount = {}
result = [''] * len(word)
for pos, c in enumerate(word):
if c in ccount:
ccount[c] += 1
else:
ccount[c] = 1
k = ccount[c]
result[pos] = _ENCS[c][1][(k-1) % _ENCS[c][0]]
return ''.join(result)
[/bbone] resulted in this timings:

Output:
Function:     encrypt_ori Time: 1.163
Function:  encrypt_nojoin Time: 1.216
Function:  encrypt_inidic Time: 1.045
Function:        enc_list Time: 1.151
Function:     encrypt_nok Time: 1.136
Function:       enc_noini Time: 1.290
Function:  enc_inidictemp Time: 1.066
Function:      enc_global Time: 1.199

I'll have to test it using Python 2.5. and psyco. Or am I to blind to see an obvious acceleration? I'm still far away from being an expert in python...
Daft
P.S. The times shown are seconds for ten calls of respective function for encoding a 5*10^4 char string.