Comparison of lists of intervals

Question

From the following script, the "similarity" function should be callable to compare two sets of lists and return a certain similarity score. The elements of the lists represent intervals, so [12,16] represents 12, 13, 14, 15 and 16. From the sets, the lists are compared one by one. So the first lists from both sets are compared to each other only, the second lists to each other only, and so on. The sets are to be given in text files, so the input to the "similarity" function would be similar to the following image:

I am wondering how my code could be improved, with regard to runtime, memory usage and readability. I will explain the used functions in greater detail so you know what their general purpose is, though I hope the comments in the code itself are clear enough also.
The "ls" function takes two lists as input and computes a metric based on how many intervals from the first list overlap with at least one interval of the second list. It also checks whether the input is correct.
As this function is sensitive to the order in which the lists are given, it is done for both possible orders. Then the "sym_ls" function is used to take the average of the two outputs.
Then the "ss" function applies the above functions to all the lists of the sets, so the total similarity score between the sets is calculated (an average of the scores of similarity between the individual lists).
Finally, the "similarity" function opens the text files containing the data, cleans out the data so it can be used as input to the "ss" function and then applies this "ss" function, after which the final similarity score is saved to a new text file.

Please let me know what parts of the code could be written more concisely, efficiently and whether the comments are clear or not, and of course how to improve. Eventually the code should be executed by importing the "similarity" function from the .py file, and calling it with correct input arguments.

# import necessary modules
import ast

# define functions needed for similarity computation
def ls(list1, list2):
    '''
    This function determines the similarity between the two given lists, 
    list1 and list2, using overlapping intervals.
    The input (list1 and list2), should be lists containing lists of 2 integers, 
    of which the second integer is greater than the first.
    '''
    
    # overlap variable is set to 0 for every new computation
    overlap = 0
    
    # loop through the intervals to identify the number of intervals in list1 
    # that have an overlap with at least one interval in list2
    for inter1 in list1:
        for inter2 in list2:
            
            # check whether intervals are correclty syntaxed
            if len(inter1) != 2 or len(inter2) != 2:
                print("Error ls: intervals are expected to be represented by two integers, not more or less.")
                break
            elif inter1[0] >= inter1[1] or inter2[0] >= inter2[1]:
                print("Error ls: the first integer representing an interval should be lesser than the second.")
                break
                
            else:
                # determine whether there is overlap
                if inter1[0] >= inter2[0] and inter1[0] <= inter2[1]:
                    overlap += 1
                    break
                elif inter1[1] >= inter2[0] and inter1[1] <= inter2[1]:
                    overlap += 1
                    break
                elif inter1[0] < inter2[0] and inter1[1] > inter2[1]:
                    overlap += 1
                    break
    
    # determine the maximum of the lengths of list1 and list2
    maxlen = max(len(list1), len(list2))
                        
    # compute the similarity (ls)
    ls = overlap / maxlen

    return ls


def sym_ls(ls1, ls2):
    '''
    This function computes the symmetric version of the similarity between two 
    lists. It does so by taking the average of the two similarities.
    The input (ls1 and ls2), should be real numbers in [0,1].
    '''
    
    # check whether input is within the expected range ([0,1])
    if (ls1 < 0 or ls1 > 1) or (ls2 < 0 or ls2 > 1):
        print("Error sym_ls: similarity metrics as input should be a value in [0,1], check the input.")
    else:
        # calculate the average similarity
        symmetric_ls = (ls1 + ls2) / 2
            
    return symmetric_ls


def ss(set1, set2):
    '''
    This function computes the similarity between two sets of lists of intervals. 
    It does so by applying the ls functions on the different set elements. Then, 
    using the sym_ls function, the symmetric similarities are computed. Finally, 
    the global set similarity is calculated and returned as S.
    The input (set1 and set2) should be lists with lists as elements. These list-
    elements have intervals as elements. Both sets should have an equal amount of 
    elements.
    '''
    
    # initialize variable to sum up all symmetric similarity values
    symmetric_similarity_total = 0
    
    # for every ith element of both sets, apply the ls function to them
    # and add the results to the similarity lists
    for i in range(len(set1)):
        symmetric_similarity_total += sym_ls(ls(set1[i], set2[i]), ls(set2[i], set1[i]))
    
    # compute set similarity metric, S
    S = symmetric_similarity_total / len(set1)
    
    return S


def similarity(set_1, set_2, outfile):
    
    # open the textfiles and read in its contents
    set1_data = open(set_1, "r")
    set2_data = open(set_2, "r")
    S1 = set1_data.readlines()
    S2 = set2_data.readlines()
    set1_data.close()
    set2_data.close()
    
    # loop through the set elements to clean up the data
    for i in range(len(S1)): 
        
        # check for equal sizes of sets
        if S1[i][-1] == "\n" and S2[i][-1] != "\n":
            print("Error get_sets: Set1 seems to contain more elements than Set2.")
            break
        elif S1[i][-1] != "\n" and S2[i][-1] == "\n":
            print("Error get_sets: Set2 seems to contain more elements than Set1.")
            break
            
        else:
            # clean the data and convert it to the right type
            S1[i] = list(ast.literal_eval(S1[i].replace("\n", "")))
            S2[i] = list(ast.literal_eval(S2[i].replace("\n", "")))
    
    S = round(ss(S1, S2), 2)
    
    
    # write the similarity metric S to a textfile
    output_file = open(outfile, "x")
    output_file.write("The similarity metric S is: {}".format(S))
    output_file.close()

Answer 1

You asked about performance and complexity. In that regard, the problem is that you naively test each range against each of the other ranges, which gives you O(n²) runtime complexity. Like so:

