What can slow down the execution time of a python script?

[orochimaru_sof]

Hello,

Can someone please list the things that can slow down the execution time of a python program, and have faster subsitutes in python, especially in context of time-critical problems, like SBANK, etc.

Thanks,

Oro

[izekia]

Do you use psyco?
It can make your code work more faster

[izekia]

and show your solution for sbank
i've solved it with naive algorithm

[orochimaru_sof]

Hi,

#!/usr/local/bin/python
import sys
def stablesort(list2):
        a=[];
        c=[];
        n = len(list2[0][0]);
        if(n > 4):
                list3 = [];
                for elem in list2:
                        elem[1].extend([elem[0]]);
                        elem = [elem[0][4:],elem[1]];
                        list3.extend([elem]);
                list4= stablesort(list3);
                list3 = [];
                for elem in list4:
                        iword = elem.pop(len(elem)-1);
                        list3.extend([[iword[:4],elem]]);
                list3 = stablesort(list3);
                return list3;
        n = 10**n;
    for i in range(n+1):
            a.extend([0]);
    for i in range(len(list2)):
            c.extend([0]);
    for elem in list2:
            a[int(elem[0])] += 1;
    for i in range(1,n):
            a[i]+= a[i-1];
    i = len(list2)-1;
    while i >= 0:
            c[a[int(list2[i][0])]-1] = list2[i][1];
            a[int(list2[i][0])]-=1;
            i -= 1;
    return c;
def radixsort(list1):
        digitlist = list1;
        n = len(digitlist[0]);
        i2 =n-1;
        while i2>0:
                digitlist2=[];
                for listelem in digitlist:
                        digitlist2.extend([[listelem[i2],listelem]]);
                digitlist = stablesort(digitlist2);
                i2-=1;
        return digitlist;
def mysort(listtobesorted):
        finallist = [];
        for i in listtobesorted:
                finallist.extend([i.split(' ')]);
        return radixsort(finallist);
accountnumberlist = [];
accountnumberlist2 = [];
t = int(sys.stdin.readline().rstrip());
for i in range(t):
        n = int(sys.stdin.readline().rstrip());
        accountnumberlist = [];
        for j in range(n):
                accountnumberlist.extend([sys.stdin.readline().rstrip()]);
        sys.stdin.readline().rstrip();
        if int(n)>0:
                newlist = [];
                newlist2 = [];
                newlist = mysort(accountnumberlist);
                for elem in newlist:
                    newlist2.extend([' '.join(elem)]);
            i = 0;
            while i < len(newlist2):
                    count2 = newlist2.count(newlist2[i]);
                    temp = newlist2[i];
                    for j in range(count2):
                            sys.stdout.write(temp+" "+str(j+1)+"\n");
                    i+=count2;
            sys.stdout.write("\n");

I've used radixsort (along with counting sort). It should be working fast, but it's not

What's wrong with it ?

Thanks,

oro

[orochimaru_sof]

You solved SBANK in python using naive algorithm ?

What exactly is your definition of "naive" ? I hope you don't mean bubble sort

[izekia]

no
i just simply used sorted() function

about your code:
instead of

myList = []
# and then many extends or appends

use

myList = [None] * listSize
# and the just do myList[idx] = value

no need to strip account and no need to strip empty line, of course

use % formatting instead of concatenating string

and about sorting ...

[izekia]

... about sorting you using string to int converting it's too expensive
you should avoid it in this problem
and so many lists extending i've wrote about before

and at last use psyco
simply write

import psyco
psyco.full()

after import sys

and if you don't use psyco, you should use xrange instead of range in for in -constructions

[orochimaru_sof]

Hello,

I tried your naive method, didn't work

I tried using psyco, xrange, using %s instead of string concatenation and using the internal sorted() function. Still didn't work (

Here's my code, can you please tell me where I'm going wrong

