Generator function to find common lines between two files

Question

I am reading Python Object-oriented programming by Steven and Dusty.

I am at Chapter 10, and it's all about Iterator design pattern. At the end of chapter there is an exercise to write generator function/expression to find common lines between two files.

Here are my naive approaches:

old = os.path.normpath('E:/testing/old.txt')
new = os.path.normpath('E:/testing/new.txt')
res = []

def func(source):
    for line in source.readlines():
        yield line

Approach 1:

with open(old, "r") as f:
    for line in func(f):
        with open(new, "r") as _f:
            for _line in func(_f):
                if line == _line:
                    res.append(line)

Approach 2:

with open(old, "r") as f:
    for line in func(f):
        with open(new, "r") as _f:
            res.extend(filter(lambda a: line == a, func(_f)))

Context:

Now, let's think about totally different problem, let's assume we have list of strings instead of files with n and m elements, we can find common strings in O(n) time complexity with O(m) space.

Big questions

1. Is there any better pythonic approach to re-factor above codes?
2. I know generators are all about saving space and state, but following the above context, is there a better way in terms of time complexity to compare two files and find common lines.

My end goal is to optimize my code (if it is possible) in terms of time and space complexity and to make it more pythonic.

P.S. - Can someone point me to the source code of linux diff command and git-diff source code.

I tried finding source code of linux diff and git-diff but was unable to.

Answer 1

I don't believe this problem is best solved using generators. My approach would be:

old = 'E:/testing/old.txt'
new = 'E:/testing/new.txt'

with open(old) as f:
    old_lines = set(f) # A set of lines

with open(new) as f:
    matches = [line for line in f if line in old_lines]

print(matches)

If you want to compare lines stripped of the trailing newline character (since the last line may not have a trailing newline), then you could use the following code, which also demonstrates creating two sets and doing an "intersection" operation on them. In that way you do not have to explicitly loop through lines. But by creating two sets and computing their intersection you lose control over the order in which matches will be printed. It will also be less memory efficient and not run any faster (perhaps even a bit more slowly) compared with the first solution. Finally, if any of the files contain duplicated lines, you will compute a different, smaller set of changes.

old = 'E:/testing/old.txt'
new = 'E:/testing/new.txt'

with open(old) as f:
    old_lines = set(line.strip('\n') for line in f) # A set of lines

with open(new) as f:
    matches = set(line.strip('\n') for line in f) & old_lines

print(matches)

Answer 2

As far as I know, there is no python-specific approach. However, as pointed out in other answers, set.intersection is efficient way to do it, so chunked loading is also worth a try.

def chunked_reader(fo: TextIO, chunk_size: int):
    while True:
        lines = fo.readlines(chunk_size)
        if not lines:
            break
        # Uncomment this if the trailing newline is an issue.
        # lines = [l.strip("\n") for l in lines]
        yield lines


def intersect_files(path1: str, path2: str, chunk_size: int):
    results = []
    with open(path1) as f1, open(path2) as f2:
        for l1 in chunked_reader(f1, chunk_size):
            f2.seek(0)
            l1 = set(l1)
            for l2 in chunked_reader(f2, chunk_size):
                results.extend(l1.intersection(set(l2)))
    return results

intersect_files reads chunk_size bytes from both files and compares them. The smaller the chunk_size, the less memory used; the larger the chunk_size, the fewer repeated file reads. If chunk_size is larger than the file, both files are read only once.

However, note that the order of the results will change depending on the chunk_size.

Answer 3

Finding common lines is not exactly the same problem as comparing for differences. Comparing differences would have to take the order of lines into account, but common lines is merely a set membership problem.

You can actually use a set to implement it:

with open(old) as f:
    oldLines = set(f)  # O(m) space

with open(new) ad f:
    common = (line for line in f if line in oldLines)  # O(n) time

If you need to count repetitions in the old and new as distinct occurrences, then use the Counter class from collections instead of a set.

from collections import Counter

with open(old) as f:
    oldLines = Counter(f)  # O(m) space

with open(new) ad f:
    common = ( oldLines.subtract([line]) or line for line in f 
               if oldLines[line] > 0 ) 

Answer 4

Edit: This answer is suboptimal for space complexity, see Booboo's answer.

If I were you, I would use a set, they can do membership testing in (almost) constant time. some_set.intersection(some_other_set) yields their common members. It's really fast because they use hashtables.