C Самый быстрый способ сравнения двух растровых изображений

Question

Существует два массива растровых изображений в виде массивов char с миллионами записей. Что может быть самым быстрым способом их сравнения с помощью C.

Я могу представить, как использовать побитовый оператор xor 1 байт за один раз в цикле for.

Важный момент о растровых изображений:

• 1% до 10% от раз алгоритма запуска, растровые изображения могут отличаться. Большую часть времени они будут такими же. Когда они могут отличаться, они могут достигать 100%. Существует высокая вероятность изменения битов в непрерывной полосе.
• Оба растровых изображения имеют одинаковую длину.

Цель:

• Проверить они отличаются, и если да, то где.
• Будьте правильные каждый раз (вероятность обнаружения ошибки, если таковая должна быть 1).

Answer 1

Этот ответ подразумевает, что вы имели в виду «точечный рисунок» в виде последовательности 0/1 значений, а не «растровый формат изображения»

Если вы просто есть два растровых изображений одинаковой длины и хотите быстро сравнить их, memcmp() будет эффективен, как кто-то предложил в комментариях. Вы можете попробовать, используя оптимизацию типа SSE, но это не так просто, как memcmp(). memcmp() предполагает, что вы просто хотите знать, что они разные, и больше ничего.

Если вы хотите узнать, сколько бит они отличаются друг от друга, например, 615 бит различаются, то опять у вас мало возможностей, кроме XOR каждый байт и подсчет количества различий. Как отмечали другие, вы, вероятно, захотите сделать это больше на 32/64 или даже на 256 бит за раз, в зависимости от вашей платформы. Однако, если массивы составляют миллионы байтов, то самая большая задержка (с текущими процессорами) будет временем переноса основной памяти на CPU, и это не имеет большого значения, что делает процессор (здесь много предостережений)

Если вопрос больше спрашивать о сравнении а до Б, но на самом деле вы делаете это много раз, например, от а до в и с, D, Е и т.д., то вы можете сделать несколько вещей

• A. Храните контрольную сумму каждого массива и сначала сравнивайте контрольные суммы, если они одинаковы, тогда существует высокая вероятность того, что массивы одинаковы. Очевидно, существует риск, что контрольные суммы могут быть равными, но данные могут отличаться, поэтому убедитесь, что ложный результат в этом случае не будет иметь драматических побочных эффектов. И, если вы не можете противостоять ложным результатам, не используйте эту технику.
• B. Если у массивов есть структура, например, они являются данными изображения, а затем использовать определенные инструменты для этого, как за этим объяснением объяснить.
• C. Если данные изображения могут быть эффективно сжаты, сжать каждый массив и сравнить с использованием сжатой формы. Если вы используете ZIP-тип сжатия, вы не можете напрямую определить из zip количество бит, но другие методы, такие как RLE, могут быть эффективны для быстрого подсчета бит-бит (но много работы по созданию и получению правильного и быстрого)
• D. Если риск с (a) является приемлемым, тогда вы можете проверять каждую часть, скажем, 262144 бит, и учитывать только различия, когда контрольные суммы различаются. Это значительно сокращает доступ к основной памяти и будет намного быстрее.

Всей A..D дальномеров о снижении основного доступа к памяти, как это гвоздь любого прироста производительности (для задачи, как указано)