Python efficiency for list comparison on numbers >= 10,000
Question: I've been trying to complete a problem from one of the most recent ACM
programming challenges post competition, and have been running into a snag.
The problem states

> Your team has been retained by the director of a competition who supervises
> a panel of judges. The competition asks the judges to assign integer scores
> to competitors – the higher the score, the better. Although the event has
> standards for what score values mean, each judge is likely to interpret
> those standards differently. A score of 100, say, may mean different things
> to different judges.
>
> The director's main objective is to determine which competitors should
> receive prizes for the top positions. Although absolute scores may differ
> from judge to judge, the director realizes that relative rankings provide
> the needed information – if two judges rank the same competitors first,
> second, third, ... then they agree on who should receive the prizes.
>
> Your team is to write a program to assist the director by comparing the
> scores of pairs of judges. The program is to read two lists of integer
> scores in competitor order and determine the highest ranking place (first
> place being highest) at which the judges disagree.
>
> Input to your program will be a series of score list pairs. Each pair begins
> with a single integer giving the number of competitors N, 1 < N < 1,000,000.
> The next N integers are the scores from the first judge in competitor order.
> These are followed by the second judge's scores – N more integers, also in
> competitor order. Scores are in the range 0 to 100,000,000 inclusive. Judges
> are not allowed to give ties, so each judge’s scores will be unique. Values
> are separated from each other by one or more spaces and/or newlines. The
> last score list pair is followed by the end-of-file indicator.

There were example test cases which cover N = 4, and N = 8

> 4
>
> 3 8 6 2
>
> 15 37 17 3
>
> 8
>
> 80 60 40 20 10 30 50 70
>
> 160 100 120 80 20 60 90 135

And the Expected Output: For each score pair, print a line with the integer
representing the highest-ranking place at which the judges do not agree. If
the judges agree on every place, print a line containing only the word
"agree". Use the format below: "Case", one space, the case number, a colon and
one space, and the answer for that case with no trailing spaces.

> Case 1: agree
>
> Case 2: 3

My Code is as follows:

    
    
    import sys
    
    def calculate(competitors, scores1, scores2):
        scores1sort = sorted(scores1, reverse = True)
        scores2sort = sorted(scores2, reverse = True)
    
        for x in range(len(scores1)) :
            indexed1 = scores1.index(scores1sort[x])
            #print ('place: ', x+1, 'Position: ',indexed1+1)
        #iterating over the entire length  of the sorted lists multiple times takes too long
            indexed2 = scores2.index(scores2sort[x])
            #print ('place: ', x+1, 'Position: ',indexed2+1)
            if indexed2 != indexed1 :
                print ( "Case",  str(case) + ":", x+1)
                return
    
        #run both fors at the same time, compare indexed of scores1 to index of scores2
        #if the position(indexed + 1) doesnt match between the two, print the place(x+1) of the disparity
    
    
        #if match:
            #print ("Case " + case +": " + "agree"
        #else: print (Case " + case + ": " + index of disagreement
    
        print ("Case", str(case) + ":" , "agree")
    
    
    
        scores1 = [];
        scores2 = [];
        case = 1;
        state = 0;
        # 0 indicates number of competitors
        # 1 indicates judge 1
        # 2 indicates judge 2
        #for line in sys.stdin:
        for line in test.split("\n"):
            line = line.strip().split()
            if not line:
                continue
    
        if state == 0:
            #if empty line, error
            competitors = int(line[0])
            state = 1;
    
        else:
            for y in line:
                if state == 1:
                    scores1.append(int(y))
                    if len(scores1) >= competitors:
                        state = 2;
                elif state == 2:
                    scores2.append(int(y))
                    if len(scores2) >= competitors:
                        state = 0;
                        #print (competitors, score1, scores2)
                        calculate(competitors, scores1, scores2);
                        case += 1;
    

My code is currently run using a text file containing test input from the
programming contest that was left for us, which includes small test values,
but also includes a set of values with 10,000 competitors.

I have no doubt that the code could complete if given enough time, but the
programming challenge guidelines specified that the code had to run in a
window of time shorter than the current runtime.

As such I'd like to ask for any tips anyone might have on how to optimize my
code for faster execution.


Answer: Providing sample input will help a bit. At this point, seems that you are
loosing time at index method call and memory alloc in range(in case of running
at py2). Try using _enumerate_ to avoid indexing.

