40

.NET CORE下最快比较两个文件内容是否相同的方法 - WAKU

 4 years ago
source link: https://www.cnblogs.com/waku/p/11069214.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

本文因为未考虑磁盘缓存, 结果不是很准确, 更严谨的结果请参看本博文的续集

最近项目有个需求,需要比较两个任意大小文件的内容是否相同,要求如下:

  1. 项目是.NET CORE,所以使用C#进行编写比较方法
  2. 文件大小任意,所以不能将文件内容全部读入到内存中进行比较(更专业点说,需要使用非缓存的比较方式)
  3. 不依赖第三方库

为了选出最优的解决方案,我搭建了一个简单的命令行工程,准备了两个大小为912MB的文件,并且这两个文件内容完全相同.在本文的最后,你可以看到该工程的Main方法的代码.

下面我们开始尝试各个比较方法,选出最优的解决方案:

比较两个文件是否完全相同,首先想到的是用哈希算法(如MD5,SHA)算出两个文件的哈希值,然后进行比较.

废话少说,撸起袖子写一个MD5比较方法:

/// <summary>
/// MD5
/// </summary>
/// <param name="file1"></param>
/// <param name="file2"></param>
/// <returns></returns>
private static bool CompareByMD5(string file1, string file2)
{
    // 使用.NET内置的MD5库
    using (var md5 = MD5.Create())
    {
        byte[] one, two;
        using (var fs1 = File.Open(file1, FileMode.Open))
        {
            // 以FileStream读取文件内容,计算HASH值
            one = md5.ComputeHash(fs1);
        }
        using (var fs2 = File.Open(file2, FileMode.Open))
        {
            // 以FileStream读取文件内容,计算HASH值
            two = md5.ComputeHash(fs2);
        }
        // 将MD5结果(字节数组)转换成字符串进行比较
        return BitConverter.ToString(one) == BitConverter.ToString(two);
    }
}

比较结果:

Method: CompareByMD5, Identical: True. Elapsed: 00:00:05.7933178

耗时5.79秒,感觉还不错.然而,这是最佳的解决方案吗?

其实我们仔细想一下,答案应该是否定的.

因为任何哈希算法本质上都是对字节进行一定的计算,而计算过程是要消耗时间的.

很多下载网站上提供了下载文件的哈希值,那是因为下载的源文件本身不会改变,只需要计算一次源文件的哈希值,提供给用户验证即可.

而我们的需求中,两个文件都是不固定的,那么每次都要计算两个文件的哈希值,就不太合适了.

所以,哈希比较这个方案被PASS.

这种求算法最优解的问题,我以往的经验是: 去stackoverflow查找 😃

经过我的艰苦努力,找到了一个非常切题的答案: How to compare 2 files fast using .NET?

得赞最多一个答案,将代码改造了一下放入工程中:

/// <summary>
/// https://stackoverflow.com/a/1359947
/// </summary>
/// <param name="file1"></param>
/// <param name="file2"></param>
/// <returns></returns>
private static bool CompareByToInt64(string file1, string file2)
{
    const int BYTES_TO_READ = sizeof(Int64);        // 每次读取8个字节
    int iterations = (int)Math.Ceiling((double)new FileInfo(file1).Length / BYTES_TO_READ); // 计算读取次数

    using (FileStream fs1 = File.Open(file1, FileMode.Open))
    using (FileStream fs2 = File.Open(file2, FileMode.Open))
    {
        byte[] one = new byte[BYTES_TO_READ];
        byte[] two = new byte[BYTES_TO_READ];

        for (int i = 0; i < iterations; i++)
        {
            // 循环读取到字节数组中
            fs1.Read(one, 0, BYTES_TO_READ);
            fs2.Read(two, 0, BYTES_TO_READ);

            // 转换为Int64进行数值比较
            if (BitConverter.ToInt64(one, 0) != BitConverter.ToInt64(two, 0))
                return false;
        }
    }

    return true;
}

