How to reduce the execution time of a program in python?

2

I've been trying to solve a scheduling problem for a couple of days that involves searching to find the union and the intersection between sets.

I have managed to solve the problem with small sets, but when the set starts getting very large, however much the program arrives in the response, I get a Time limit exceeded.

I made a similar program in c ++ and the code was accepted, but in python it just did not pass ...

I've optimized my program as much as possible, but the runtime has not changed enough ...

My question is:

  • Is there any way to further reduce runtime with python programs?

The problem comes down to given a number of sets. For example

Set 1: - > 1 1

Set 2: - > 2 1 5

Set 3: - > 3 2 4 6

Set 4: > 4 1 3 5 7

And given certain operations between sets return:

(1: Number of elements other than the intersection)

(2: Number of distinct elements of the union)

Example operations:

Case 1: - > 1 1 2 (Intersection between set 1 and set 2)

Case 2: - > 2 1 4 (Union between set 1 and set 4)

Case 3: - > 1 3 4 (Intersection between set 3 and set 4)

Case 4: - > 2 2 4 (Union between set 2 and set 4)

Program I did:

def main():
    # Casos de Teste
    for i in range(int(input())):

        lis = []
        # Quantidade de Conjuntos
        for j in range(int(input())):
            # Lista com todos os números do conjunto
            lis.append(list(map(int, input().split())))

            # O primeiro elemento é a quantidade de números do 
            conjunto
            lis[j].pop(0)

        # Quantidade de operçãoes
        for j in range(int(input())):
            # Operação e conjuntos escolhidos
            op, l1, l2 = map(int, input().split())

            # Interseção
            if(op == 1):
                # -1 por conta do index da lista
                inte = set(lis[l1-1]) & set(lis[l2-1])
                print(len(inte))

            # União
            else:
                union = set(lis[l1-1]) | set(lis[l2-1])
                print(len(union))

if __name__ == "__main__":
    main()

The link to the question is: link

    
asked by anonymous 27.12.2018 / 14:47

1 answer

1

I sent your code as python 3 and it was accepted without any modification ... See below screenshot of the result:

Imadeaversionthatwasalittlefasterthanyours;TosavetimeIdidnotconvertthenumberstointeger,andIalreadygeneratedsetsdirectly(withoutintermediatelists):

T=int(input())#Quantidadedeinstanciasfornum_instanciainrange(T):N=int(input())#Quantidadedeconjuntosconjuntos={str(num_conjunto+1):set(input().split()[1:])fornum_conjuntoinrange(N)}#leosconjuntosQ=int(input())#quantasoperacoesforn_opinrange(Q):tipo,conj1,conj2=input().split()#leaoperacaoiftipo=='1':#intersecaoprint(len(conjuntos[conj1]&conjuntos[conj2]))eliftipo=='2':#uniaoprint(len(conjuntos[conj1]|conjuntos[conj2]))

Result:

    
27.12.2018 / 17:13