1 / 16
Aug 2008

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

  • created

    Aug '08
  • last reply

    Jan '14
  • 15

    replies

  • 1.3k

    views

  • 6

    users

  • 3

    links

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

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

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 frowning

What's wrong with it ?

Thanks,

oro

You solved SBANK in python using naive algorithm ?

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

no smile
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 smile

use % formatting instead of concatenating string

and about sorting ...

... 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

Hello,

I tried your naive method, didn't work frowning

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

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

#!/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

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).

read my blog smile
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()#

Hi

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

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

Thanks a lot,

Oro

5 years later

[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

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.

2 months later

Hope I get a reply on this one, as none of my posts have recieved any replies so far! cry exclamation
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)

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