该方法基本的原理是循环读取两个文件,每次读取8个字节,转换为Int64,再进行数值比较.那么效率如何呢?

Method: CompareByToInt64, Identical: True. Elapsed: 00:00:08.0918099

什么?8秒!竟然比MD5还慢?这不是SO得赞最多的答案吗,怎么会这样?

其实分析一下不难想到原因,因为每次只读取8个字节,程序频繁的进行IO操作,导致性能低下.看来SO上的答案也不能迷信啊!

那么优化的方向就变为了如何减少IO操作带来的损耗.

既然每次8个字节太少了,我们定义一个大一些的字节数组,比如每次读取1024*10个字节到数组中,然后进行字节数组的比较.

但是这样又带来一个新问题,就是如何快速比较两个字节数组是否相同?

我首先想到的是在MD5方法中用过的----将字节数组转换成字符串进行比较:

/// <summary>
/// 读入到字节数组中比较(转为String比较)
/// </summary>
/// <param name="file1"></param>
/// <param name="file2"></param>
/// <returns></returns>
private static bool CompareByString(string file1, string file2)
{
    const int BYTES_TO_READ = 1024 * 10;

    using (FileStream fs1 = File.Open(file1, FileMode.Open))
    using (FileStream fs2 = File.Open(file2, FileMode.Open))
    {
        byte[] one = new byte[BYTES_TO_READ];
        byte[] two = new byte[BYTES_TO_READ];
        while (true)
        {
            int len1 = fs1.Read(one, 0, BYTES_TO_READ);
            int len2 = fs2.Read(two, 0, BYTES_TO_READ);
            if (BitConverter.ToString(one) != BitConverter.ToString(two)) return false;
            if (len1 == 0 || len2 == 0) break;  // 有文件读取到了末尾,退出while循环
        }
    }

    return true;
}

Method: CompareByString, Identical: True. Elapsed: 00:00:07.8088732

耗时也接近8秒,比上一个方法强不了多少.

分析一下原因,在每次循环中,字符串的转换是一个非常耗时的操作.那么有没有不进行类型转换的字节数组比较方法呢?

我想到了LINQ中有一个比较序列的方法SequenceEqual,我们尝试使用该方法比较:

/// <summary>
/// 读入到字节数组中比较(使用LINQ的SequenceEqual比较)
/// </summary>
/// <param name="file1"></param>
/// <param name="file2"></param>
/// <returns></returns>
private static bool CompareBySequenceEqual(string file1, string file2)
{
    const int BYTES_TO_READ = 1024 * 10;

    using (FileStream fs1 = File.Open(file1, FileMode.Open))
    using (FileStream fs2 = File.Open(file2, FileMode.Open))
    {
        byte[] one = new byte[BYTES_TO_READ];
        byte[] two = new byte[BYTES_TO_READ];
        while (true)
        {
            int len1 = fs1.Read(one, 0, BYTES_TO_READ);
            int len2 = fs2.Read(two, 0, BYTES_TO_READ);
            if (!one.SequenceEqual(two)) return false;
            if (len1 == 0 || len2 == 0) break;  // 有文件读取到了末尾,退出while循环
        }
    }

    return true;
}

Method: CompareBySequenceEqual, Identical: True. Elapsed: 00:00:08.2174360

竟然比前两个都要慢(实际这也是所有方案中最慢的一个),LINQ的SequenceEqual看来不是为了效率而生.

那么我们不用那些花哨的功能,回归质朴,老实儿的使用while循环比较字节数组怎么样呢?

