Контрольная сумма массивов с любым порядком следования чисел

[jcxz 0]

17 минут назад, Alt.F4 сказал:

По всей видимости будем писать тесты для выбора лучшего расчета КС с помощью умножения и XOR...

XOR сам по себе по надёжности ничем не отличается от простой суммы. А Вы ранее сказали, что этот метод не достаточно надёжен.

17 минут назад, Alt.F4 сказал:

У нас таких массивов порядка 50тыс, дорогое решение держать дополнительные массивы в ОЗУ.

Нам тут трудно найти правильное решение, по приведённому кусочку задачи. У вас данных об условиях задачи 100%, а нам Вы приоткрыли максимум ~10%.

Опять любимая тема этого форума про партизана в гестапо....  

[AHTOXA 0]

15 минут назад, Alt.F4 сказал:

У нас таких массивов порядка 50тыс, дорогое решение держать дополнительные массивы в ОЗУ.

Стоит задача оперировать только 32-битной КС.

Можно сделать в два этапа: первый этап: просто сумма. Если сумма не совпала - массивы точно разные.

Если сумма совпала, то делать доп. проверку: сортировать массив и считать crc.

 

[RobFPGA 0]

Приветствую!

2 hours ago, Alt.F4 said:

По всей видимости будем писать тесты для выбора лучшего расчета КС с помощью умножения и XOR...

Как и предлагали  выше можно считать только позиционно независимые чек-суммы.  А для уменьшения вероятности коллизий можно перед суммированием хешировать  значения меток  и считать несколько сумм с разными функциями хеширования.

 

Удачи! Rob.  

 

[ae_ 0]

On 6/25/2020 at 4:02 PM, Alt.F4 said:

Просто сложение и просто XOR очень слабые КС, т.к. есть большая вероятность совпадения КС при разных значения меток времени. (см. 2+5=3+4)

Одновременно вычисляйте и храните сразу две(три) КС — сумму и произведение (и XOR).

2, 5 — sum=7; mul=10; xor=7

3, 4 — sum=7; mul=12; xor=7.

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

16 hours ago, ViKo said:

Если при умножении вы будете урезать число, отбрасывать старшую часть, то результат тоже будет зависеть от очередности данных.

Умножение — это многократное сложение, если отбрасывание старшей части и перестановка слагаемых не влияет на сложение, то почему должно влиять на произведение?

Можете привести пример, когда произведение зависит от очерёдности данных?

UPD:

Целочисленное умножение без дополнительных ухищрений не поможет, достаточно 32-х чётных чисел в массиве и результат будет всегда 0, если оставлять 32 младших бита результата.

На малых числах произведение казалось хорошей идеей.

Edited June 27, 2020 by ae_

[ViKo 0]

Потому, что результат произведения, а потом отбрасывания, будет участвоватьтв следующей операции, со следующим словом данных. 

Вы правы. Результат перемножения не будет зависеть от положения слов, если отбрасывать все биты, большие, чем длина слова. 

[Alt.F4 0]

На хабре нашлась статейка на тему контрольной суммы (не совсем понятно почему в ней везде в расчетах КС обозначается как CRC), вот несколько предложенных вариантов для КС 32 бит в разрезе нашей задачи:

Метку времени timestamp сразу урезаем до младшего слова 32 бита, т.к. старшие у всех одинаковые, затем умножение на константу, в статье это 0x990C9AB5:

cs=cs+(timestamp32*0x990C9AB5);

cs=cs^(cs>>16);

И второй вариант без умножения:

cs=(cs<<5)+cs+timestamp32; 

cs=(cs<<5)+cs;

cs=cs^(cs>>16);

[ae_ 0]

1 hour ago, Alt.F4 said:

вот несколько предложенных вариантов для КС 32 бит в разрезе нашей задачи:

Эти варианты не подходят для вашей задачи, результат зависит от порядка меток. Проверьте всего на 2х числах, (2; 5) и (5; 2), CS получается разной.

