Shorten runtime of this Python program

Question

This is an answer to this question on Code-Golf.SE (but obviously not golfed). How can I shorten the runtime of my program? It is taking far too long to run some of the test cases. Can I utilise Python map() or lambda?

def main():

    # Store number of test cases
    T = int(input())

    # Loop for each test case:
    for testCase in range(0, T):

        # Store number of members each team can have
        N = int(input())

        # Store power of beyblades of Team G-Revolution members
        teamG_beybladePowers = [int(x) for x in input().split()]

        # Store power of beyblades of opponent team members
        opponentBeybladePowers = [int(x) for x in input().split()]

        # Store the calculated order of our team members as a list
        teamG_calculatedOrder = []
        # Store the caclulated order of opponent team members as a list
        opponentCalculatedOrder = []

        # Loop through each of the team members and opponent team members, and match them
        for index in range(0, N):

            # Check if Team G's highest beyblade power is lower than or equal to opponent's highest
            if max(teamG_beybladePowers) <= max(opponentBeybladePowers):

                # Team G's highest beyblade power is weaker than opponent's highest.
                # We need not waste our best player on their best player, when we will lose.
                # Match our lowest player against their highest player.
                teamG_calculatedOrder.append(min(teamG_beybladePowers))
                opponentCalculatedOrder.append(max(opponentBeybladePowers))

                # Remove these members from original list
                teamG_beybladePowers.remove(min(teamG_beybladePowers))
                opponentBeybladePowers.remove(max(opponentBeybladePowers))

            else:
                # Team G's highest beyblade power is more than opponent's highest.
                # We can use our best player to beat the opponent's best player.
                # Match them up:
                teamG_calculatedOrder.append(max(teamG_beybladePowers))
                opponentCalculatedOrder.append(max(opponentBeybladePowers))

                # Remove these members from the original list
                teamG_beybladePowers.remove(max(teamG_beybladePowers))
                opponentBeybladePowers.remove(max(opponentBeybladePowers))

        # Store total number of wins
        totalWins = 0

        # Calculate number of wins
        for index in range(0, N):

            # Check if current match was won
            if teamG_calculatedOrder[index] > opponentCalculatedOrder[index]:
                # This match was won
                # Increment total wins:
                totalWins += 1

            else:
                # This match was lost
                pass

        # Print total number of wins
        print(totalWins)

main()

Answer 1

Specific suggestions

1. Using command-line arguments is the idiomatic way to collect input. This makes the code scriptable and reusable as a library.

2. The idiomatic way to run main is this:

   if __name__ == "__main__":
       main()
   

3. Several bits of code are duplicated, such as min(teamG_beybladePowers). Pull those out into variables to avoid re-iterating through the whole list more than necessary.

Tool support suggestions

1. black can automatically format your code to be more idiomatic. It'll do things like adjusting the vertical and horizontal spacing, while keeping the functionality of the code unchanged. In your case the code does look decently formatted, so it may not change much (or at all).

2. flake8 can give you hints to write idiomatic Python. I would start with this configuration:

   [flake8]
   max-complexity = 4
   ignore = W503,E203
   

Answer 2

Presuming that you are not asking for code-golfing recommendations, here are a few observations.

It would be better to separate the input operations from the code that determines the number of winning matches. For example, separating the concerns lets you test the input code separately from the calculating code. Or lets you change where the input comes from: the command line, a file, a url, user input on a web page, etc.

The current code has a O(n^2) complexity. It is obvious that the outer for index in range(0, N) loop runs N times. What may not be so obvious is that each call to min, max, and remove also processes the entire list, for another N times (and there are 8 calls each time through the outer loop). That's O(N * 8N) = O(N^2). So if the length of the lists is doubles, the time spent on the loop goes up by about 4 times. (The lists get shorter each loop, so in the average, min etc. process half the loop but O(N * 8N/2) is still O(N^2)). Sorting the lists would be O(N log N).

The second loop that counts the wins can be eliminated. You already know that you win the match in the else clause of the first loop. Just count the winners there.

Lastly, it is not necessary to actually make the pairings to determine how many would be won.

Put that together, and you get something like:

def calculate_winners(us, them):
    """count how many matches we would win by choosing 
       which wrestlers to pair up.
    """
    us = sorted(us, reverse=True)     # largest to smallest
    them = sorted(them, reverse=True)

    winners = 0
    us_index = 0
    for opponent in them:
        if us[us_index] > opponent:
            winners += 1
            us_index += 1

    return winners