Есть ли очень быстрый алгоритм генерации контрольной суммы?

Question

Искал немного, но я действительно не нашел то, что я смотрел.

Я должен проверять около 100 байт [16384] каждую секунду (+ много других задач ..). Самая большая проблема, которая стоит за углом, - это скорость.

Вы, ребята, знаете какой-либо хороший алгоритм контрольной суммы в C# .NET, который безумно быстро? Он не обязательно должен быть очень точным, но если изменяется один бит, контрольная сумма должна (обычно ..) также меняться.

Байт хранится в памяти, поэтому нет элементов ввода-вывода, которые замедляют его.

Спасибо!

Answer 1

Если каждый бит имеет значение, алгоритм контрольной суммы должен обрабатывать каждый байт. Простой алгоритм просто добавляя каждое значение и игнорируя переполнение:

static unsafe uint GetChecksum(byte[] array) 
    { 
     unchecked 
     { 
      uint checksum = 0; 
      fixed (byte* arrayBase = array) 
      { 
       byte* arrayPointer = arrayBase; 
       for (int i = array.Length - 1; i >= 0; i--) 
       { 
        checksum += *arrayPointer; 
        arrayPointer++; 
       } 
      } 
      return checksum; 
     } 
    } 

Конечно, вы не можете обнаружить все изменения и получить дубликаты, но это может дать вам указания о том, как быстрый алгоритм выполняет.

Answer 2

Расширение ответа C.Evenhuis, вот некоторые варианты, которые должны быть довольно быстрыми. Я не уверен, что из-за их правильности, кто-нибудь с большим опытом работы хочет помочь мне? Я знаю, что они не дают той же контрольной суммы, что и для каждого байта, но я действительно думаю, что они дают контрольную сумму, которая равна хорошим (не очень, но явно достаточным) в качестве байтового.

Как я уже сказал в комментарии, вы можете значительно улучшить скорость, не сравнивая байт за байт, но рассматривая массив как в 4 раза меньшем массиве ints или в 8 раз меньшем массиве длин. Рассмотрение этого вопроса как long[] дает только преимущество в производительности на 64-битном уровне.

static unsafe uint ChecksumInt(byte[] array) 
{ 
    unchecked 
    { 
    uint checksum = 0; 
    fixed (byte* ptr = array) 
    { 
     var intPtr = (uint*)ptr; 

     var iterations = array.Length/4; 
     var remainderIterations = array.Length % 4; 

     for (var i = 0; i < iterations; i++) 
     { 
     var val = intPtr[i]; 
     checksum += val; 
     } 

     while (remainderIterations >= 0) // no more than 3 iterations 
     { 
     checksum += ptr[array.Length - remainderIterations]; 
     remainderIterations--; 
     } 
     return checksum; 
    } 
    } 
} 

static unsafe ulong ChecksumLong(byte[] array) 
{ 
    unchecked 
    { 
    ulong checksum = 0; 
    fixed (byte* ptr = array) 
    { 
     var intPtr = (ulong*)ptr; 

     var iterations = array.Length/8; 
     var remainderIterations = array.Length % 8; 

     for (var i = 0; i < iterations; i++) 
     { 
     var val = intPtr[i]; 
     checksum += val; 
     } 

     while (remainderIterations >= 0) // no more than 7 iterations 
     { 
     checksum += ptr[array.Length - remainderIterations]; 
     remainderIterations--; 
     } 
     return checksum; 
    } 
    } 
} 

Мои измерения производительности на 64-разрядных (Core 2 Duo 3 ГГц) для массива 100000 элементов более 10000 итераций:

• За 1 байт: 00: 00: 00,7052533
• Пер 4 байта: 00: 00: 00,1761491
• За 8 байт: 00: 00: 00,0856880

Так совсем немного быстрее.

Но, как я уже сказал, я не знаю точно, обеспечит ли он такую ​​же хорошую контрольную сумму.