for inter1 in list1:
    for inter2 in list2:

You can easily improve complexity by using a datastructure that allows fast lookup, like a sorted list with binary search, which results in O(n log n) complexity. Apart from performance, there's a few more issues with your code. Let's start with this piece:

# check whether input is within the expected range ([0,1])
if (ls1 < 0 or ls1 > 1) or (ls2 < 0 or ls2 > 1):
    print("Error sym_ls: similarity metrics as input should be a value in [0,1], check the input.")
else:
    # calculate the average similarity
    symmetric_ls = (ls1 + ls2) / 2

First, you don't need the error check here because it's not a user-visible interface. There is no way how you would end up with a value outside the correct range. This line of code has never been executed and will never be executed. Delete it. Secondly, if you want an error check, use assert. Like this:

assert 0 <= ls1 <= 1
assert 0 <= ls2 <= 1
symmetric_ls = (ls1 + ls2) / 2

This raises an exception when the condition is untrue. You can catch the exception in the interface code that uses the library function and talks to the user through a text-based interface. Never use print inside the library function itself. Your comments are also fairly useless here. Don't comment every line of code. Don't tell us what you do (we see that), tell us why you're doing it. Use comments to explain the edge cases and non-obvious things. Move code into separate functions. A good function name is usually better than a comment. For example, the code that determines if two ranges overlap can be moved into a separate function:

def overlaps(x, y):
    ''' tests if two ranges overlap, bounds inclusive '''
    return x[0] <= y[1] and y[0] <= x[1]

Whenever you call overlaps() from a different piece of code, everyone knows what's going on. You don't need comments anymore. The code became self-explanatory. Next, I have a further nitpick on error handling.

elif inter1[0] >= inter1[1] or inter2[0] >= inter2[1]:
    print("Error ls: the first integer representing an interval should be lesser than the second.")
    break

In my opinion, a range with the upper bound less than the lower bound is perfectly valid. You shouldn't throw an error if the user gives you a range like (5, 3). A mathematician would write such a set as

$$ \left\{ x \in \mathbb{Z},\quad 5 \le x \le 3\right\} = \emptyset $$

and conclude it's an empty set. The empty set never overlaps with anything, not even with itself, so we should silently ignore it. You can use a somewhat modified overlaps() function that handles the empty set correctly and always returns false.

def overlaps(x, y):
    ''' tests if two ranges overlap, bounds inclusive '''
    return max(x[0], y[0]) <= min(x[1], y[1])

Finally, the most glaring problem with your code are the function names. Why would you name a function ss or ls? Give them proper names.

---

Here is an improved version of your business logic. It uses sorted lists and binary search, list comprehensions (which are incredibly concise and readable), useful function names with docstrings and only two (but useful) comments. This code also separates the algorithm from the interface (I didn't rewrite the interface here).

from bisect import bisect

def symmetric_similarity(list1, list2):
    ''' computes the symmetric similarity between two lists of ranges '''
    unique1 = sorted_unique(list1)
    unique2 = sorted_unique(list2)
    valid1 = [x for x in list1 if overlaps_any(x, unique2)]
    valid2 = [x for x in list2 if overlaps_any(x, unique1)]
    return (len(valid1) + len(valid2)) / max(len(list1), len(list2)) / 2

def overlaps_any(x, ys):
    ''' tests if x overlaps with any y, ys must be sorted, non-empty, non-overlapping '''
    i = bisect(ys, x)
    # bisect returns the index where x would be inserted into ys, so we
    # have to compare it against the ys before and after that point.
    return i > 0 and overlaps(x, ys[i-1]) or i < len(ys) and overlaps(x, ys[i])

def overlaps(x, y):
    ''' tests if two ranges overlap, bounds inclusive '''
    return max(x[0], y[0]) <= min(x[1], y[1])

def sorted_unique(ranges):
    ''' sorts, removes empty ranges, then merges overlapping ranges '''
    ranges = [x for x in sorted(ranges) if overlaps(x, x)]
    unique = list(ranges[:1])
    for x in ranges:
        if overlaps(unique[-1], x):
            # The lower bound is correct because we sorted, but we have to
            # take the maximum of the upper bounds to merge the ranges.
            unique[-1] = unique[-1][0], max(unique[-1][1], x[1])
        else:
            unique.append(x)
    return unique

If you don't need the binary search, everything reduces to just a few lines of code. It's beautifully simple and reads almost like plain English, even without comments.

def symmetric_similarity(list1, list2):
    ''' computes the symmetric similarity between two lists of ranges '''
    valid1 = [x for x in list1 if overlaps_any(x, list2)]
    valid2 = [x for x in list2 if overlaps_any(x, list1)]
    return (len(valid1) + len(valid2)) / max(len(list1), len(list2)) / 2

def overlaps_any(x, ys):
    ''' tests if x overlaps with any y '''
    return any(overlaps(x, y) for y in ys)

def overlaps(x, y):
    ''' tests if two ranges overlap, bounds inclusive '''
    return max(x[0], y[0]) <= min(x[1], y[1])

If you want to win the price for compactness, you can reduce it even further:

def symmetric_similarity(list1, list2):
    ''' computes the symmetric similarity between two lists of ranges '''
    count1 = sum(any(overlaps(x, y) for y in list2) for x in list1)
    count2 = sum(any(overlaps(x, y) for y in list1) for x in list2)
    return (count1 + count2) / max(len(list1), len(list2)) / 2

def overlaps(x, y):
    ''' tests if two ranges overlap, bounds inclusive '''
    return max(x[0], y[0]) <= min(x[1], y[1])