/// <summary>
/// 读入到字节数组中比较(while循环比较字节数组)
/// </summary>
/// <param name="file1"></param>
/// <param name="file2"></param>
/// <returns></returns>
private static bool CompareByByteArry(string file1, string file2)
{
    const int BYTES_TO_READ = 1024 * 10;

    using (FileStream fs1 = File.Open(file1, FileMode.Open))
    using (FileStream fs2 = File.Open(file2, FileMode.Open))
    {
        byte[] one = new byte[BYTES_TO_READ];
        byte[] two = new byte[BYTES_TO_READ];
        while (true)
        {
            int len1 = fs1.Read(one, 0, BYTES_TO_READ);
            int len2 = fs2.Read(two, 0, BYTES_TO_READ);
            int index = 0;
            if (len1 != len2) return false;
            while (index < len1)
            {
                if (one[index] != two[index]) return false;
                index++;
            }
            if (len1 == 0) break;
        }
    }

    return true;
}

结果是....

Method: CompareByByteArry, Identical: True. Elapsed: 00:00:01.5356821

1.53秒!大突破!看来有时候看起来笨拙的方法反而效果更好!

试验到此,比较两个900多MB的文件耗时1.5秒左右,读者对于该方法是否满意呢?

No!我不满意!我相信通过努力,一定会找到更快的方法的!

同样.NET CORE也在为了编写高性能代码而不断的优化中.

那么,我们如何继承优化我们的代码呢?

我突然想到在C# 7.2中加入的一个新的值类型: Span<T>,它用来代表一段连续的内存区域,并提供一系列可操作该该区域的方法.

对于我们的需求,因为我们不会更改数组的值,所以可以使用另外一个只读的类型ReadOnlySpan<T>追求更高的效率.

修改代码,使用ReadOnlySpan<T>:

/// <summary>
/// 读入到字节数组中比较(ReadOnlySpan)
/// </summary>
/// <param name="file1"></param>
/// <param name="file2"></param>
/// <returns></returns>
private static bool CompareByReadOnlySpan(string file1, string file2)
{
    const int BYTES_TO_READ = 1024 * 10;

    using (FileStream fs1 = File.Open(file1, FileMode.Open))
    using (FileStream fs2 = File.Open(file2, FileMode.Open))
    {
        byte[] one = new byte[BYTES_TO_READ];
        byte[] two = new byte[BYTES_TO_READ];
        while (true)
        {
            int len1 = fs1.Read(one, 0, BYTES_TO_READ);
            int len2 = fs2.Read(two, 0, BYTES_TO_READ);
            // 字节数组可直接转换为ReadOnlySpan
            if (!((ReadOnlySpan<byte>)one).SequenceEqual((ReadOnlySpan<byte>)two)) return false;
            if (len1 == 0 || len2 == 0) break;  // 有文件读取到了末尾,退出while循环
        }
    }

    return true;
}

核心为是用来比较的SequenceEqual方法,该方法是ReadOnlySpan的一个扩展方法,要注意它只是方法名与LINQ中一样,实现完全不同.
那么该方法的表现如何呢?

Method: CompareByReadOnlySpan, Identical: True. Elapsed: 00:00:00.9287703

不 到 一 秒!

相对上一个已经不错的结果,速度提高了差不多40%!

对此结果,我个人觉得已经很满意了,如果各位有更快的方法,请不吝赐教,我非常欢迎!

关于Span<T>结构类型,各位读者如有兴趣,可浏览该文章,该文有非常详细的介绍.

  • 文中的代码只是出于实验性质,实际应用中仍可以继续细节上的优化, 如:

    1. 如两个文件大小不同,直接返回false
    2. 如果两个文件路径相同,直接返回true

  • 试验工程的Main方法源码:

    static void Main(string[] args)
{
    string file1 = @"C:\Users\WAKU\Desktop\file1.ISO";
    string file2 = @"C:\Users\WAKU\Desktop\file2.ISO";
    var methods = new Func<string, string, bool>[] { CompareByMD5, CompareByToInt64, CompareByByteArry,  CompareByReadOnlySpan };
    foreach (var method in methods)
    {
        var sw = Stopwatch.StartNew();
        bool identical = method(file1, file2);
        Console.WriteLine("Method: {0}, Identical: {1}. Elapsed: {2}", method.Method.Name, identical, sw.Elapsed);
    }
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK