Jump to content

    
Sign in to follow this  
Alt.F4

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

Recommended Posts

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

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

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

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

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

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

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

Share this post


Link to post
Share on other sites
15 минут назад, Alt.F4 сказал:

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

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

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

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

 

Share this post


Link to post
Share on other sites

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

2 hours ago, Alt.F4 said:

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

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

 

Удачи! Rob.  

 

Share this post


Link to post
Share on other sites
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 by ae_

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

На хабре нашлась статейка на тему контрольной суммы (не совсем понятно почему в ней везде в расчетах КС обозначается как 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);

Share this post


Link to post
Share on other sites
1 hour ago, Alt.F4 said:

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

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

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

12 minutes ago, Alt.F4 said:

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

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

 

Удачи! Rob.

 

Share this post


Link to post
Share on other sites
32 минуты назад, Alt.F4 сказал:

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

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

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

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

Share this post


Link to post
Share on other sites
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 by ae_

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites
28 минут назад, Alt.F4 сказал:

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

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

Цитата

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

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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this