[Alt.F4 0]

Конечно, там же сдвиги! После 4-часовой объемного коддинга, совсем фильтровать перестал...

Как Вам наш первоначальный вариант с умножением на константу и последующим XOR с КС: checksum(cs,num) {return cs^(num*X);} ?

[RobFPGA 0]

Приветствую!

12 minutes ago, Alt.F4 said:

Как Вам наш первоначальный вариант с умножением на константу и последующим XOR с КС: checksum(cs,num) {return cs^(num*X);} ?

Операция умножения  метки на константу тут как раз и работает элементарным хешированием которое позволяет уменьшить риск коллизий  суммы при взаимно-компенсирующем изменении бит в метках.  Обычно хеширование уменьшает разрядность значения. Но в данном случае можно использовать расширяющее хеширование - например 64 бит значения метки хешировать в 128...256 бит, а уж затем просто делать XOR всех хешей.    

 

Удачи! Rob.

 

[jcxz 0]

32 минуты назад, Alt.F4 сказал:

Конечно, там же сдвиги!

32 минуты назад, Alt.F4 сказал:

Как Вам наш первоначальный вариант с умножением на константу и последующим XOR с КС

Так "умножение на константу" - это тоже сдвиги.  

[ae_ 0]

2 hours ago, Alt.F4 said:

Конечно, там же сдвиги!

Виноваты сдвиги вправо(деление). Если просто перемножить все 100 000 чисел, каждый раз домножая на константу, результат не будет зависеть от порядка. Можно перемножить сначала все числа, затем помножить на все константы, результат не изменится.

a*k*b*k = a*b*k*k. Тоже самое со сложением a+k+b+k = a+b+k+k, а если комбинировать эти операции вместе и/или ещё xor, наверное результат уже будет зависеть от порядка. Я в теории чисел не очень, я бы проверил практически.

upd:

Сумма чисел, каждое домноженное на константу, не улучшит алгоритм, т.к. k можно вынести за скобки и умножить на k уже итоговую сумму a1*k + a2*k + an*k = k*sum, т.е. бесполезно.

произведение чисел, каждое домноженное на константу также не лучше, заменяется на разовое умонжение итогового произведения на k^n mod 2^32.

Повторюсь, произведение в чистом виде или с домножением на константу не работает, достаточно 32-х чётных чисел в массиве и любой 100 000 массив превратится в 0.

Edited June 28, 2020 by ae_

[Alt.F4 0]

Выходит, остаётся только XOR...

[jcxz 0]

15 минут назад, Alt.F4 сказал:

Выходит, остаётся только XOR...

А чем не подходит вариант который я предлагал?

[Alt.F4 0]

jcxz, я писал на прошлой странице, что у нас таких данных с метками 100тыс порядка 50тыс и это только суточное разделение, т.е за каждый день накапливается еще столько же. Поэтому слишком дорого держать дополнительные массивы в ОЗУ. По этой же причине мы не можем ничего сортировать.

Надо что-то максимально дешевое и максимально точное, чтобы гарантировано позволяло находить отличия в метках данных у разных серверов.

[jcxz 0]

28 минут назад, Alt.F4 сказал:

jcxz, я писал на прошлой странице, что у нас таких данных с метками 100тыс порядка 50тыс и это только суточное разделение, т.е за каждый день накапливается еще столько же. Поэтому слишком дорого держать дополнительные массивы в ОЗУ. По этой же причине мы не можем ничего сортировать.

Ну и что? Хоть миллион. Вы ничего не писали про разброс значений меток внутри массивов. А именно от этого будет зависеть размер рабочих массивов. В идеальном случае размер одного раб.массива вообще может быть == 1 слову.

Цитата

Надо что-то максимально дешевое и максимально точное, чтобы гарантировано позволяло находить отличия в метках данных у разных серверов.

Так не бывает. Чтобы и самое дешёвое/простое и самое точное. Или или.