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

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

我相信你可以通过简单地首先检查文件大小来存档最重要的性能改进,如果filesize不匹配,你可以跳过整个文件,甚至不打开它.

您还可以保留已知文件大小的列表,并在文件大小匹配时仅进行内容比较,而不仅仅是保存已知哈希列表.当filesize不匹配时,您甚至可以避免查看文件内容.

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

• 当第一个字节不同时,要么与早期中止进行二进制比较(保存读取整个文件,如果文件通常很大,这可能是一个非常显着的改进,任何哈希算法都会读取整个文件.检测第一个字节是不同的使您免于阅读文件的其余部分).如果您的查找文件列表可能包含许多相同大小的文件,那么您可能需要对多个文件进行二进制比较,而是考虑:

• 以每个1MB的块为单位进行散列.首先仅针对查找中预先计算的第一个块哈希检查第一个块.如果第一个块相同,则仅比较第二个块,在大多数情况下,对于不同的文件,将读数保存在第一个块之外 当文件很大时,这两个选项都非常值得.

我怀疑更改散列算法本身(例如,首先检查按建议执行CRC)会产生任何显着差异.您的瓶颈可能是磁盘IO,而不是CPU,因此避免磁盘IO会给您带来最大的改进.但是,与性能一样,请进行衡量.

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