c# - 查找一个字节数组是否包含另一个字节数组的最快方法是什么？

Question

我有一些非常慢的代码。我知道它会是，现在它是。基本上，我正在从一堆目录中读取文件。文件名改变但数据不变。为了确定我是否已读取该文件，我对其字节进行哈希处理并将其与已处理文件的哈希列表进行比较。每个目录中大约有 1000 个文件，找出每个目录中的新文件需要花费一分钟左右的时间(然后处理开始)。这是基本代码:

public static class ProgramExtensions
{
    public static byte[] ToSHA256Hash(this FileInfo file)
    {
        using (FileStream fs = new FileStream(file.FullName, FileMode.Open))
        {
            using (SHA256 hasher = new SHA256Managed())
            {
                return hasher.ComputeHash(fs);
            }
        }
    }
    public static string ToHexString(this byte[] p)
    {

        char[] c = new char[p.Length * 2 + 2];

        byte b;

        c[0] = '0'; c[1] = 'x';

        for (int y = 0, x = 2; y < p.Length; ++y, ++x)
        {
            b = ((byte)(p[y] >> 4));

            c[x] = (char)(b > 9 ? b + 0x37 : b + 0x30);

            b = ((byte)(p[y] & 0xF));

            c[++x] = (char)(b > 9 ? b + 0x37 : b + 0x30);
        }

        return new string(c);

    }
}

class Program
{
    static void Main(string[] args)
    {
        var allFiles = new DirectoryInfo("c:\\temp").GetFiles("*.*");

        List<string> readFileHashes = GetReadFileHashes();

        List<FileInfo> filesToRead = new List<FileInfo>();

        foreach (var file in allFiles)
        {
            if (readFileHashes.Contains(file.ToSHA256Hash().ToHexString()))
                filesToRead.Add(file);
        }

        //read new files
    }
}

无论如何我可以加快速度吗？

Answer 1

我相信您可以通过简单地首先检查文件大小来存档最显着的性能改进，如果文件大小不匹配，您可以跳过整个文件甚至不打开它。

您不仅可以保存已知哈希列表，还可以保存已知文件大小列表，并且仅在文件大小匹配时才进行内容比较。当文件大小不匹配时，您甚至可以不用查看文件内容。

根据文件的一般大小，进一步改进可能是值得的:

• 要么在第一个字节不同时进行二进制比较和早期中止(节省读取整个文件，如果您的文件通常很大，这可能是一个非常显着的改进，任何哈希算法都会读取整个文件。检测第一个字节不同可以避免读取文件的其余部分)。如果您的查找文件列表可能包含许多相同大小的文件，那么您可能必须对多个文件进行二进制比较，而不是考虑:

• 散列每个 1MB 的 block 。首先仅根据查找中预先计算的第一个 block 哈希检查第一个 block 。如果第一个 block 相同，则只比较第二个 block ，在大多数情况下，对于不同的文件，可以节省读取超过第一个 block 的时间。当您的文件很大时，这两个选项才真正值得付出努力。

我怀疑更改散列算法本身(例如，首先按照建议检查 CRC)是否会产生任何显着差异。您的瓶颈可能是磁盘 IO，而不是 CPU，因此避免磁盘 IO 会给您带来最大的改进。但一如既往地在性能方面，做衡量。

然后，如果这仍然不够(并且仅此而已)，请尝试使用异步 IO(请记住，尽管顺序读取通常比随机访问更快，因此过多的随机异步读取会损害您的性能)