djdebonis/doccompare

exploring nlp applications for comparing and contrasting documents

Welcome!

David J DeBonis

doccompare's Issues

algorithm analysis of functions and reducing iteration costs

We are working with extremely expensive functions, especially when we are working with large sets of data. Thus it's important for us to do a bit of algorithm analysis and to determine whether can reduce iteration costs with some steps. Here is the initial function:

def getIntersect(set1, set2):

    intersectSet = []

    for index,ngram in enumerate(set1):
        if ngram not in intersectSet:
            if ngram in set2:
                intersectSet.append(ngram)
 
    return(intersectSet)
        

so here in the first loop we have iteration 1, which we will call n1 of len(set1)

then we have line 2: this iteration size changes as the program progresses, but we know that it cannot iterate more than len(set1) + len(set2) because due to the lines below it is not possible to exceed this because it accounts for all unique values between both. So, let's set n2 = len(set2) and so n3 will be (n1 + n2)

the third line iterates through set2, which we previously decided was the length of n2.

and so our final length is equal to n1 * (n1 + n2) * n2. if n4 is max([len(set1), len(set2)]), then big-oh is O(n4^3)