r10 - 26 Sep 2015 - 19:20:08 - Sergej ZnamenskijYou are here: TWiki >  IS4UGP Web > MainConcept > EntitiesClassesContexts > TimeCoding

Кодирование времени в информационной системе "Ботик"

При сохранении данных в ИС "Ботик" фиксируется время. Формат, в котором оно сохраняется, должен удовлетворять следующим требованиям:

Задача

  1. Монотонность: более позднему моменту должна соотвествовать лексикографически большая строка.
  2. Состав: могут быть использованы только буквы и, возможно, цифры и знак подчёркивания.
  3. Расширяемость: диапазон представляемого времени должен быть расширяем, точность сохранения должна быть варьируема.
  4. Компактность: строки должны быть по возможности короткими.

Идея решения

Если понадобится представлять даты в далёком прошлом и будущем

Числа от 0 до 1 можно представлять с нужной точностью отрезком десятичной дроби.

Чтобы расширить это представление на всю прямую, рассмотрим следующее взаимно-однозначное непрерывное монотонное отображение числовой прямой на (0,1), тождественное на отрезке [0.1, 0.9].

f(x)={

...

0.001+ 0.00001(x-9.8), если -99.8 <= x <-9.8

0.01+ 0.001(x+0.8), если -9.8 <= x <-0.8

0.1+ 0.1(x-0.1), если -0.8 <= x <0.1

x, если 0.1 <= x <0.9

0.9+ 0.1(x-0.9), если 0.9 <=x< 1.8

0.99+ 0.001(x-1.8), если 1.8<= x <10.8

0.999+ 0.00001(x-10.8), если 10.8<= x <100.8

....

}

Мы получаем монотонное представление вешественных чисел с любой точностью конечной десятичной дробью из (0,1), то есть по сути конечной последовательностью цифр. Оно удовлетворяет свойствам 1-3. Если, например, ограничиться точностью 10^(-10), то 1/5, 1/3 и 3/4 кодируется как 2000000000, 3333333333 и 7500000000, десятью знаками, а 98 будет кодироваться 999872000000000 с тремя дополнительными девятками впереди и -90 будет кодироваться 000802000000000 с тремя дополнительными нулями впереди.

Если пока не надо представлять даты в далёком прошлом и будущем, то надо взять единицу времени, существенно превышающую 50 лет, и ограничиться условием 0.1 <= x <0.9, используя обычную запись в позиционной системе счисления. Когда станет предвидеться потребность выхода за эти рамки, алгоритм придётся уточнить согласно описанной идее.

Выбор системы счисления

Чтобы сделать представление более компактным, надо перейти к системе счисления, основанной на латинских буквах (сначала большие, затем малые по алфавиту).

Если бы латинских букв было 64... Но их всего 52, ни то, ни сё. Поэтому придётся честно делить с остатком на 60 как положено. За единицу придётся взять 60 в степени 7 миллисекунд.

Это позволяет ограничиться последовательностью из семи знаков для записи с точностью до миллисекунды чисел в пределах от 60**6 = 46656000000 миллисекунд до 60**7-60**6 = 2752704000000 миллисекунд, то есть примерно с 1971 по 2058 год будет работать линейная часть функции. Поскольку использование дат вне этого диапазона пока не предвидится, можно упростить алгоритм, ограничившись центральной линейной частью, то есть просто перевести time() в миллисекундах в позиционную систему счисления с основанием 60 и записать результат семью буквами, не используя в качестве первой ни 0, ни z. Символы 0 и z будут задействованы вне диапазона по чуть более сложному алгоритму.

Таким образом, в указанном диапазоне строка из 7 символов фиксирует время с точностью до миллисекунды. Для информации от клиента лучше откинуть последнюю цифру, чтобы данное от одного пользователя ни при каких условиях не могло записаться более 17 раз в секунду. Для записи в лог часто повторяющихся данных полезно отбросить еще одну или две цифры, увеличив период создания новой записи до 4 секунд (останется 5 символов в строке) или 4 минут (оставить 4 символа) соответственно.

Алгоритм

Делим время в миллисекундах на 60 с остатком. Остаток указывает позицию последнего символа искомой строки в эталонной строке "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklnbopqrstuvwxy". Делим частное на 60 с остатком. Буква с номером остатка в эталонной строке - предпоследняя в искомой строке. Снова делим ... И так далее пока частное не будет ноль, а остаток даст последнюю седьмую букву.

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

Новый алгоритм см. в TimeStamp.pm

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r10 < r9 < r8 < r7 < r6 | More topic actions
 
Powered by TWiki

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback