Способ кодирования и вычисления даты с использованием упрощенного формата в цифровых устройствах
Владельцы патента RU 2639669:
Открытое акционерное общество "Информационные технологии и коммуникационные системы" (RU)
Изобретение относится к вычислительной технике и, в частности, к способу кодирования и преобразования даты для хранения. Технический результат заключается в увеличение диапазона значений даты практически до максимального, при сравнимой простоте и скорости вычислений, а также компактности хранений. Технический результат достигается за счет выделения для хранения данных о дате, включающей год, месяц и день, целое число длиной K бит, установки для отсчета фиксированной даты как первое января определенного года Y0, ввода значения текущего года Y, месяца М, дня D, и если D<31, то вычисляют целое число N для хранения данных о дате по формуле: N=366×(Y-Y0)+(М-1)×30+D, иначе при М=1 вычисляют целое число N по формуле: N=366×(Y-Y0)+60, а при М>1 вычисляют целое число N по формуле: N=366×(Y-Y0)+360+(М div 10+М) div 2, где div - операция целочисленного деления.
Область техники, к которой относится изобретение
Изобретение относится к вычислительной технике и, в частности, к способам кодирования и преобразования даты для хранения и использования в цифровых устройствах: компьютерах, терминалах и пр.
Уровень техники
В современных цифровых устройствах для хранения и использования даты и времени применяются различные внутренние форматы данных. Для преобразования из внутреннего формата во внешний и наоборот требуется проведение ряда вычислений и операций кодирования/декодирования.
Так, известен способ кодирования и преобразования даты в программном обеспечении (ПО) SQL Server 2005 и SQL Server 2012 компании Microsoft [1, 2]. Для хранения даты и времени отводятся два 4-байтовых целых числа (всего используется 8 байт). Первые 4 байта используются для хранения собственно даты и содержат количество дней до или после даты отсчета, в качестве которой выбрано 1 января 1900 года (для типа данных datetime; вторые 4 байта содержат текущее значение времени, представленного в виде трехсотых долей секунды, прошедших после полуночи). Используется также хранение даты и времени с меньшей точностью. В этом варианте даты хранятся в виде 2-байтового целого числа, представляющего количество дней, прошедших с 1 января 1900 года (для типа данных smalldatetime; в двух следующих байтах хранится количество минут, прошедших после полуночи).
Таким образом, дата может храниться в виде целого числа и минимально занимать 2 байта (16 бит).
Для прямого преобразования даты по григорианскому календарю в содержимое ячейки памяти может использоваться следующий алгоритм [3]:
а=(М-14) div 12,
у=Y+4800-а,
m=М+12×а-3,
J=D+(153×m+2) div 5+365×у+у div 4 - у div 100+у div 400 - 32075,
где а, у, m - промежуточные переменные целого типа;
М - месяц года, от 1 (январь) до 12 (декабрь);
D - день месяца, от 1 до 31;
Y - год григорианского календаря.
После этого для получения N из полученного значения J (номер юлианского дня для исходной даты) вычитают константу J0, которая зависит от стартовой даты и является номером юлианского дня для стартовой даты. Однако для обратного преобразования целого числа N в дату используется еще большее количество преобразований и вычислений, сначала получают номер юлианского дня J, прибавляя константу J0, далее вычисляют
j=J+32044,
g=j div 146097,
dg=j mod 146097,
c=(dg div 36524+1)×3 div 4,
dc=dg-с×36524,
b=dc div 1461,
db=dc mod 1461,
a=(db div 365+1)×3 div4,
da=db-a×365,
у=g×400+с×100+b×4+a,
m=(da×5+308) div 153-2,
d=da-(m+4)×153 div 5+122,
Y=y-4800+(m+2) div 12,
M=(m+2) mod 12+1,
D=d+1,
где b, c, d, j, g, da, db, dc, dg - промежуточные переменные целого типа.
Недостатками известного способа являются необходимость проводить ряд сложных вычислений и большой занимаемый объем хранимых данных.
В ряде цифровых устройств возникает необходимость использования только даты, включающей год, месяц и день, что позволяет снизить объем хранимых данных и упростить вычисления.
Для таких устройств может быть использован известный способ кодирования даты [4], заключающийся в том, что:
- выделяют для хранения данных о дате, включающей год, месяц и день, целое число длиной K бит;
- устанавливают для отсчета фиксированную дату как первое января определенного года Y0;
- вводят значения текущего года Y, месяца М, дня D;
- вычисляют целое число N для хранения данных о дате по формуле N=D+(М-1)×32+(Y-Y0)×384;
- сохраняют число N в двоичном формате;
- вычисляют, при необходимости, дату по формулам
D=N mod 32,
M=(Ndiv 32) div 12+1,
Y=Y0+(Ndiv384),
где div - операция целочисленного деления (деления с отбрасыванием дробной части);
mod - операция взятия остатка от целочисленного деления.
Описанный способ принят за прототип.
Недостатком известного способа является ограничение диапазона хранимых дат. Несмотря на то, что способ выигрывает в простоте вычисления и компактности данных, часть возможных значений не используется.
Для сравнения рассмотрим возможный диапазон хранимых дат. В качестве первоначальной даты Y0 возьмем 01.01.1900 (1 января 1900 г.). Размер даты 2 байта (16 бит).
Если использовать способ компании Microsoft, когда дата вычисляется в днях от первоначальной даты, получаем конечную дату 06.06.2079. Если учитывать только полностью входящие годы, то 31.12.2078. Таким образом, данный способ обеспечивает максимально возможный диапазон в 179 лет.
Если использовать способ, принятый за прототип, то получаем максимальную дату 30.08.2070. Если учитывать только полностью входящие годы, то получаем 31.12.2069. В результате, обеспечивается диапазон в 170 лет. Данный способ содержит меньше вычислений, но приходится жертвовать частью значений, поэтому диапазон становится короче на 9 лет.
Раскрытие сущности изобретения
Техническим результатом является увеличение диапазона возможных значений даты.
Для этого предлагается способ, заключающийся в том, что
выделяют для хранения данных о дате, включающей год, месяц и день, целое число длиной K бит;
устанавливают для отсчета фиксированную дату как первое января определенного года Y0;
вводят значения текущего года Y, месяца М, дня D;
если D<31, то вычисляют целое число N для хранения данных о дате по формуле:
N=366×(Y-Y0)+(М-1)×30+D.
Иначе, если М=1 (январь), то вычисляют целое число N для хранения данных о дате по формуле:
N=366*(Y-Y0)+60.
А для всех остальных значений М>1 (т.е. 2<=М<=12):
N=366×(Y-Y0)+360+(М div 10+М) div 2,
сохраняют число N в двоичном формате;
вычисляют, при необходимости, дату по формулам
Y=Y0+(N-1) div 366;
вычисляют промежуточную величину
A=(N-1) mod 366+1;
если А=60, то М=1; D=31;
если А>360, то вычисляют:
М=(А-360)×2+1-(А-361) div 3;
D=31;
иначе вычисляют:
М=(А-1) div 30+1;
D=(A-1) mod 30+1.
В предложенном способе вычисляют целое число N для хранения данных о дате по формуле
Если D<31, то:
N=366×(Y-Y0)+(М-1)×30+D;
иначе, если М=1 (и D=31):
N=366*(Y-Y0)+60;
а для М>1 (и D=31):
N=366×(Y-Y0)+360+(М div 10+М) div 2.
Значение N представляет собой количество дней от первоначальной даты.
При вычислении N по приведенной формуле в качестве количества дней в любом месяце берется значение 30. Соответственно значения с 1 по 30 - это числа января с 1 по 30, значения с 31 по 59 - числа февраля с 1 по 29 (значение 60 - это всегда 31 января), значения с 61 по 90 - числа марта с 1 по 30, …, значения с 331 по 360 - числа января с 1 по 30.
Значения с 361 по 366 - это даты года, с 31 числом: 31 марта - 361, 31 мая - 362, 31 июля - 363, 31 августа - 364, 31 октября - 365 и 31 декабря - 366. А 31 января - 60. В результате для кодирования одного года нам потребуется 366 чисел (как в високосном году), в котором значение 59 используется только для високосного года. Таким образом, каждая дата внутри года будет иметь свой постоянный порядковый номер от 1 (1 января) до 366 (31 декабря) независимо от того, был ли год високосный или нет. Поэтому, чтобы преобразовать дату в число для дня месяца, значение которого меньше 31, используется формула
N=366×(Y-Y0)+(М-1)×30+D;
А вот для значений даты с D=31 и М>1 используются следующие соответствия:
31 марта (месяц 3) - 361,
31 мая (месяц 5) - 362,
31 июля (месяц 7) - 363,
31 августа (месяц 8) - 364,
31 октября (месяц 10) - 365,
31 декабря (месяц 12) - 366.
Это можно выразить следующей формулой:
N=366×(Y-Y0)+360+(M div 10+M) div 2.
Для обратного преобразования значений диапазона 361-366 в месяц с 31 числом используется формула:
М=(А-360)×2+1-(А-361) div 3,
где промежуточное значение А вычисляется по формуле
A=(N-1) mod 366+1.
Для D=31 и М=1 (январь) значение всегда равно 60.
Количество байт для хранения числа N остается таким же, как в прототипе (2 байта = 16 бит). Соответственно максимально N содержит 216 = 65536 значений в диапазоне от 0 до 65535. Значение 0 означает, что дата не задана (на языке С# имеет значение null).
Если Y0 = 01.01.1900, то получаем
- при N=1 дату 01.01.1900,
- при N=2 - 02.01.1900,
- при N=30 - 30.01.1900,
- при N=31 - 01.02.1900,
- при N=60 - 31.01.1900,
- при N=61 - 01.03.1900,
- при N=360 - 30.12.1900,
- при N=361 - 31.03.1900,
- при N=366 - 31.12.1900,
- при N=367 - 01.01.1901.
Используя данный метод для первоначального года Y0=1900, получаем максимальную дату 21.01.2079. По причине того, что рассматриваются только полностью входящие годы, получаем максимальную дату - 31.12.2078. В результате обеспечивается диапазон в 179 лет (такой же по способу от Microsoft), что на 9 лет больше чем у известного способа, принятого за прототип, при сравнимой скорости вычислений.
Для рассмотренного варианта, когда за первоначальную дату берется Y0=01.01.1900, максимальная дата по способу от Microsoft получается 06.06.2079 (охватывается диапазон в 65536 дней, обозначим как i), по способу прототипа - 30.08.2070 (62334 дня, обозначим как р), по предложенному способу - 21.01.2079 (65400 дня, обозначим как v). Таким образом, способ прототипа обеспечивает p/i=62334/65536≈95.11%, а предложенный способ v/i=65400/65536≈99,79% от максимально возможного. При этом, если способ прототипа теряет около 5% значений от максимально возможного, то предложенный способ только около 0,21%. Если же рассматривать только полностью входящие года, то потери равны 0.
Таким образом, предложенный способ позволяет увеличить диапазон значений даты практически до максимального, при сравнимой простоте и скорости вычислений, а также компактности хранения данных. Согласно предложенному способу под каждый год отводится 366 дней, вне зависимости от того, был ли год на самом деле високосным или нет. Для високосных годов значение 59 (29 февраля) используется, а для остальных годов - нет. При этом самые сложные вычисления високосного года опускаются, тем самым упрощая конвертацию числа в дату. При этом диапазон полностью входящих годов остается таким же, как и в способе от Microsoft.
Осуществление изобретения
Реализация предложенного способа может быть осуществлена в вычислительной системе, способной производить операции целочисленного деления, т.е. практически в любой, включая системы, работающие, например, под управлением операционной системы MS Windows.
Для реализации способа достаточно реализовать выполнение предложенных операций на каком-либо языке программирования.
Например, на языке С# реализация может выглядеть следующим образом:
Реализовать действия предложенного способа в составе программы или функции может специалист в области программирования (программист). Наибольший эффект применение предложенного способа может дать в системах, обрабатывающих данные о датах и имеющих сильные ограничения на объем памяти и аппаратные ресурсы, а также передающие информацию о датах в условиях ограничения на объем передаваемой информации.
Примерами таких систем могут служить системы, хранящие и/или передающие различную информацию, в том числе и даты (например, даты рождения человека, дата отправки груза, дата отправления поезда и т.п.) в виде штрих-кода. В этом случае каждый сэкономленный бит имеет значение.
Эффективно также применение способа в системах и базах данных, в которых имеется большой объем данных с датами, в этом случае может достигаться значительная экономия объема хранения.
Источники информации
1. Дата и время (Transact-SQL), статья по адресу
https://msdn.microsoft.com/ru-ru/library/ms187819(v=sql.90).aspx
2. Datetime (Transact-SQL), статья по адресу
http://msdn.microsoft.com/ru-ru/library/ms 187819(y=sql.110).aspx
3. Julian day, статья по адресу
http://en.wikipedia.org/wiki/Julian_day
4. Патент РФ №2543961, приоритет от 16.01.2013 г.
Способ кодирования и вычисления даты с использованием упрощенного формата в цифровых устройствах, заключающийся в том, что
выделяют для хранения данных о дате, включающей год, месяц и день, целое число длиной K бит;
устанавливают для отсчета фиксированную дату как первое января определенного года Y0;
вводят значения текущего года Y, месяца М, дня D;
если D<31, то вычисляют целое число N для хранения данных о дате по формуле:
N=366×(Y-Y0)+(М-1)×30+D;
иначе
при М=1 вычисляют целое число N по формуле:
N=366×(Y-Y0)+60;
а при М>1 вычисляют целое число N по формуле:
N=366×(Y-Y0)+360+(М div 10+М)div 2,
где div - операция целочисленного деления (деления с отбрасыванием дробной части);
сохраняют число N в двоичном формате;
вычисляют, при необходимости, дату по формулам
Y=Y0+(N-1)div 366;
вычисляют промежуточную величину
А=(N-1)mod 366+1,
где mod - операция взятия остатка от целочисленного деления;
если А=60, то М=1; D=31;
если А>360, то вычисляют:
М=(А-360)×2+1-(А-361)div 3;
D=31;
иначе вычисляют:
M=(A-1)div 30+1;
D=(A-l)mod 30+1.
