Duplicate File Finder in python

Question

I just started learning python yesterday, I have prior experience of C++. So I think I am able to get most of it pretty fast. I wrote a duplicate file finder for testing and practicing.

Can you guys look on this and give me some opinion if I am doing this right?

import argparse
import os
import fnmatch
import hashlib

class MyFile:
    partHashSize = 0
    def __init__(self, name):
        self.name = name
        self.size = os.path.getsize(self.name)
        self._processed = False
        self._partHash = None
        self._fullHash = None

    def __str__(self):
        return '{} is {}'.format(self.name, self.size)
    def __repr__(self):
        return '<MyFile {}:{}>'.format(self.name, self.size)

    def _getPartHash(self):
        if self._partHash is None:
            h = hashlib.sha1()
            with open(self.name, 'rb') as f:
                h.update(f.read(MyFile.partHashSize))
            self._partHash = h.hexdigest()
        return self._partHash
    partHash = property(_getPartHash)

    def _getFullHash(self):
        if self._fullHash is None:
            h = hashlib.sha256()
            with open(self.name, 'rb') as f:
                while True:
                    buf = f.read(MyFile.partHashSize)
                    if not buf:
                        break
                    h.update(buf)
                self._fullHash = h.hexdigest()
        return self._fullHash
    fullHash = property(_getFullHash)

    def findDuplicates(self, files):
        if self._processed:
            return list()
        dup = list()
        for f in files:
            if f.size == self.size and not os.path.samefile(f.name, self.name):
                if f.partHash == self.partHash and f.fullHash == self.fullHash:
                    f._processed = True
                    dup.append(f)
        if len(dup) > 0:
            dup.append(self)
        return dup                           

def sizeParse(szstr):
    suffix = ['GB', 'MB', 'KB', 'B']
    for i, s in enumerate(suffix):
        if szstr.endswith(s):
            return int(szstr[0: len(szstr) - len(s)]) * (1024 ** (len(suffix) - i - 1))
    return int(szstr)

def recursiveDir(dir, pattern, filter):
    l = list()
    for root, dirs, files in os.walk(dir):
        for file in files:
            if fnmatch.fnmatch(file, pattern):
                f = MyFile(os.path.join(root, file))
                if filter(f):   
                    l.append(f)
    return l


def getFiles(arg, filter):
    if os.path.isfile(arg):
        return [MyFile(arg)]
    if os.path.isdir(arg):
        return recursiveDir(arg, '*', filter)
    [path, file] = os.path.split(arg)
    if len(path) == 0:
        path = '.'
    return recursiveDir(path, file, filter)

def main():
    parser = argparse.ArgumentParser(description='Duplicate File Finder')
    parser.add_argument('--min-size', dest= 'minsize', default='1KB', help='minimum file size, supports suffixes GB, MB, KB, B')
    parser.add_argument('--max-size', dest= 'maxsize', default='1024GB', help='maximum file size, supports suffixes GB, MB, KB, B')
    parser.add_argument('--hash-size', dest= 'hashsize', default='64KB', help='file hash size used for preliminary checking')
    parser.add_argument('dirs', metavar='dirs', type=str,
                        nargs='*', help='dirs or globs or files, supports glob patterns')
    args = parser.parse_args()
    MyFile.partHashSize = sizeParse(args.hashsize)
    MinimumSize = sizeParse(args.minsize)
    MaximumSize = sizeParse(args.maxsize)

    Files = list()
    [Files.extend(getFiles(x, lambda x: x.size > MinimumSize and x.size < MaximumSize)) for x in args.dirs]

    p = False

    for f in Files:
        dup = f.findDuplicates(Files)
        if len(dup) > 0:
            if not p:
                print("Following are the duplicates:")
                p = True
            print([x.name for x in dup])

if __name__ == '__main__':
    main()

Answer 1

Python has some neat features, some of which might seem familiar from C++ and some not. The Python standard library is also very powerful. These comments are meant to be complementary to the answer by @Reinderlein, I will not repeat the useful advice given there.

• You can compare multiple things: MINIMUM_SIZE < x.size < MAXIMUM_SIZE.

• The itertools module:

  from itertools import chain
  files = list(chain.from_iterable(
      get_files(x, lambda x: MINIMUM_SIZE < x.size < MAXIMUM_SIZE)) for x in args.dirs))
  

• Decorators, which makes code involving getters easy with property, which you are already using, but not to it's full potential:

  @property
  def part_hash(self):
      if self._part_hash is None:
          h = hashlib.sha1()
          with open(self.name, 'rb') as f:
              h.update(f.read(self.part_hash_size))
          self._part_hash = h.hexdigest()
      return self._part_hash
  

  Note that self.part_hash_size is the same as MyFile.part_hash_size, unless you overwrite it in the instance (and be careful of mutating mutable objects). This gives you additional flexibility.

