Group duplicate files (part 3)

Question

This is a continued discussion (from here => Group duplicate files (part 2)) with new code and new thoughts/questions (see special question part for details for new questions), and I decide to make a new post.

Here is my source code which group duplicate files together, written in Python 2.7. Any advice on smarter ideas to group duplicate files together more efficient, it will be great. Any general advice on code bugs and code style are also appreciated.

Problem statement:

I am given a list of files e.g. ["1.txt", "2.txt", "3.txt", "4.txt", "5.txt", "6.txt"]. I want to group all files which have the exact same content. Suppose in this example, file "1.txt", "2.txt", "3.txt" are the same, file "4.txt", "5.txt", "6.txt" have common header, but "4.txt", "6.txt" are exactly the same whole content. Then, the output should be two groups "1.txt", "2.txt", "3.txt" and "4.txt", "6.txt".

My major idea:

1. To avoid reading full content for each file, I generate a hash code for a piece of a file (in my example, I define the piece of file to be the 10 bytes of a file)
2. Each time after reading the next 10 bytes, I will hash the content of the next 10 bytes, and combine the hash value (of the next 10 bytes) with existing hash value of a file
3. Each time I see there is no common hash value for a file, I will stop reading this file from next piece (del file_handle_map[f])
4. The whole algorithm complete when all files are read

Special question

In method hash_next_n_bytes, I will return -1 if file already reached end (EOF), but sure if there is any better way to represent it, since I think -1 may conflict with some valid hash value -1?

Source code in Python 2.7

from collections import defaultdict
def group_duplicate_files(files):
    # open all filee
    file_handle_map = defaultdict(file)
    file_hash_map = defaultdict(int)
    for f in files:
        file_handle_map[f] = open(f, "r")
    while True:
        terminate = True
        group_map = defaultdict(list)
        for file_name, file_handle in file_handle_map.items():
            h = hash_next_n_bytes(file_handle, 10)
            if h != -1:
                terminate = False
                file_hash_map[file_name] = hash(file_hash_map[file_name]+h)
            group_map[file_hash_map[file_name]].append(file_name)
        remove_list = []
        for h, file_list in group_map.items():
            if len(file_list) == 1:
                remove_list.append(file_list[0])
        for f in remove_list:
            del file_handle_map[f]
        if terminate:
            break
    for h in file_handle_map.values():
        h.close()
    return group_map

def hash_next_n_bytes(f,n):
    x = f.read(n)
    if x:
        return hash(x)
    else:
        return -1

if __name__ == "__main__":
    files = ["1.txt", "2.txt", "3.txt", "4.txt", "5.txt", "6.txt"]
    print group_duplicate_files(files)

Answer 1

• hash_next_n_bytes can return None in case of EOF

• You close the remaining files at the end of group_duplicate_files, but you just del file_handle_map[f] in the while loop. You don't have to close the files, their __del__ method will take care of it when the function returns.

• Instead of

  while True:
      terminate = True
      ...
      if terminate:
          break
  

  you can do

  terminate = False
  while not terminate:
      terminate = True
      ...
  

• No need to make file_handle_map a defaultdict, it can be just dict.

---

Some optimization suggestions:

• You can initialize the hash with sizes of files. That way, you will avoid comparing large files with many common leading bytes.
• It might just be faster to calculate some simple checksum (MD5 or so) of a larger portion of the file. Alternately reading 10 bytes from many different files and calling hash on each result will likely be inefficient.