#!/usr/local/bin/python
import sys
import psyco
psyco.full();
t = int(sys.stdin.readline().rstrip());
print t;
for i in range(t):
        n = int(sys.stdin.readline().rstrip());
        accountnumberlist  = [None]*n;
        for j in range(n):
                accountnumberlist[j] = sys.stdin.readline().rstrip();
        accountnumberlist=sorted(accountnumberlist);
    sys.stdin.readline().rstrip();
    newlist2 = sorted(accountnumberlist);
    a = len(newlist2);
    x = 0;
    while x < a:
            elem = newlist2[x];
            sys.stdout.write("%s 1\n" % (elem));

            j = x+1;
            while j < a and newlist2[j] == elem :
                    sys.stdout.write("%s %s\n" % (elem,j-x+1));
                    j += 1;
            x = j;
    sys.stdout.write("\n");

Thanks,

Oro

[peristarkawan]

I/O is slow, and this problem has a lot of it. Try reading the entire input at once into a cStringIO object. Also try doing all your output using a single print statement (the str.join method is very useful for this).

[izekia]

read my blog
psyco work only with functions
my solution:

import gc
gc.disable()
import sys
import psyco
psyco.full()
fin = sys.stdin
#from datetime import datetime#
def main():
	data = fin.read().split('\n')
	start = 2
	dataLen = len(data)
	while start < dataLen:
		accs = {}
		lines = int(data[start - 1].rstrip())
		for i in xrange(start, start + lines):
			accs[data[i]] = (accs[data[i]] + 1) if accs.has_key(data[i]) else 1
		for k, v in sorted(accs.iteritems()):
			sys.stdout.write('%s%i\n' % (k, v))
		sys.stdout.write('\n')
		start += lines + 2
#fin = open('sbank.in')#
#fout = open('sbank.out', 'w')#
#tmpout = sys.stdout#
#sys.stdout = fout#
#t = datetime.now()#
main()
#sys.stdout = tmpout#
#print datetime.now() - t#
#fout.close()#
#fin.close()#

[orochimaru_sof]

Hi

Thanks a lot, both of you, got AC. As you both correctly pointed out, I/O was the main culprit

I'll keep this in mind in the future..

Thanks a lot,

Oro

[ronaeg]

[quote="izekia"]... about sorting you using string to int converting it's too expensive
you should avoid it in this problem
and so many lists extending i've wrote about before
شركة تنظيف
شركة نقل اثاث
شركة نقل عفش بالرياض
and at last use psyco
simply write

import psyco
psyco.full()

after import sys

and if you don't use psyco, you should use xrange instead of range in for in -constructions[/quote]
i tried that , but unfortionatly didn't work

[numerix]

Psyco is dead and no longer supported. So you have to do it without.
If you tell me what problem you want to solve, I might perhaps tell you, if you have a chance to get it AC in time.

[mjnovice]

Hope I get a reply on this one, as none of my posts have recieved any replies so far!
Upon suggestions i used bulk i/o, still TLE . any suggestions ?? This is SBANK problem.

import sys
alls=sys.stdin.readlines()
#print len(alls)
ind=0
dd=[]
t=int(alls[ind])
ind+=1
while ind<len(alls):
  while t:
	n=str(alls[ind])
	ind+=1
	if ind==len(alls):
	  break
	if n:
		n=int(n)	
		myaccs={}
		for i in xrange(0,n):
			m=str(alls[ind])
			ind+=1
			m=m.replace(" ","")
			m=int(m)
			if myaccs.has_key(m):
				myaccs[m]+=1
			else:
				myaccs.update({m:1})
		#print len(myaccs)
		for tmp,cnt in sorted(myaccs.iteritems()):
			ans=str("%026d"%tmp)
			fin= ans[0:2]+" "+ans[2:10]+" "+ans[10:14]+" "+ans[14:18]+" "+ans[18:22]+" "+ans[22:26]+" "+str(cnt)
			#print fin
			dd.append(fin)
			#print "%02d"%int(ans[0:2]),"%08d"%int(ans[3:10]),  "%04d"%int(ans[11:15]), "%04d"%int(ans[16:20]),"%04d"%int(ans[21:25]),"%04d"%myaccs[i][26:30],cnt
		#print ""
		dd.append("")
		ind+=1
		t-=1
nl="\n"
dd=tuple(dd)
qew=nl.join(dd)
sys.stdout.write(qew)
#print len(dd)

[numerix]

any suggestions ??

Yes. Tell us the SPOJ problem you want to solve.

[mjnovice]

I have made the edit stating the problem code . Please Help