• (Python 3.6+) Format strings, which utilize the format syntax and make it even better:

  def __str__(self):
      return f"{self.name} is {self.size}"
  
  def __repr__(self):
      return f"<{self.__class__.__name__} {self.name}:{self.size}>"
  

• (Python 3.8+) Assignment expressions, which allow you to shorten some while loops:

  @property
  def full_hash(self):
      if self._full_hash is None:
          h = hashlib.sha256()
          with open(self.name, 'rb') as f:
              while buf := f.read(self.part_hash_size):
                  h.update(buf)
              self._full_hash = h.hexdigest()
      return self._full_hash
  

• Truthiness of non-empty containers: if l is the same as if len(l) > 0 for any container in the standard library (and should also be the same for any custom classes you create).

• Modules are automatically in their own namespace. No need to come up with names like MyFile, just call it File. You should avoid overwriting built-in names, but everything else is fair game, since you can always import them from another module and prefix them with the module name.

• List comprehensions are nice, but sometimes the functions in operator give you more readability. Not really in this case, but as a demonstration:

  from operator import attrgetter
  a = [x.name for x in dup]              # in your code
  b = [getattr(x, "name") for x in dup]  # if the attribute name is a variable
  c = map(attrgetter("name"), dup)       # using operator instead
  assert a == b == list(c)
  

• Generators allow you to get rid of storing the full result in a list only to then operate on every item of the list. Instead, generate the next item whenever you are done processing the previous one:

  def recursive_dir(dir, pattern, filter):
      for root, dirs, files in os.walk(dir):
          for file in files:
              if fnmatch.fnmatch(file, pattern):
                  if filter(f := File(os.path.join(root, file))):
                      yield f
  

  Or, with a generator expression added and using the yield from keyword:

  def recursive_dir(dir, pattern, filter):
      for root, dirs, files in os.walk(dir):
          yield from (f for file in files
                      if fnmatch.fnmatch(file, pattern)
                      and filter(f := File(os.path.join(root, file))))
  

---

As to your actual algorithm, you want to group together "equal" items, for some measure of equality. Currently you are comparing each file against each other file, so your algorithm is \$\mathcal{O}(n^2)\$. Instead, just define how two files compare and what the hash should be:

def __eq__(self, other):
    if not isinstance(other, self.__class__):
        return False
    return self.part_hash == other.part_hash and self.full_hash == other.full_hash

def __hash__(self):
    return int(self.part_hash, base=16)

Then you can just put them into a dictionary, which is \$\mathcal{O}(n)\$, because you only need to iterate over the files once:

from collections import defaultdict

def groupby_hash(files):
    duplicates = defaultdict(list)
    for f in files:
        duplicates[f].append(f)
    return duplicates

def files_with_duplicates(files):
    groups = groupby_hash(files).values()
    return list(filter(lambda x: len(x) > 1, groups))

This uses the fact that when putting a hashable object into a dictionary, it is not just put into a slot according to its hash. If two objects have the same hash, they are also compared by equality. This way only the part_hash should be used if there are no duplicates of it and the full_hash is used to make sure they are actually full duplicates. Sometimes the full_hash will still be calculated anyway because of regular collisions. You can test that this is the case for example like this:

files = list(recursive_dir(".", "*", lambda f: os.path.isfile(f.name)))
len(files)
# 1448
d = groupby_hash(files)

# There are files which are unique and their `full_hash` has never been computed
sum(map(lambda f: f._full_hash is None and len(d[f]) == 1, files)))
# 759

# The `full_hash` has been computed for all files with duplicates
sum(map(lambda f: f._full_hash is not None and len(d[f]) > 1, files))
# 93
sum(map(lambda f: f._full_hash is None and len(d[f]) > 1, files))
# 0

# But there are some files without duplicates, whose `full_hash` has been computed
sum(map(lambda f: f._full_hash is not None and len(d[f]) == 1, files))
# 596

Answer 2

Formatting

There are some minor issues that would not pass PEP8. You should run a linter or inspector over your code, and it will suggest that you should change some whitespace.

Another formatting suggestion is that you write PART_HASH_SIZE instead of partHashSize for constants, and size_parse instead of sizeParse for function names and variables.

Disposable comprehensions

There's not really a point to making this a list comprehension:

[Files.extend(getFiles(x, lambda x: x.size > MinimumSize and x.size < MaximumSize)) for x in args.dirs]

You're better off to just for .. in.

Units

1 MB == 1,000,000 bytes. 1 MiB == 1,048,576 bytes. You're using the latter, so you need to add some 'i' letters to your unit names.

Return unpacking

This:

[path, file] = os.path.split(arg)

doesn't need the square brackets.