首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >如果字节数组的数组包含另一个字节数组,那么最快的查找方法是什么?

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

Stack Overflow用户
提问于 2009-06-09 21:44:21
回答 6查看 1K关注 0票数 2

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

代码语言:javascript
运行
复制
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
    }
}

有没有什么我可以加快速度的方法?

EN

回答 6

Stack Overflow用户

回答已采纳

发布于 2009-06-09 21:52:24

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

除了保存已知散列的列表之外,您还将保留已知文件大小的列表,并且仅在文件大小匹配时才进行内容比较。当文件大小不匹配时,您甚至可以省去查看文件内容。

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

当第一个字节不同时,

  • 或者做一个二进制比较与早期中止(保存读取整个文件,这可以是一个非常显著的改进,如果您的文件通常很大,任何散列算法都将读取整个文件。检测到第一个字节不同,您就不必读取文件的其余部分)。如果您的查找文件列表可能包含许多相同大小的文件,那么您可能必须对多个文件进行二进制比较,而不是以块为单位(比方说每个1MB )进行consider:
  • hashing。首先,在您的查找中,仅根据预先计算的第一个块哈希检查第一个块。如果第一个数据块相同,只比较第二个数据块,在大多数情况下,对于不同的文件,可以节省超过第一个数据块的读取。只有当你的文件很大时,这两种选择才是真正值得的。

我怀疑改变散列算法本身(例如第一次检查,按照建议做CRC )是否会有任何显着的不同。您的瓶颈可能是磁盘IO,而不是CPU,因此避免磁盘IO会给您带来最大的改进。但一如既往地在性能上,做了度量。

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

票数 8
EN

Stack Overflow用户

发布于 2009-06-09 21:53:36

  • 创建文件列表
  • 按列表中具有唯一大小的文件对列表进行排序
  • 现在执行散列(首先使用快速散列也可以提高性能)
票数 1
EN

Stack Overflow用户

发布于 2009-06-09 22:15:15

  • 为您的readFileHashes存储使用具有高效搜索功能(散列或二进制搜索)的数据结构。我认为HashSet或TreeSet在这里更适合你。
  • 使用了一个合适的校验和(散列和)函数。SHA256是一种加密散列,可能是过度杀伤力。CRC的计算成本较低,最初旨在捕获无意的/随机的更改(传输错误),但很容易受到设计/打算隐藏的更改的影响。什么符合您正在扫描的文件之间的差异?

请参阅http://en.wikipedia.org/wiki/List_of_checksum_algorithms#Computational_costs_of_CRCs_vs_Hashes

通过采样实现真正简单的校验和(例如,checksum =(前10字节和后10字节))是否有效?

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/972667

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档