logo标签列表

比较两个字节数组的最快方法是什么？

vb.netarrayscompare
6
我希望能够在VB.NET中比较两个长的字节数组，但遇到了问题。比较两个50兆字节的文件需要将近两分钟的时间，因此我显然做错了什么。我使用的是以下代码，现在想要进行更改：

_Bytes和item.Bytes是要比较的两个不同数组，并且它们已经具有相同的长度。
For Each B In item.Bytes
   If B <> _Bytes(I) Then
        Mismatch = True
        Exit For
   End If
   I += 1
Next

我需要能够尽快比较潜在达到数百兆甚至可能达到一两个千兆的文件。有什么建议或算法能更快地完成这项任务吗？ Item.bytes是从数据库/文件系统中获取的对象，用于与要添加的项目进行比较，因为它的字节长度与用户想要添加的项目匹配。通过比较这两个数组，我可以确定用户是否向数据库添加了新内容，如果没有，则可以将它们映射到其他文件而不浪费硬盘空间。
[更新]
我将数组转换为Byte()的本地变量，然后进行了同样的比较，使用相同的代码，运行时间只需一秒钟（我仍需要对其进行基准测试并与其他结果进行比较），但是如果您使用本地变量并使用通用数组执行相同操作，则速度会大幅降低。我不确定为什么会这样，但这让我对数组的使用产生了更多的疑问。
使用朴素方法比较两个50MB的数组对我来说只需要不到一秒钟的时间。你应该有其他问题。 - Mehrdad Afshari
1
请查看 https://dev59.com/c3VD5IYBdhLWcg3wO5ED，这是关于 C# 的同样问题。有很多答案。我喜欢不安全版本 https://dev59.com/c3VD5IYBdhLWcg3wO5ED#8808245，因为它也可以在 Mono Linux 上运行。 - user276648
6个回答
17
< p > _Bytes(I)调用在做什么？它不会每次加载文件，是吗？即使使用缓冲，那也是个坏消息！

有很多方法可以进行微观优化，例如一次查看长整型等，可能使用不安全代码等--但我只是专注于首先获得合理的性能。显然有些奇怪的事情正在发生。

建议您将比较代码提取到单独的函数中，该函数接受两个字节数组。这样您就知道不会出现任何奇怪的事情。在这种情况下，我还建议使用简单的For循环而不是ForEach--这样会更简单。哦，还要先检查长度是否正确 :)

编辑：这是我将使用的代码（未经测试，但足够简单）。它是C#的，我会秒转换：

public static bool Equals(byte[] first, byte[] second)
{
    if (first == second)
    {
        return true;
    }
    if (first == null || second == null)
    {
        return false;
    }
    if (first.Length != second.Length)
    {
        return false;
    }
    for (int i=0; i < first.Length; i++)
    {
        if (first[i] != second[i])                
        {
            return false;
        }
    }
    return true;
}

编辑：这是VB的代码：

Public Shared Function ArraysEqual(ByVal first As Byte(), _
                                   ByVal second As Byte()) As Boolean
    If (first Is second) Then
        Return True
    End If

    If (first Is Nothing OrElse second Is Nothing) Then
        Return False
    End If
    If  (first.Length <> second.Length) Then
         Return False
    End If

    For i as Integer = 0 To first.Length - 1
        If (first(i) <> second(i)) Then
            Return False
        End If
    Next i
    Return True
End Function
_Bytes(I) 是一个已经存在于内存中的字节数组。 - Middletone
嗨Jon，你VB代码中的第一个条件有一个额外的“Not”。括号也不需要，但它们也没有任何害处（Is == object.ReferenceEquals == 当未定义operator ==时，大致等于引用）。 - Konrad Rudolph
@JonSkeet我们能否使用不同维度的类似于数组的东西来获取仅未匹配的项？而不使用Enumerable.Except。 - huMpty duMpty
@huMptyduMpty：不太清楚你的意思，或者为什么不想使用Enumerable.Except？听起来需要提出一个新问题。 - Jon Skeet
@JonSkeet，这是一个较旧版本的.NET框架，它不允许我使用**.Except。无论如何，我已经在这里发布了我的问题：http://stackoverflow.com/questions/9633112/compare-two-arrays-with-different-dimention/9633171#comment12228018_9633171**。 - huMpty duMpty
显示剩余4条评论
4

比较两个大小相等的字节数组最快的方法是使用Interop。在控制台应用程序上运行以下代码：

using System;
using System.Runtime.InteropServices;
using System.Security;

