[Alt.F4 2]

Здравствуйте.

Есть 2 сервера, у каждого массив с метками времени (64-битные числа), во время синхронизации, метки сохраняются без сортировки, т.е. на одном может быть [1,2,3], а на другом [2,1,3].

Задача посчитать 32-битную контрольную сумму (КС) у этих массивов, чтобы она сходилась, вне зависимости от порядка следования чисел.

Исходя из задачи, доступны только операции сложения, умножения и XOR (+, *, ^).

Подскажите, пожалуйста, как оптимальнее считать КС?...

Спасибо.

P.S. Пока остановились на варианте с умножением на константу (вопрос, какое значение брать за константу) и последующим XOR с КС: checksum(cs,num) {return cs^(num*X);}

Добавлено: при расчете КС старшее слово 64-битной метки можно отбросить, т.к. оно будет одинаковое у всех.

[jcxz 183]

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

Задача посчитать 32-битную контрольную сумму (КС) у таких массивов, чтобы она сходилась, вне зависимости от порядка следования чисел.

x1+x2+x3+..., а потом сложить младшее слово со старшим, кэп.  

[Alt.F4 2]

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

[Ruslan1 14]

7 hours ago, Alt.F4 said:

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

Так условие-то: от перемены порядка обработки результат не меняется.

А значит, сдвиги и прочие позиционно-зависимые стандартные вещи для "усиления КС" использовать нельзя. Тут только сложение и умножение остаются. Мне кажется, что умножение тут будет сильнее, чем сложение.

 

Я бы предложил алгоритм:

шаг#1: перемножить все 64 числа без отбрасывания старшей части. будет 32*64 = 2048 бит

шаг#2: эти 2048 бит ужать до 32 бит (да хоть бы и через нормальную CRC32)

[Alt.F4 2]

Ruslan1, Вы невнимательно прочли первый пост, почему Вы решили, что там 64 числа? В каждом массиве планируется порядка 100тыс чисел и старшее слово как раз можно отбросить из-за его повторения во всех метках.

[Ruslan1 14]

3 minutes ago, Alt.F4 said:

Ruslan1, Вы невнимательно прочли первый пост, почему Вы решили, что там 64 числа? В каждом массиве планируется порядка 100тыс чисел и старшее слово как раз можно отбросить из-за его повторения во всех метках.

Упс, да, извиняюсь. Но это не меняет главной идеи: использовать результат максимально возможной разрядности, и потом этот результат завернуть в 32 бита чем-то хорошим (вроде CRC32), а не просто отбрасывать старшие разряды. Да хотя бы еще раз перемножить перед отбрасыванием.

Хорошо бы, конечно,  посчитать, какая КС из придуманных на коленке будет лучшей по соотношению цена/качество. И тут для нестандартных велосипедов не все так просто- нужно еще придумать критерии оценки и сделать калькуляторы для этих критериев. Ну и сравнить хоть 2-3 метода между собой. Или хоть один метод на разных параметрах.

[jcxz 183]

Если информацию о положении конкретных значений нужно удалить, а оставить только инфу о наличии конкретных значений. И если предположить, что разница между минимальным и максмальным значениями в одном массиве (максимальное расхождение временных меток) не превышает некоторого числа N, такого что: N=(Tmax-Tmin)/D, где D - дискрета времени (вес (в единицах времени) самого младшего разряда 64-битной метки), то можно реализовать примерно такой алгоритм:

1. Выделяем массив (N*2+1) 32-битных счётчиков. Назовём его M. Обнуляем.

2. Как опорное значение берём первую 64-битную метку массива, запоминаем её (Tref). А также: M[N] = 1;

3. Для каждой следующей метки (Tnext) делаем: M[(Tnext-Tref)/D] += 1. Проходим по всем 100тыс. меткам массива.

4. Считаем CRC (любым способом) от полученного массива M.

Всё! Возможны вариации этого метода в зависимости от более детальных условий применения, но в целом как-то так.

Одна из вариаций: Добавить предварительный проход по массиву с нахождением минимальной метки и взять её потом за опорную (Tref). Так можно уменьшить объём массива M до (N+1) ячеек.

 

