Speed up python code

  • (2 Pages)
  • +
  • 1
  • 2

22 Replies - 2034 Views - Last Post: 23 May 2014 - 07:55 AM Rate Topic: -----

#1 Hrand   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 109
  • Joined: 25-June 12

Speed up python code

Posted 21 May 2014 - 12:24 PM

I'm trying to submit this code in sphere online judge. It works just fine, however it exceeds the time limit. I've submitted the code in c++ and it worked just fine using the same logic. How would I go about optimizing this code in python
num = int(input())
arr1 = []
arr2 = []
for i in range(0, num):
    temp, temp2 = input().split()
    temp, temp2 = [int(temp), int(temp2)]
    arr1.append(temp)
    arr2.append(temp2)

for j in range(0, num):
    print(arr1[j] * arr2[j])



Is This A Good Question/Topic? 0
  • +

Replies To: Speed up python code

#2 jon.kiparsky   User is online

  • Beginner
  • member icon


Reputation: 11836
  • View blog
  • Posts: 20,061
  • Joined: 19-March 11

Re: Speed up python code

Posted 21 May 2014 - 12:32 PM

Can you provide the problem description, so we know what you're trying to do?
Was This Post Helpful? 0
  • +
  • -

#3 Hrand   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 109
  • Joined: 25-June 12

Re: Speed up python code

Posted 21 May 2014 - 12:38 PM

n [the number of multiplications <= 1000]
l1 l2 [numbers to multiply (at most 10000 decimal digits each)]

Text grouped in [ ] does not appear in the input file.




Output



The results of multiplications.


Example

Input:
5
4 2
123 43
324 342
0 12
9999 12345

Output:
8
5289
110808
0
123437655
Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky   User is online

  • Beginner
  • member icon


Reputation: 11836
  • View blog
  • Posts: 20,061
  • Joined: 19-March 11

Re: Speed up python code

Posted 21 May 2014 - 12:48 PM

One obvious improvement would be to just multiply and print the numbers as you read them. Since the products don't depend on any other values, this should save you a little time.
Was This Post Helpful? 0
  • +
  • -

#5 Hrand   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 109
  • Joined: 25-June 12

Re: Speed up python code

Posted 21 May 2014 - 01:05 PM

However that would mean at the end of every input an output would follow, instead of printing out all the outputs at once like SPOJ showed in their example.
Was This Post Helpful? 0
  • +
  • -

#6 Hrand   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 109
  • Joined: 25-June 12

Re: Speed up python code

Posted 21 May 2014 - 01:14 PM

View Postjon.kiparsky, on 21 May 2014 - 12:48 PM, said:

One obvious improvement would be to just multiply and print the numbers as you read them. Since the products don't depend on any other values, this should save you a little time.


I did try your suggestion though

num = int(input())
for i in range(0, num):
    temp, temp2 = input().split()
    temp, temp2 = [int(temp), int(temp2)]
    print(temp * temp2)



And the code still ran too slow for SPOJ I honestly don't know what would make it faster.
Was This Post Helpful? 0
  • +
  • -

#7 jon.kiparsky   User is online

  • Beginner
  • member icon


Reputation: 11836
  • View blog
  • Posts: 20,061
  • Joined: 19-March 11

Re: Speed up python code

Posted 21 May 2014 - 01:14 PM

That will produce the same output as the code you've got now, and it'll do it a little more efficiently. If there are contraints on the output format that you're not mentioning or including in your code, please spell them out. Ideally, the precise problem statement that you're working from would be nice. Or just a link to the problem...
Was This Post Helpful? 0
  • +
  • -

#8 Hrand   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 109
  • Joined: 25-June 12

Re: Speed up python code

Posted 21 May 2014 - 01:18 PM

View Postjon.kiparsky, on 21 May 2014 - 01:14 PM, said:

That will produce the same output as the code you've got now, and it'll do it a little more efficiently. If there are contraints on the output format that you're not mentioning or including in your code, please spell them out. Ideally, the precise problem statement that you're working from would be nice. Or just a link to the problem...



I copied and pasted the problem in, but here is the link to the problem as well. http://www.spoj.com/problems/MUL/
Was This Post Helpful? 0
  • +
  • -

#9 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7507
  • View blog
  • Posts: 15,558
  • Joined: 16-October 07

Re: Speed up python code

Posted 21 May 2014 - 03:50 PM

Hmm... you could burn one more step:
for i in range(int(input())):
    temp, temp2 = input().split()
    print(int(temp) * int(temp2))



On the off chance print is a slow implementation, I suppose you could do something like:
[code]
n = int(input())
print('\n'.join(str(int(x)*int(y) for (x,y) in ( input().split() for i in range(n) ) ) ) )


Was This Post Helpful? 1
  • +
  • -

#10 Hrand   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 109
  • Joined: 25-June 12

Re: Speed up python code