namespace CompareByteArray
{
    class Program
    {
        static void Main(string[] args)
        {
            const int SIZE = 100000;
            const int TEST_COUNT = 100;

            byte[] arrayA = new byte[SIZE];
            byte[] arrayB = new byte[SIZE];

            for (int i = 0; i < SIZE; i++)
            {
                arrayA[i] = 0x22;
                arrayB[i] = 0x22;
            }

            {
                DateTime before = DateTime.Now;
                for (int i = 0; i < TEST_COUNT; i++)
                {
                    int result = MemCmp_Safe(arrayA, arrayB, (UIntPtr)SIZE);

                    if (result != 0) throw new Exception();
                }
                DateTime after = DateTime.Now;

                Console.WriteLine("MemCmp_Safe: {0}", after - before);
            }

            {
                DateTime before = DateTime.Now;
                for (int i = 0; i < TEST_COUNT; i++)
                {
                    int result = MemCmp_Unsafe(arrayA, arrayB, (UIntPtr)SIZE);

                    if (result != 0) throw new Exception();
                }
                DateTime after = DateTime.Now;

                Console.WriteLine("MemCmp_Unsafe: {0}", after - before);
            }


            {
                DateTime before = DateTime.Now;
                for (int i = 0; i < TEST_COUNT; i++)
                {
                    int result = MemCmp_Pure(arrayA, arrayB, SIZE);

                    if (result != 0) throw new Exception();
                }
                DateTime after = DateTime.Now;

                Console.WriteLine("MemCmp_Pure: {0}", after - before);
            }
            return;
        }

        [DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl, EntryPoint="memcmp", ExactSpelling=true)]
        [SuppressUnmanagedCodeSecurity]
        static extern int memcmp_1(byte[] b1, byte[] b2, UIntPtr count);

        [DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl, EntryPoint = "memcmp", ExactSpelling = true)]
        [SuppressUnmanagedCodeSecurity]
        static extern unsafe int memcmp_2(byte* b1, byte* b2, UIntPtr count);

        public static int MemCmp_Safe(byte[] a, byte[] b, UIntPtr count)
        {
            return memcmp_1(a, b, count);
        }

        public unsafe static int MemCmp_Unsafe(byte[] a, byte[] b, UIntPtr count)
        {
            fixed(byte* p_a = a)
            {
                fixed (byte* p_b = b)
                {
                    return memcmp_2(p_a, p_b, count);
                }
            }
        }

        public static int MemCmp_Pure(byte[] a, byte[] b, int count)
        {
            int result = 0;
            for (int i = 0; i < count && result == 0; i += 1)
            {
                result = a[0] - b[0];
            }

            return result;
        }

    }
}
3
在你的测试中，哪一个是最快的？时间记录？ - jjxtra
MemCmp_Safe: 00:00:00.0060003
MemCmp_Unsafe: 00:00:00.0020002
MemCmp_Pure: 00:00:00.0270015 - Nathan Schubkegel
3
如果您不需要知道字节，可以使用64位整数，它可以一次给出8个。实际上，一旦将其隔离到8个集合中，您可以找出错误的字节。
使用BinaryReader：
saveTime  = binReader.ReadInt32()

或者对于整数数组：

Dim count As Integer = binReader.Read(testArray, 0, 3)
请问您能否进一步解释一下？ - Middletone
使用int数组而不是字节数组。 - sfossen
那么，既然这些是来自文件的字节数组，我该如何将它们转换成你所说的这种分块格式呢？ - Middletone
可以选择一次读取一个64位整数的二进制文件，或者在读取8个字节后，使用位移和位或操作将它们放入64位整数中。 - greyfade
@Middletone：请检查链接，并使用BinaryReader。 - sfossen
0

我看到两件事可能会有所帮助：

首先，不要总是使用item.Bytes来访问第二个数组，而是使用一个本地变量直接指向该数组。也就是说，在开始循环之前，可以这样做：

 array2 = item.Bytes

这将避免每次想要一个字节时都需要从对象中取消引用的开销。在Visual Basic中，如果该属性上有Getter方法，那么这可能是昂贵的。

此外，使用“明确循环”而不是“for each”。您已经知道数组的长度，因此只需使用该值编写循环即可。这将避免将数组视为集合所带来的开销。循环代码应如下所示：

For i = 1 to max Step 1
   If (array1(i) <> array2(i)) 
       Exit For
   EndIf 
Next
0
更好的方法... 如果你只是想看看这两个数组是否不同，那么可以节省时间，不必遍历整个字节数组并生成每个字节数组的哈希字符串进行比较。MD5应该可以很好地工作，并且效率也相当高。
这是非常荒谬的事情。任何加密函数都应该扫描每个数组并计算两者的哈希值... 因此，它的成本比仅执行每字节比较要高得多。 - Maxim
0

与比较算法无关：

你确定瓶颈不是与可用内存和加载字节数组所需的时间有关吗？加载两个2GB的字节数组仅用于比较可能会使大多数计算机崩溃。如果程序设计允许，请尝试使用流来读取较小的块。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接