6
\$\begingroup\$

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()
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I don't know why there's a close vote; this seems fine to me. \$\endgroup\$
    – Reinderien
    Aug 20, 2019 at 17:32

2 Answers 2

3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.