Какой самый быстрый способ сравнить два байтовых массива?
Я пытаюсь сравнить два длинных байт-массива в VB.NET и столкнулся с загадкой. Сравнение двух файлов размером 50 мегабайт занимает почти две минуты, поэтому я явно что-то делаю не так. Я на машине x64 с тоннами памяти, поэтому там нет проблем. Вот код, который я использую в данный момент и хотел бы изменить.
_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() и затем сделал то же самое сравнение, тот же код, и он работал примерно за одну секунду (я должен сравнить его еще и сравнить с другими), но если вы делаете то же самое с локальным Переменные и использовать общий массив становится значительно медленнее. Я не уверен почему, но это вызывает у меня гораздо больше вопросов об использовании массивов.
6 ответов
Что _Bytes(I) звонить делать? Он не загружает файл каждый раз, не так ли? Даже с буферизацией это будет плохой новостью!
Будет много способов микрооптимизировать это с точки зрения просмотра длинных за один раз, потенциально используя небезопасный код и т. Д. - но я бы просто сконцентрировался на получении разумной производительности в первую очередь. Очевидно, что происходит что-то очень странное.
Я предлагаю вам извлечь код сравнения в отдельную функцию, которая занимает два байтовых массива. Таким образом, вы знаете, что не будете делать ничего странного. Я также использовал бы простой For цикл, а не For Each в этом случае - будет проще. Да, и проверьте правильность длины сначала:)
РЕДАКТИРОВАТЬ: Вот код (непроверенный, но достаточно простой), который я бы использовал. Это на 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
Самый быстрый способ сравнить два байтовых массива одинакового размера - это использовать взаимодействие. Запустите следующий код в консольном приложении:
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;
}
}
}
Если вам не нужно знать байт, используйте 64-битные числа, которые дают вам 8 сразу. На самом деле, вы можете определить неправильный байт, как только вы выделите его из набора 8.
Используйте BinaryReader:
saveTime = binReader.ReadInt32()
Или для массивов целых:
Dim count As Integer = binReader.Read(testArray, 0, 3)
Лучший подход... Если вы просто пытаетесь увидеть, отличаются ли эти два, сэкономьте некоторое время, не проходя весь байтовый массив и генерируя хэш каждого байтового массива в виде строк и сравнивая строки. MD5 должен работать нормально и довольно эффективно.
Не строго связано с алгоритмом сравнения:
Вы уверены, что ваше узкое место не связано с доступной памятью и временем, используемым для загрузки байтовых массивов? Загрузка двух 2 ГБ байтовых массивов только для сравнения может поставить большинство машин на колени. Если дизайн программы позволяет, попробуйте вместо этого использовать потоки для чтения небольших кусков.
Я вижу две вещи, которые могут помочь:
Во-первых, вместо того, чтобы всегда обращаться ко второму массиву как item.Bytes, используйте локальную переменную, чтобы указывать непосредственно на массив. То есть перед запуском цикла сделайте что-то вроде этого:
array2 = item.Bytes
Это позволит сэкономить на разыменовании объекта каждый раз, когда вы хотите получить байт. Это может быть дорого в Visual Basic, особенно если в этом свойстве есть метод Getter.
Кроме того, используйте "определенный цикл" вместо "для каждого". Вы уже знаете длину массивов, поэтому просто закодируйте цикл, используя это значение. Это позволит избежать затрат на обработку массива как коллекции. Цикл будет выглядеть примерно так:
For i = 1 to max Step 1
If (array1(i) <> array2(i))
Exit For
EndIf
Next