带有大文件的Java CRC (Adler)

Question

我有以下情况:一个大文件的目录树(大约5000个文件，大约4GB大小)。我要在这棵树上找到副本。

我尝试使用内置到Java的CRC32和Adler32类，但是它非常慢(每个文件大约3-4分钟)。

守则是这样的：

1) Init map <path, checksum>
2) Create CheckSum instance (CRC32 or Adler32);
3) Read file per block (10-100 bytes);
4) In each iteration call update()
5) Result checksum passed in map <path, summ>
6) Find duplicates

问:有没有任何方法可以加快第3-4行中校验和的收集？

Answer 1

我将以以下方式处理这一问题：

1. 尝试使用Java 8并行流或类似的东西，这样我的多核CPU就会被用来加快速度。
2. 用所有文件填充地图。
3. 获取所有文件的大小。
4. 删除所有具有唯一文件大小的文件。如果您的文件是“相当正常”，这很可能已经消除了几个较大的文件。这实际上可以通过使用文件大小作为Map中的键和列表作为值来实现。然后删除具有大小为1的列表的所有条目。
5. 获取每个文件的下一个(第一次:第一次) 4K字节的校验和。
6. 删除所有具有唯一校验和的文件。
7. 重复4和5，直到没有唯一校验和的文件都被完全读取。
8. 其余的文件是重复的文件(如果校验和没有冲突)。
9. 在发生冲突时，比较重复文件的文件内容。

加速校验和的关键是以块的形式完成，并在两者之间进行比较。如果前几个字节已经不同了，为什么还要看剩下的字节呢？

加速比较的另一个关键可能是倒置地图。我会使用Map<checksum, List<path>>而不是Map<path, checksum>。通过这种方式，您可以非常直接地消除所有具有大小为1的列表的条目，而无需进一步查找或比较。

也许还有比这更聪明的方法，当我读到任务的时候，我就把我脑子里的东西抛在脑后了。

我已经画出了一个小程序，几乎可以实现这一点。它不会得到片段中的校验和。这样做的原因是，当我在236670个文件上运行这个文件时，总共有6GB的数据，只花了7秒。免责声明:我有一个SSD。但也许我会更新程序的部分校验和甚至。

import java.io.*;
import java.nio.file.*;
import java.nio.file.attribute.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.stream.*;
import java.util.zip.*;

public class FindDuplicates {
    public static void main(final String... args) throws IOException {
        findDuplicates(argsOrCurrentDirectory(args));
    }

    private static String[] argsOrCurrentDirectory(final String... args) {
        return args.length == 0 ? new String[] {"."} : args;
    }

    private static void findDuplicates(final String... paths) throws IOException {
        final Stream<Path> allFilesInPaths = find(paths);

        final Map<Long, List<Path>> filesBySize = allFilesInPaths.collect(Collectors.groupingByConcurrent(path -> path.toFile().length()));
        final Stream<Path> filesWithNonUniqueSizes = getValueStreamFromDuplicates(filesBySize);

        final Map<Long, List<Path>> filesByChecksum = filesWithNonUniqueSizes.collect(Collectors.groupingBy(FindDuplicates::getChecksum));
        final Stream<Path> filesWithNonUniqueChecksums = getValueStreamFromDuplicates(filesByChecksum);

        filesWithNonUniqueChecksums.forEach(System.out::println);
    }

    private static Stream<Path> toPaths(final String... pathnames) {
        return Arrays.asList(pathnames).parallelStream().map(FileSystems.getDefault()::getPath);
    }

    private static Stream<Path> find(final String... pathnames) {
        return find(toPaths(pathnames));
    }

    private static Stream<Path> find(final Stream<Path> paths) {
        return paths.flatMap(FindDuplicates::findSinglePath);
    }

    private static Stream<Path> findSinglePath(final Path path) {
        try {
            return Files.find(path, 127, ($, attrs) -> attrs.isRegularFile());
        } catch (final IOException e) {
            System.err.format("%s: error: Unable to traverse path: %s%n", path, e.getMessage());
            return Stream.empty();
        }
    }

    public static <V> Stream<V> getValueStreamFromDuplicates(final Map<?, List<V>> original) {
        return original.values().parallelStream().filter(list -> list.size() > 1).flatMap(Collection::parallelStream);
    }

    public static long getChecksum(final Path path) {
        try (final CheckedInputStream in = new CheckedInputStream(new BufferedInputStream(new FileInputStream(path.toFile())), new CRC32())) {
            return tryGetChecksum(in);
        } catch (final IOException e) {
            System.err.format("%s: error: Unable to calculate checksum: %s%n", path, e.getMessage());
            return 0L;
        }
    }

    public static long tryGetChecksum(final CheckedInputStream in) throws IOException {
        final byte[] buf = new byte[4096];
        for (int bytesRead; (bytesRead = in.read(buf)) != -1; );
        return in.getChecksum().getValue();
    }
}