Posted 21 May 2014 - 04:15 PM

View Postbaavgai, on 21 May 2014 - 03:50 PM, said:

Hmm... you could burn one more step:
for i in range(int(input())):
    temp, temp2 = input().split()
    print(int(temp) * int(temp2))



On the off chance print is a slow implementation, I suppose you could do something like:
[code]
n = int(input())
print('\n'.join(str(int(x)*int(y) for (x,y) in ( input().split() for i in range(n) ) ) ) )



I'm starting to think the problem is with spoj, I tried both implementations you gave and they both exceeded the time limit.
Was This Post Helpful? 0
  • +
  • -

#11 Hrand   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 109
  • Joined: 25-June 12

Re: Speed up python code

Posted 21 May 2014 - 04:39 PM

View PostHrand, on 21 May 2014 - 04:15 PM, said:

View Postbaavgai, on 21 May 2014 - 03:50 PM, said:

Hmm... you could burn one more step:
for i in range(int(input())):
    temp, temp2 = input().split()
    print(int(temp) * int(temp2))



On the off chance print is a slow implementation, I suppose you could do something like:
[code]
n = int(input())
print('\n'.join(str(int(x)*int(y) for (x,y) in ( input().split() for i in range(n) ) ) ) )



I'm starting to think the problem is with spoj, I tried both implementations you gave and they both exceeded the time limit.



I've even tried to write directly reducing header and it was still too slow
import sys
for i in range(int(input())):
    temp, temp2 = input().split()
    sys.stdout.write(str(int(temp) * int(temp2)))


Was This Post Helpful? 0
  • +
  • -

#12 Hrand   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 109
  • Joined: 25-June 12

Re: Speed up python code

Posted 21 May 2014 - 04:51 PM

I've been reading forums online about this problem and the use of python. Must people seem to agree that python cannot solve this problem fast enough because of the int<->string conversion. That's probably why I was able to solve the problem in c++ using the same logic and not in python.
Was This Post Helpful? 0
  • +
  • -

#13 jon.kiparsky   User is online

  • Beginner
  • member icon


Reputation: 11836
  • View blog
  • Posts: 20,061
  • Joined: 19-March 11

Re: Speed up python code

Posted 21 May 2014 - 05:37 PM

Surely that can't be the only reason. Do you not need to convert from string to int to do this in C?

If the question is interesting to you, you could always try benchmarking different operations and see if you can spot the holdup that way. It might be in the conversion, it might be in the multiplication, it might be in the input step. If you prepare little programs that each just do one of those steps, and then time them running on batches of 1000. Keep in mind that you're dealing with 10k-digit numbers, so you're going to have to generate some streams of data to handle that - that's a considerable amount of data, in the megabytes, which you probably want to have at the ready and in memory so you don't taint your experiment.

Once you've figured out where you're spending most of your time, you have a pretty good idea of where to start optimizing.
Was This Post Helpful? 1
  • +
  • -

#14 Shadowys   User is offline

  • D.I.C Head
  • member icon

Reputation: 10
  • View blog
  • Posts: 64
  • Joined: 16-May 14

Re: Speed up python code

Posted 21 May 2014 - 09:59 PM

Using a scenario of 1000 nines multiplying each other.
import profile
nines="9"*1000+" "+"9"*1000+"\n"
Ex=nines*1000
def main():
    x=Ex.split("\n")
    arr= (int(k.split()[0])*int(k.split()[1]) for k in x if len(k.split())>1)
    arr='\n'.join(str(k) for k in arr)
    print(arr)    
profile.run('main()') 



Done in 1.531 seconds.

Your code:
import profile
nines="9"*1000+" "+"9"*1000+"\n"
Ex=nines*1000
def main2():
    num=1000
    arr1=[]
    arr2=[]
    x=Ex.split("\n")
    for i in range(num):
        temp,temp2=x[i].split()
        temp,temp2=[int(temp),int(temp2)]
        arr1.append(temp)
        arr2.append(temp2)
    for j in range(num):
        print(arr1[j]*arr2[j])
profile.run('main2()') 


Done in 3.391 seconds.

Note:
I used generators, with the (<gen exp>) not [<gen exp>] so it won't be turned into a list, which I don't need.
I also reduced the print statement to just one, so it dumps everything once.
You can try profiling the code for performance checks.

This post has been edited by Shadowys: 21 May 2014 - 10:02 PM

Was This Post Helpful? 1
  • +
  • -

#15 Shadowys   User is offline

  • D.I.C Head
  • member icon

Reputation: 10
  • View blog
  • Posts: 64
  • Joined: 16-May 14

Re: Speed up python code

Posted 21 May 2014 - 10:23 PM

Interesting note:
1.297 seconds were all spent in the join function and the genexp
and another 0.453 seconds were spent in another genexp.
*-*

This post has been edited by Shadowys: 21 May 2014 - 10:27 PM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2