How can you speed up?

a=input() aa=[int(s) for s in input().split()] b=input() bb=[int(s) for s in input().split()] c=input() cc=[int(s) for s in input().split()] sum=0 for i in aa: if i in bb and i in cc: sum+=1 print(sum)
  • one
    This is a question on the label [inspection code]. Must contain only working code. If you have a question "why does not work" - do not put this label. Be sure to describe the implemented functionality and the purpose of the code. Use a standard coding style for a language - function and variable names, padding, spaces, and so on. Detailed instructions are in the full description. See label description [Inspection Code] - Kromster

1 answer 1

Take advantage of the sets.

Example:

 aa = [1, 3, 1, 5, 7, 9] bb = [1,2,3,4] cc = [1,3,10] chk = set(bb) & set(cc) print(chk) #{1, 3} res = sum(x in chk for x in aa) print(res) #3

The average complexity of testing x in set is O(1) , while the complexity of testing x in list is O(n) .

Comparison of execution speed for arrays consisting of 10,000 elements:

 In [3]: %paste from random import randint N = 10**4 aa = [randint(0,1000) for _ in range(N)] bb = [randint(0,10**7) for _ in range(N)] cc = [randint(0,10**9) for _ in range(N)] ## -- End pasted text -- In [4]: %paste %%timeit sm=0 for i in aa: if i in bb and i in cc: sm+=1 ## -- End pasted text -- 3.74 s ± 46.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) In [5]: %paste %%timeit chk = set(bb) & set(cc) res = sum(x in chk for x in aa) ## -- End pasted text -- 5.16 ms ± 33.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

speed difference:

 In [6]: 3.74 * 1000 / 5.16 Out[6]: 724.8062015503875