Advertisement
husoski

GFG Common Elements, with timing

Nov 24th, 2022 (edited)
634
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.85 KB | Software | 0 0
  1. class Solution:
  2.        
  3.     # Version shared by okitsme_Parth:
  4.     def commonElements0(self,A, B, C, n1, n2, n3):
  5.         a = 0
  6.         b = 0
  7.         c = 0
  8.         r = []
  9.         while a < n1 and b < n2 and c < n3:
  10.             if A[a] == B[b] == C[c]:
  11.                 if A[a] not in r:
  12.                     r.append(A[a])
  13.                 a += 1
  14.                 b += 1
  15.                 c += 1
  16.             elif A[a] < B[b]:
  17.                 a += 1
  18.             elif B[b] < C[c]:
  19.                 b += 1
  20.             else:
  21.                 c += 1
  22.                
  23.         return sorted(r) if r else [-1]
  24.  
  25.     # My refactored version based on okitsme_Parth's:
  26.     def commonElements1(self,A, B, C, n1, n2, n3):
  27.         i1 = i2 = i3 = 0
  28.         result = []
  29.         while i1 < n1 and i2 < n2 and i3 < n3:
  30.             if A[i1] < B[i2]:
  31.                 i1 +=1
  32.             elif B[i2] < C[i3]:
  33.                 i2 += 1
  34.             elif C[i3] < A[i1]:
  35.                 i3 += 1
  36.             else:
  37.                 result.append(A[i1])
  38.                 i1 += 1
  39.                 i2 += 1
  40.                 i3 += 1
  41.                
  42.         return result
  43.  
  44.     # I didn't like doing 3 comparisons every time one index value changed,
  45.     # or indexing the array when the index value hadn't changed.
  46.     # This is my stab at using iterators to rememdy that and get out of the
  47.     # main loop as soon as any list hits the end.
  48.    
  49.     # I also added while loops in the "else:" clause to eliminate duplicate
  50.     # values.  The statement is (IMHO) not clear about whether duplicates are
  51.     # possible within the lists, but the reference solution appears to
  52.     # return only unique values.
  53.  
  54.     def commonElements2(self, A, B, C, n1, n2, n3):
  55.         result = []
  56.         i1, i2, i3 = iter(A), iter(B), iter(C)
  57.        
  58.         try:
  59.             x1, x2, x3 = next(i1), next(i2), next(i3)
  60.             while True:
  61.                 if x1 < x2:
  62.                     x1 = next(i1)
  63.                 elif x2 < x3:
  64.                     x2 = next(i2)
  65.                 elif x3 < x1:
  66.                     x3 = next(i3)
  67.                 else:
  68.                     result.append(x1)
  69.                     while x2 == x1: x2 = next(i2)
  70.                     while x3 == x1: x3 = next(i3)
  71.                     while x1 < x2: x1 = next(i1)
  72.  
  73.         except StopIteration:
  74.             pass
  75.    
  76.         return result
  77.  
  78.     commonElements = commonElements1 ### Reference solution
  79.  
  80. # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  81. # Test code
  82.  
  83. import timeit
  84. import random
  85.  
  86. def random_select(seq, p=0.5):
  87.     R = random.random
  88.     return filter(lambda x: R()<p, seq)
  89.  
  90. A = list(random_select(range(100000), .1))
  91. B = list(random_select(range(100000), .1))
  92. C = list(random_select(range(100000), .1))
  93. nA = len(A)
  94. nB = len(B)
  95. nC = len(C)
  96. S = Solution()
  97.  
  98. result = S.commonElements(A, B, C, nA, nB, nC)
  99. r0 = S.commonElements0(A, B, C, nA, nB, nC)
  100. r1 = S.commonElements1(A, B, C, nA, nB, nC)
  101. r2 = S.commonElements2(A, B, C, nA, nB, nC)
  102. assert r0 == result, 'mismatch in r0'
  103. assert r1 == result, 'mismatch in r1'
  104. assert r2 == result, 'mismatch in r2'
  105.  
  106.  
  107. t0 = timeit.timeit(
  108.         stmt='S.commonElements0(A, B, C, nA, nB, nC)',
  109.         setup='from __main__ import S, A, B, C, nA, nB, nC',
  110.         number=100)
  111. t1 = timeit.timeit(
  112.         stmt='S.commonElements1(A, B, C, nA, nB, nC)',
  113.         setup='from __main__ import S, A, B, C, nA, nB, nC',
  114.         number=100)
  115. t2 = timeit.timeit(
  116.         stmt='S.commonElements2(A, B, C, nA, nB, nC)',
  117.         setup='from __main__ import S, A, B, C, nA, nB, nC',
  118.         number=100)
  119.  
  120. print('Time (in seconds) to run 100 times on list sizes', (nA,nB,nC))
  121. print('  with', len(result), 'items in common:')
  122. print('Original:       ', round(t0, 3))
  123. print('Refactored:     ', round(t1, 3))
  124. print('Using iterators:', round(t2, 3))
  125.  
  126.  
Advertisement
Comments
  • husoski
    5 days
    # text 0.20 KB | 0 0
    1. - - - - Sample output:
    2. Time (in seconds) to run 100 times on list sizes (10037, 9991, 10061)
    3. with 104 items in common:
    4. Original: 0.431
    5. Refactored: 0.34
    6. Using iterators: 0.169
    7. - - - -
    8.  
Add Comment
Please, Sign In to add comment
Advertisement