Другой вариант:

Отсортировать метки массива в порядке возрастания/убывания. А потом посчитать от результата CRC. Но думаю такой алгоритм будет медленнее чем 1-й.

[ae_ 2]

Если все метки времени уникальны, а события происходят не в каждый квант времени D, то массив М 32-битных счётчиков будет в разы, в десятки раз больше исходного массива, но содержать будет лишь 0 или 1 в 32-битной ячейке. Для такого случая, когда метки уникальны, достаточно битового массива.

Пример: суточный лог с дискретностью 0,001с (системный таймер 1мс) 24*60*60*1000 = 86,4 млн возможных меток хранит лишь 0,1 млн записей.

Если условия другие, например 3-х часовой лог, дискретность 1с, 10 800 квантов времени, 100 000 записей, в среднем по 9-10 не уникальных записей/сек., то наверняка сработает.

[ViKo 1]

Вижу 2 варианта:

1. Складывать все числа в одно большое.

2. xor - ить все числа в одно 32-разрядное.

Поскольку сдвиги использовать нельзя, никакой CRC посчитать нельзя.

[jcxz 183]

2 часа назад, ae_ сказал:

Для такого случая, когда метки уникальны, достаточно битового массива.

Если такое имеет место быть - то конечно. Поэтому я и говорил о "вариациях".

2 часа назад, ae_ сказал:

Если условия другие, например 3-х часовой лог, дискретность 1с, 10 800 квантов времени, 100 000 записей, в среднем по 9-10 не уникальных записей/сек., то наверняка сработает.

Если Ваше предположение верно (что массив меток представляет из себя метки последовательно происходящих с некоторым примерно постоянным интервалом событий (назовём его P - среднее значение интервала между метками)), то можно сделать оптимизацию 1-го алгоритма, уменьшающую число N:

1. Выделяем массив (N*2+1) 32-битных счётчиков. Назовём его M. Обнуляем.

2. Как опорное значение берём первую 64-битную метку массива, запоминаем её (Tref). А также Tprev=Tref. А также: M[N] = 1.

3. Для каждой следующей метки (Tnext) делаем: M[(Tnext-Tprev-P)/D] += 1.

4. Tprev=Tnext. Перейти к п.3.

5. Проходим по всем ~100тыс. меткам массива.

6. Считаем CRC (любым способом) от полученного массива M.

Здесь при начальном расчёте числа N нужно прибавить к нему некоторый запас, учитывающий разброс реальных значений периода от среднего значения периода (число P ).

PS: Для экономии памяти (если нужно) можно уменьшить разрядность массива M до 17 бит.

[Alt.F4 2]

Есть еще такой момент, что при добавлении новой метки нет возможности заново проходить по всему массиву.

Т.е. в работе мы оперируем только 32-битной КС, которую рассчитали ранее и по приходу новой метки 64-бита мы должны быстро и максимально дешево обновить КС.

[jcxz 183]

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

Есть еще такой момент, что при добавлении новой метки нет возможности заново проходить по всему массиву.

Т.е. в работе мы оперируем только 32-битной КС, которую рассчитали ранее и по приходу новой метки 64-бита мы должны быстро и максимально дешево обновить КС.

Тогда держите массив M всё время в памяти и просто обновляйте его с приходом каждой новой метки и пересчитывайте CRC от результата.

[AHTOXA 14]

25.06.2020 в 12:35, Alt.F4 сказал:

Есть 2 сервера, у каждого массив с метками времени (64-битные числа), во время синхронизации, метки сохраняются без сортировки, т.е. на одном может быть [1,2,3], а на другом [2,1,3].

А эти метки отсортировать сразу при сохранении нельзя? Не думаю, что это будет сильно накладно.

-------

А, увидел ниже:

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

Есть еще такой момент, что при добавлении новой метки нет возможности заново проходить по всему массиву.

Тогда отбой.

[Alt.F4 2]

1 час назад, jcxz сказал:

Тогда держите массив M всё время в памяти и просто обновляйте его с приходом каждой новой метки и пересчитывайте CRC от результата.

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

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

 

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

[ViKo 1]

Только что, Alt.F4 сказал:

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

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