代码之家 › 专栏 › 技术社区 › scottm

如果一个字节数组数组包含另一个字节数组,最快的方法是什么?

bytearray reference-type comparison c#

scottm · 技术社区 · 15 年前

我有一些非常慢的代码。我知道会是现在是。基本上,我是从一堆目录中读取文件。文件名会更改,但数据不会更改。为了确定我是否读过这个文件,我对它的字节进行散列,并将其与已处理文件的散列列表进行比较。每个目录中大约有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
    }
}

我能加快速度吗?

7 回复 | 直到 15 年前

Ben Schwehn 15 年前

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

除了保存已知哈希列表之外,您还将保留已知文件大小的列表,并且只在文件大小匹配时进行内容比较。当文件大小不匹配时,即使查看文件内容,也可以保存自己。

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

当第一个字节不同时进行二进制比较和早期中止(保存读取整个文件的过程,这是一个非常显著的改进,如果您的文件通常很大,任何哈希算法都会读取整个文件。如果检测到第一个字节不同,则可以避免读取文件的其余部分)。如果查找文件列表可能包含许多大小相同的文件,因此您可能需要对多个文件进行二进制比较,请考虑:
散列,每一块1兆字节。首先,只根据查找中预先计算好的第一个块散列检查第一个块。仅当第一个块相同时才比较第二个块,在大多数情况下,保存不同文件的第一个块以外的读数。这两个选项都只在您的文件很大时才真正值得您这么做。

我怀疑改变散列算法本身(如建议进行CRC的第一次检查)会产生任何显著的差异。您的瓶颈很可能是磁盘IO,而不是CPU,因此避免磁盘IO将给您带来最大的改进。但和往常一样, 做措施。

然后,如果这还不够(只有在那时),可以尝试使用异步IO(请记住,尽管顺序读取通常比随机访问快,但是过多的随机异步读取可能会损害您的性能)

Vinko Vrsalovic 15 年前

创建文件列表
按文件大小对列表排序
从列表中删除具有唯一大小的文件
现在做散列(首先快速散列可能会提高性能)

Bert F 15 年前

使用具有有效搜索功能(哈希或二进制搜索)的readfilehashes存储区的数据结构。我认为哈希集或Treeset在这里更适合你。
使用适当的校验和(哈希和)函数。sha256是一个加密散列,可能是杀戮过度。CRC的计算成本较低,最初用于捕获无意/随机更改(传输错误),但可以接受设计/打算隐藏的更改。您正在扫描的文件之间的区别是什么?

见 http://en.wikipedia.org/wiki/List_of_checksum_algorithms#Computational_costs_of_CRCs_vs_Hashes

一个真正简单的通过采样的校验和(例如,校验和=(前10个字节和后10个字节))能工作吗?

Michael G 15 年前

我会先做一个快速的CRC哈希检查,因为它比较便宜。如果CRC不匹配,则继续执行更“可靠”的哈希测试,如sha

Unknown 15 年前

你对问题的描述仍然不够清楚。

最大的问题是你在做一些散列。这肯定很慢。

您可能希望尝试搜索修改时间,如果文件名发生更改,则修改时间不会更改:

http://msdn.microsoft.com/en-us/library/ms724320(VS.85,loband).aspx

或者您可能希望监视文件夹中是否有任何新文件更改:

http://www.codeguru.com/forum/showthread.php?t=436716

Daniel Brückner Pradip 15 年前

首先按文件大小对文件进行分组-这将使您拥有较小的文件组。现在它取决于组大小和文件大小。您可以开始并行读取所有文件,直到找到不同之处。如果存在差异,则将组拆分为在当前位置具有相同值的较小组。如果您有关于文件差异的信息,那么您可以使用这些信息—从末尾开始读取,如果集群发生较大的变化,则不要逐字节读取和比较,或者了解文件的内容。如果必须并行读取许多文件导致随机磁盘访问,此解决方案可能会引入I/O性能问题。

您还可以计算每个组中所有文件的哈希值并进行比较。您不必一次处理整个文件—只需计算几个字节(可能是4kib集群或任何适合您文件大小的字节)的散列值,并检查是否存在所有就绪的差异。如果没有,计算接下来几个字节的哈希值。这将使您能够处理每个文件的较大块,而无需为内存中一组中的每个文件保留一个这样大的块。

所以这一切都是关于时间内存(磁盘I/O内存)的权衡。您必须找到将组中的所有文件读取到内存中并逐字节比较它们(高内存需求、快速顺序访问,但可能读取大量数据)和逐字节读取文件并仅比较最后一个字节读取(低内存需求、缓慢随机访问、只读取所需数据)的方法。此外,如果组非常大,则逐字节比较文件将变慢-从n个文件中比较一个字节是一个O(N)操作-首先计算哈希值,然后仅比较哈希值可能会变得更高效。

justlost 15 年前

更新: 绝对不要只检查文件大小。如果您的操作系统版本允许使用fileinfo.lastwritetime

我为内部项目编译器/打包程序实现了类似的功能。我们有超过8K个文件,所以我们将最后修改的日期和哈希数据存储到SQL数据库中。然后在随后的运行中,我们首先查询任何特定文件上的修改日期,然后只查询哈希数据…这样我们只计算那些看起来被修改的文件的新哈希数据…

.NET可以在fileinfo类中检查上次修改的日期。我建议你去看看。 编辑: 这是链接 LastWriteTime

我们的打包程序需要大约20秒来找出哪些文件被修改过。