Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Program must to find duplicate files (by content) in a given directory(and subdirectories).

I collect all data in Map<Long, ArrayList<String>> map where Key is the size of file and Value is the List of paths to files with the same size.

public static void main(String[] args) {

     long start = System.currentTimeMillis();

     new FileScanner("/").searchFiles();

     System.out.println(System.currentTimeMillis() - start);
}

I tested program on root directory (Linux) / where total count of files is: 281091. The time is of scanning: 3131064 milliseconds. In my opinion it's may be more faster.

/boot/grub/biosdisk.mod
/usr/lib/grub/i386-pc/biosdisk.mod

/usr/lib/ruby/vendor_ruby/1.8/rubygems/command_manager.rb
/usr/lib/ruby/1.9.1/rubygems/command_manager.rb

/usr/share/pixmaps/openjdk-7.xpm
/usr/share/app-install/icons/_usr_share_icons_sun-java5.xpm
...

Also the program make log/files.log files where outputting paths of files the same contents separated groups on one blank line.

import org.apache.log4j.Logger;

import java.io.*;
import java.util.*;
import java.nio.file.Files;

public class FileScanner {

    private String path, canonPath;

    private static final int BUFFER_SIZE_SMALL  = 1024;         // 1024 byte
    private static final int BUFFER_SIZE_MEDIUM = 1048576;      // 1 mb
    private static final int BUFFER_SIZE_BIG    = 10485760;     // 10 mb

    private static Logger log = Logger.getLogger(FileScanner.class);

    /*
     * Data structure where keys is a size of file and
     * value is list of canonical path to files the same size
     */
    private Map<Long, ArrayList<String>> mapFiles;

    /*
     * Constructor using the specified path
     */
    public FileScanner(String path) {
        this.path = path;
        mapFiles = new HashMap<>();
    }

    /*
     * Constructor with the specified initial capacity
     */
    public FileScanner(String path, int capacity) {
        this.path = path;
        mapFiles = new HashMap<>(capacity);
    }

    /*
     * Getter and Setter for path
     */
    String getPath() {
        return path;
    }
    void setPath(String path) {
        this.path = path;
    }

    /*
     * Get canonical path from File
     */
    private String toCanonicalPath(File file) {
        try {
            canonPath = file.getCanonicalPath();

        } catch (IOException e) {
            e.printStackTrace();
        }
        return canonPath;
    }

    /*
     * Get an input stream that reads bytes from a file
     */    
    protected InputStream getInputStream(File file) throws FileNotFoundException {
        return new BufferedInputStream(new FileInputStream(file));
    }

    /*
     * Define buffer size by file length
     */
    protected int defineBufferLength(long length) {

        if (length < BUFFER_SIZE_MEDIUM)               // file size less than 1mb
            return BUFFER_SIZE_SMALL;                  // 1bt

        if (length < BUFFER_SIZE_BIG)                  // file size less than 10mb
            return BUFFER_SIZE_SMALL * 10;             // 10bt

        if (length < BUFFER_SIZE_BIG * 10)             // file size less than 100mb
            return BUFFER_SIZE_MEDIUM;                 // 1mb

        if (length < BUFFER_SIZE_BIG * 100)            // file size less than 1gb
            return BUFFER_SIZE_BIG;                    // 10mb

        return BUFFER_SIZE_BIG * 10;                   // 100mb
    }

    /*
     * Search similar files by length in the directory and subdirectories
     */
    private void scanner(String path) {

        File[] subDirs = new File(path).listFiles(new FileFilter() {
            @Override
            public boolean accept(final File file) {

                if (file.isFile() && file.canRead()) {

                    long size = file.length();          // length of the file is a key in map

                    if (mapFiles.containsKey(size))
                        mapFiles.get(size).add(toCanonicalPath(file));

                    else mapFiles.put(size, new ArrayList<String>(25) {{
                        add(toCanonicalPath(file));
                    }});

                    return false;
                }
                return file.isDirectory() && file.canRead() && !Files.isSymbolicLink(file.toPath());
            }
        });

        for (int i = 0; i < subDirs.length; i++)
            scanner(toCanonicalPath(subDirs[i]));
    }

    /*
     * Compare binary files
     */
    protected boolean compareFiles(String path1, String path2) {

        if (path1.equals(path2)) return false;

        boolean isSimilar = true;

        final File f1 = new File(path1), f2 = new File(path2);

        int size = defineBufferLength(f1.length());

        byte[] bytesF1 = new byte[size], bytesF2 = new byte[size];

        try (InputStream in1 = getInputStream(f1); InputStream in2 = getInputStream(f2)) {

            while (in1.read(bytesF1) != -1 && in2.read(bytesF2) != -1) {

                if (!Arrays.equals(bytesF1, bytesF2)) {
                    isSimilar = false;
                    break;
                }
            }
        } catch (IOException e) {
            log.error("Error:", e);
        }
        return isSimilar;
    }

    public void searchFiles() {

        scanner(path);

        for (ArrayList<String> paths : mapFiles.values()) {

            if (paths.size() == 1) continue;

            for (int i = 0; i < paths.size(); i++) {

                String path1 = paths.get(i);

                boolean isFound = false;

                for (int j = 0; j < paths.size(); j++) {

                    String path2 = paths.get(j);

                    if (compareFiles(path1, path2)) {

                        log.info(path2);
                        paths.remove(path2);
                        isFound = true;
                    }
                }
                if (isFound) log.info(path1 + "\n");

                paths.remove(path1);
            }
        }
    }
}

