CODEWITHSUNDEEP
pythonlistalgorithmperformance
Checkmate1941
Checkmate1941

Reputation: 45

How to improve efficiency of appending to and then checking for subsequent elements in list

i'm attempting to solve: http://orac.amt.edu.au/cgi-bin/train/problem.pl?problemid=980&set=aio17int

The algorithm exceeds the time limit for larger files. I'm fairly new to python, and can't find a more efficient solution online for checking if an element is in a list and then appending accordingly. Please help improve the speed without using any imports. Thank you.

input file:

8 5
2 7
1 8
8 4
7 5
8 6

re = 1
bl = 1
red = [1]
blue = [2]
input_file = open("tagin.txt","r")
n, m = map(int, input_file.readline().split())
for i in range(m):
    a, b = map(int, input_file.readline().split())
    if a in red:
        red.append(b)
        re+=1
    elif a in blue:
        blue.append(b)
        bl+=1

output_file = open("tagout.txt", "w")
output_file.write(str(re) + " " + str(bl))
output_file.close()

output file:

4 3

Also please advise if stack overflow is the wrong platform to ask this question, if so what should I use?

Upvotes: 1

Views: 69

Answers (2)

Adon Bilivit
Adon Bilivit

Reputation: 27114

If I understand the problem correctly then this should fulfil the objective:

with open('tagin.txt') as tagin:
    _, M = map(int, next(tagin).split())
    red = {1}
    blue = {2}
    for _ in range(M):
        a, b = map(int, next(tagin).split())
        (red if a in red else blue).add(b)
    print(len(red), len(blue))

Output:

4 3

Upvotes: 2

trincot
trincot

Reputation: 350715

Some things you can improve:

  • Use a set instead of a list for collecting team members. That will increase the efficiency of the in operator.

  • There is no need to keep track of the size of the team, as you can get that with the len function

  • Only collect the members of one team. We can derive the size of the other team from m, which represents how many people get tagged. If we add 2 to that, we also take into account the first two which are already tagged. Subtract from that the size of one team, and you get the size of the other.

Code:

input_file = open("tagin.txt","r")
n, m = map(int, input_file.readline().split())
red = {1}  # A set, only for the red team
for i in range(m):
    a, b = map(int, input_file.readline().split())
    if a in red:  # Better efficiency as red is now a set
        red.add(b)

output_file = open("tagout.txt", "w")
# Size of blue team can be deduced from what we already know:
output_file.write(str(len(red)) + " " + str(m + 2 - len(red)))
output_file.close()

Upvotes: 2

Related Questions