Find common list in three lists

find_common.py

from random import random
import time
import sys

def findCommon_NNN(A,B,C):

    if 1000<len(A) or 1000<len(B) or 1000<len(C):
        print("# This may be huge input for this function with O(N^3). Exit.")
        return []

    common = []
    for a in A:
        for b in B:
            for c in C:
                if a==b and b==c:
                    if a not in common:
                        common.append(a)
    return common

def findCommon_N(A,B,C):
    i=j=k=0
    common = []
    while i<len(A) and j<len(B) and k<len(C):
        if A[i]==B[j] and B[j]==C[k]:
            common.append(A[i])
        m = min(A[i],B[j],C[k])
        if A[i]==m:
            i+=1
        if B[j]==m:
            j+=1
        if C[k]==m:
            k+=1

    return common

def binary_search(C,n):
    s=0
    e=len(C)-1
    if C[s]==n or C[e]==n: return True

    m=int((s+e)/2)
    while s<m and m<e:
        if C[m]==n: return True
        if C[m]<n:
            s=m
        else:
            e=m
        m=int((s+e)/2)
    return False

def findCommon_N_L_BS(A,B,C):
    i=j=0
    common = []
    while i<len(A) and j<len(B):
        if A[i]==B[j]:
            common.append(A[i])
        m = min(A[i],B[j])
        if A[i]==m:
            i+=1
        if B[j]==m:
            j+=1

    common2 = []
    for c in common:
        if binary_search(C,c):
            common2.append(c)

    return common2

def findCommon_N_L(A,B,C):
    i=j=0
    common = []
    while i<len(A) and j<len(B):
        if A[i]==B[j]:
            common.append(A[i])
        m = min(A[i],B[j])
        if A[i]==m:
            i+=1
        if B[j]==m:
            j+=1

    common2 = []
    for c in common:
        if c in C:
            common2.append(c)

    return common2

def make_seqs(n):
    i=0
    seq = []
    while len(seq)<n:
        if int(random()*2)<1:
            seq.append(i)
        i+=1
    return seq


def make_seqs_sparse(n):
    i=0
    seq = []
    while len(seq)<n:
        if int(random()*10)<1:
            seq.append(i)
        i+=1
    return seq

if __name__ == "__main__":

    if 1 < len(sys.argv):
        n = int(sys.argv[1])
    else:
        n = 10

    print("Preparing data...")
    A = make_seqs(n)
    B = make_seqs(n)
    C = make_seqs(n)

    print("Preparing data for sparse one...")
    A_ = make_seqs_sparse(n)
    B_ = make_seqs_sparse(n)
    C_ = make_seqs(n*10)
    
    if len(A)<=10:print(A)
    if len(B)<=10:print(B)
    if len(C)<=10:print(C)
    
    print("### Try normal sequence first and then try sparse one.")
    for data in [[A,B,C], [A_,B_,C_]]: 
        pre_commons=[]
        commons=[]
        for f in [findCommon_NNN,findCommon_N,findCommon_N_L_BS,findCommon_N_L]:
            s = time.time()
            commons = f(*data)
            e = time.time()
            print("{:>20} : {:.2f} sec".format(f.__name__,(e-s)))
            if pre_commons != []:
                if not pre_commons==commons:
                    print("The result should be same.")
                    print(*data)
                    print(pre_commons)
                    print(commons)
                    exit(-1)
            pre_commons = commons.copy()
       
        print(commons if len(commons)<100 else "" )

$ python --version
Python 3.5.0
$ for n in `seq 0 5`;do python find_common.py 50;done
Preparing data...
Preparing data for sparse one...
### Try normal sequence first and then try sparse one.
      findCommon_NNN : 0.00 sec
        findCommon_N : 0.00 sec
   findCommon_N_L_BS : 0.00 sec
      findCommon_N_L : 0.00 sec
[1, 6, 37, 46, 52, 53, 60, 62, 85, 98, 99, 108]
      findCommon_NNN : 0.04 sec
        findCommon_N : 0.00 sec
   findCommon_N_L_BS : 0.00 sec
      findCommon_N_L : 0.00 sec
[85]
Preparing data...
Preparing data for sparse one...
### Try normal sequence first and then try sparse one.
      findCommon_NNN : 0.01 sec
        findCommon_N : 0.00 sec
   findCommon_N_L_BS : 0.00 sec
      findCommon_N_L : 0.00 sec
[5, 7, 11, 33, 46, 54, 64, 74, 79, 84]
      findCommon_NNN : 0.04 sec
        findCommon_N : 0.00 sec
   findCommon_N_L_BS : 0.00 sec
      findCommon_N_L : 0.00 sec
[]
Preparing data...
Preparing data for sparse one...
### Try normal sequence first and then try sparse one.
      findCommon_NNN : 0.00 sec
        findCommon_N : 0.00 sec
   findCommon_N_L_BS : 0.00 sec
      findCommon_N_L : 0.00 sec
[0, 3, 5, 6, 20, 24, 26, 34, 42, 61, 62, 74, 82]
      findCommon_NNN : 0.05 sec
        findCommon_N : 0.00 sec
   findCommon_N_L_BS : 0.00 sec
      findCommon_N_L : 0.00 sec
[121, 160]
Preparing data...
Preparing data for sparse one...
### Try normal sequence first and then try sparse one.
      findCommon_NNN : 0.01 sec
        findCommon_N : 0.00 sec
   findCommon_N_L_BS : 0.00 sec
      findCommon_N_L : 0.00 sec
[5, 10, 22, 23, 36, 41, 43, 44, 49, 53, 55, 62, 69, 70, 79, 80, 88, 94]
      findCommon_NNN : 0.05 sec
        findCommon_N : 0.00 sec
   findCommon_N_L_BS : 0.00 sec
      findCommon_N_L : 0.00 sec
[39, 52]
Preparing data...
Preparing data for sparse one...
### Try normal sequence first and then try sparse one.
      findCommon_NNN : 0.01 sec
        findCommon_N : 0.00 sec
   findCommon_N_L_BS : 0.00 sec
      findCommon_N_L : 0.00 sec
[11, 12, 13, 34, 57, 64, 70, 72, 79, 84, 102]
      findCommon_NNN : 0.05 sec
        findCommon_N : 0.00 sec
   findCommon_N_L_BS : 0.00 sec
      findCommon_N_L : 0.00 sec
[220]
Preparing data...
Preparing data for sparse one...
### Try normal sequence first and then try sparse one.
      findCommon_NNN : 0.00 sec
        findCommon_N : 0.00 sec
   findCommon_N_L_BS : 0.00 sec
      findCommon_N_L : 0.00 sec
[0, 1, 3, 4, 17, 18, 41, 51, 53, 60, 77]
      findCommon_NNN : 0.05 sec
        findCommon_N : 0.00 sec
   findCommon_N_L_BS : 0.00 sec
      findCommon_N_L : 0.00 sec
[87, 109, 243]

$ python find_common.py 100000
Preparing data...
Preparing data for sparse one...
### Try normal sequence first and then try sparse one.
# This may be huge input for this function with O(N^3). Exit.
      findCommon_NNN : 0.00 sec
        findCommon_N : 0.19 sec
   findCommon_N_L_BS : 0.52 sec
      findCommon_N_L : 57.09 sec

# This may be huge input for this function with O(N^3). Exit.
      findCommon_NNN : 0.00 sec
        findCommon_N : 0.57 sec
   findCommon_N_L_BS : 0.24 sec
      findCommon_N_L : 95.91 sec