How I can optimize any pieces of code or algorithm to be as fast as possible ?

share|improve this question

2 Answers 2

up vote 7 down vote accepted

Another approach: Currently if you have three big files (with the same size) the algorithm will compare A with B and A with C. It reads A twice which could be avoided. Read each file once, store a hash value (MD5, SHA1, etc.) of the content and compare the hash only.

About the current implementation: If I'm right it contains a bug. In the following code paths.remove(path2) modifies the list during iteration:

    for (ArrayList<String> paths : mapFiles.values()) {
        if (paths.size() == 1) continue;
        for (int i = 0; i < paths.size(); i++) {
            String path1 = paths.get(i);
            boolean isFound = false;
            for (int j = 0; j < paths.size(); j++) {
                String path2 = paths.get(j);
                if (compareFiles(path1, path2)) {
                    log.info(path2);
                    paths.remove(path2);
                    isFound = true;
                }
            }
            if (isFound) log.info(path1 + "\n");
            paths.remove(path1);
        }
    }

I've created a directory with four files with the same content. It looks to me that the code does not read one of them. (I've put a log statement before compareFiles call.)

Some other notes about the code:

  1. Instead of

    private final Map<Long, ArrayList<String>> mapFiles;
    

    use a Multimap. Guava has great implementations. (Doc, Javadoc)

  2. canonPath should be a local variable inside toCanonicalPath since no other method uses it. Furthermore, currently in case of an error the method returns the path of the previous file. It looks like a bugs.

  3. Comments like this almos unnecessary:

    /*
     * Get canonical path from File
     */
    private String toCanonicalPath(final File file) { ... }
    

    It says nothing more that the code already does, it's rather noise. (Clean Code by Robert C. Martin: Chapter 4: Comments, Noise Comments)

  4. In the FileFilter subclass you could use guard clauses to flatten the arrow code.

  5. I'd put the variable declarations to separate lines. From Code Complete, 2nd Edition, p759:

    With statements on their own lines, the code reads from top to bottom, instead of top to bottom and left to right. When you’re looking for a specific line of code, your eye should be able to follow the left margin of the code. It shouldn’t have to dip into each and every line just because a single line might contain two statements.

share|improve this answer
    
But I don't have exceptions: java.util.ConcurrentModificationException. –  Dozortsev Anton Feb 23 at 13:33
3  
@DozortsevAnton - the issue is not that obvious.... You are not using an iterator , but for (int j = 0; j < paths.size(); j++) { ... then, if you later do paths.remove(path1), and that removes something before j, then you will skip a member in the loop because everything shuffles forward by one (what was at j+1 is now at j, so on the next loop, that member is skipped). –  rolfl Feb 23 at 13:37
1  
@rolfl You right the loop have bug. –  Dozortsev Anton Feb 23 at 13:57

For your performance problems, taking nearly an hour really is a problem.

The reality is that your code is not the biggest problem, but the overall algorithm.... Making parts of your code faster will not do much, but making your code do things in different ways will help.

Non-performance problems

  • the path on the FileScanner should not be modifiable... it should be a final variable, and there should not be a setter.

  • palacsint has already pointed out a bug, but that just means that you may not be finding all the duplicates.

  • There is another bug in your code:

            while (in1.read(bytesF1) != -1 && in2.read(bytesF2) != -1) {
    
                if (!Arrays.equals(bytesF1, bytesF2)) {
                    isSimilar = false;
                    break;
                }
            }
    

    This code assumes that the InputStream.read(...) function will read as much data as possible.... which is just not true.

    Reads up to b.length bytes of data from this input stream into an array of bytes.

    Note the 'up to'... I have found that occasionally the system will not read them all, but just as much as is convenient.

    Your code will need to save away the actual number of bytes read, and adjust the compare process accordingly.....

Performance

The parts of your code that I can see as being a performance problem are

  • compareFiles() you should not be reading from two files at the same time. This will require (if the files are large) the disk to be reading from two places at once. Consider using a hashing function to read one file fully, hash it (say SHA-256), and then read the other file fully. This will reduce the amount of head-scanning the disk has to do.

    MessageDigest sha256 = MessageDigest.getInstance("SHA-256");
    .....
    
    int len = 0;
    sha256.reset();
    while ((len = stream.read(buffer)) >= 0) {
        sha256.update(buffer, 0, len);
    }
    byte[] filehash = sha256.digest();
    

    If it was me I would compare both the first 16 or so bytes of the file and also the hash of the file. It is possible for there to be a hash collision (a extremely, extremely remote possibility), but the possiblity of two files that are different, but have both the same hash, and the same first 16 bytes is even more remote.

    So, I would create a function that appends the file hash, and the first 16 bytes together, and calls that the file fingerprint.... If the fingerprints of two same-sized files are the same, then the files are the same.

  • scanner() The scanner is using a relatively slow process.... you should consider using the new and faster java.nio.file classes (spcifically a Files.walkFileTree(...)) new in Java7. This is your best bet.

    Additionally, when looping, calling the method toCanonicalPath() on every file is a problem. I would recommend that you do not do that until you have files that are the same size.... it is a very slow thing to do, and is probably a huge part of your performance problem. Doing it only on files that are the same size will save a lot of work.

share|improve this answer
    
Grateful for your good answer! –  Dozortsev Anton Feb 23 at 14:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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