[Tutor] speed issue

[Kent Johnson]

Conrad,

How fast do you need this to be? On my computer it completes instantly.

The for loops should be fast, dict operations in Python are pretty fast. I 
don't think they are O(n^2).

A few things you could do to squeeze a little bit out of it:
- You can use integers as your dict keys - there is no need to convert to 
strings, e.g. use interval[x] instead of interval[str(x)]. Actually you 
could make interval a list instead of a map, that would probably be faster.

- period and timerange could be split into two variables, that might save a 
little time.

But these are very minor improvements. I don't see any obvious time-killers 
in your code.

HTH,
Kent

At 09:31 AM 8/11/2004 -0700, Conrad wrote:
>Hey tutors,
>
>I'm trying to solve this problem:
>http://spoj.sphere.pl/?a=problem&pcode=PICAD.
>
>Basically you are given 10 test cases. The first line in the test
>contains two numbers, the beginning and end of a sequence of numbers.
>ie.
>5 10
>would equal
>5 6 7 8 9 10
>The next line contains one number, z, this number represents how many
>other sequences of numbers you will get.
>After that you are given z lines all containing 2 numbers which mark the
>beginning and end of a sequence of numbers.
>ie.
>4
>3 5
>6 7
>1 10
>2 8
>
>The task is to figure out which number occurs the most from the original
>sequence in the given sequences.
>
>My solution is here, but the two for loops really slow it down, can
>anyone point out how to speed this code up. It takes input from stdin.
>(./program.py < test_file)
>
>I appreciate any help.
>
>Conrad
>
>#!/usr/bin/python
>
>import sys
>
>input_file = sys.stdin
>
>intervals = {}
>period = [0,0]
>
>def interval():
>         possible = input_file.readline().split()
>         period[0] = (int(possible[0]))
>         period[1] = (int(possible[1]))
>         #Next two lines slow it down ((O^2)?)
>         for x in range(period[0], period[1] + 1):
>                 intervals[str(x)] = 0
>
>def find_vals():
>         interviewed = int(input_file.readline())
>         for x in range(interviewed):
>                 time_range = map(int, input_file.readline().split())
>                 if time_range[0] < period[0]:
>                         time_range[0] = period[0]
>                 if time_range[1] > period[1]:
>                         time_range[1] = period[1]
>                 #This also slows it way down
>                 for x in range(time_range[0], time_range[1] + 1):
>                         intervals[str(x)] += 1
>
>for x in range(10):
>         interval()
>         find_vals()
>         print min(intervals.values()), max(intervals.values())
>         intervals = {}
>
>
>Here is my test file:
>2 8
>8
>2 3
>1 5
>7 10
>2 6
>4 7
>1 2
>1 2
>1 2
>2 5
>3
>4 6
>3 7
>1 2
>5 10
>4
>1 8
>5 8
>7 10
>8 9
>2 5
>3
>4 6
>3 7
>1 2
>5 10
>4
>1 8
>5 8
>7 10
>8 9
>2 5
>3
>4 6
>3 7
>1 2
>5 10
>4
>1 8
>5 8
>7 10
>8 9
>2 5
>3
>4 6
>3 7
>1 2
>5 10
>4
>1 8
>5 8
>7 10
>8 9
>2 5
>3
>4 6
>3 7
>1 2
>5 10
>4
>1 8
>5 8
>7 10
>8 9
>2 5
>3
>4 6
>3 7
>1 2
>5 10
>4
>1 8
>5 8
>7 10
>8 9
>2 5
>3
>4 6
>3 7
>1 2
>5 10
>4
>1 8
>5 8
>7 10
>8 9
>2 5
>3
>4 6
>3 7
>1 2
>5 10
>4
>1 8
>5 8
>7 10
>8 9
>2 5
>3
>4 6
>3 7
>1 2
>5 10
>4
>1 8
>5 8
>7 10
>8 9
>2 5
>3
>4 6
>3 7
>1 2
>
>
>_______________________________________________
>Tutor maillist  -  Tutor at python.org
>http://mail.python.org/mailman/listinfo/tutor