dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Categories:

История изменения текста и история бух. баланса - алгоритмы.

Продолжение. Начало: "Базы данных - многомерные индексы, мгновенные суммы по отрезкам, кубам и т.п." ( http://dmitgu.livejournal.com/39518.html )

Алгоритм для изменяющегося во времени текста

Бухгалтерский баланс со всеми подробностями - это текст, который состоит из объектов учета (ОУ) и соответствующих каждому ОУ сумм по Дт и/или Кт. Общая сумма по Дг всех ОУ дает итог по Дт (активу) баланса, а общая сумма по Кт всех ОУ дает итог по его Кт (пассиву).

Но бух. баланс - это вариант изменяющегося во времени текста. Притом такого, который может меняться задним числом. Не все документы приходят сразу и некоторые вещи меняются по суду, а что-то переписывается при аудите и смене главбуха, например. То есть, вопрос сводится к тому, чтоб сохранять некие данные и иметь алгоритмы, которые позволяли бы получить данный текст в том виде, в котором он был (должен был быть) в выбранный  момент времени (в любой момент!).

Ясно, что вариант "сохранять весь текст/баланс при каждом изменении" исключен, потому что при изменении "задним числом" тебе придется изменить и сохранить все более поздние версии текста/баланса. А их может быть сколь угодно много.

Поэтому вариант решения - это сохранять информацию об изменениях/добавлениях/удалениях абзацев и уметь быстро формировать список, какие абзацы имелись в данном тексте в выбранный момент времени.

Не будем заморачиваться вопросом положения абзаца в тексте - в бух. балансе положение определяется однозначно бухгалтерским счетом и другими характеристиками ОУ (например - название контрагента, номер и дата договора и первичного документа). Ну а для произвольного текста разное положение абзацев можно считать разными абзацами с одинаковым текстом. Одинаковый текст можно хранить (1 раз) отдельно от положения абзацев (нескольких). И проблема с множественным сохранением одного и того же текста решена.

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

Это просто сделать: если абзац не менялся год - мы заносим его только в список данного года, если десятилетие - только в список десятилетия и т.д. Если же абзац исчезал в течение года, то мы исключаем его из списка года и ставим в тех месяцах, где он был весь период. Так же поступаем с месяцем, где абзац был "иногда" - разбивая его на дни, например. И т.д. Ну, можно в качестве минимального шага выбрать день, например. Если абзац  был по итогам дня, то считать что был весь день.

Приведенное в предыдущем абзаце упорядочивание данных будем называть "ранжированным по периодам" - RP (не путать с PR :) ) Ранжированным - потому что мы используем периоды, вложенные друг в друга и поэтому разница в продолжительности этих периодов изменяется в "разах", имеет разную степень, "ранг".

Поэтому изменение для одного абзаца данного текста вызывает в такой структуре такое количество изменений, которое пропорционально логарифму от числа всех имеющихся в базе операций. Например, поменяли абзац задним числом на 11 ноября 1999 года и пришлось изменить какие-то из списков дня (11 ноября 1999), месяца (ноябрь 1999), года (1999), десятилетия (90-е) и т.д. Не так уж много.

Имея такую RP-структуру, мы можем быстро составить текст на любой момент времени: Берем список года, в котором случился этот момент, добавляем к нему (в нужные места) список месяца, дня. И получаем текст, каким он должен был быть на тот момент времени.

Бух. баланс - чем он сложнее текста

Итак, вроде бы с текстом все просто в случае, если возникают изменения задним числом с каким-то абзацем: удалил те периоды, в которые он отсутствовал и добавляем те, где имелся. Притом на каждое такое изменение в RP-порядке нужно логарифмическое количество шагов (если задуматься, то нужно порядка логарифма в квадрате шагов, потому что  при вставке в каждый список новой информации мы используем индекс данного списка, а это требует порядка логарифма - от количества элементов списка - шагов, а таких списков тоже порядка логарифма от числа операций - вот и получаем произведение логарифмов).

Но с бух. балансом вопрос сложнее, чем с просто текстом. Каждый "абзац" у нас как бы со счетчиком рублей. Притом "абзац" - а точнее ОУ (объект учета) должен присутствовать в каждом бух. балансе,  в котором он не занулен. Притом он может быть как положительным, так и отрицательным. А это все значит, что изменение в бух. балансе "задним числом" порождает у нас пересчет по всем последующим дням.

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

А опасность состоит в том, что текст может неограниченно разрастаться и в результате бухгалтерия (даже программа) "утонет" в обработке кучи уже зануленных, но еще не отмеченных как отсутствующие, "абзацев" (ОУ).

Проблема разделения Дт и Кт

Вроде бы, в предыдущей бухгалтерской заметке (ссылка вверху, приведу и тут - http://dmitgu.livejournal.com/39518.html ) был найден алгоритм, который позволяет мгновенно считать результат по любому ОУ на любой момент времени. Казалось бы, можно просто объединять по несколько ближайших ОУ (ближайших - по порядку их расположения в "тексте") в небольшие группы и считать результат по каждой такой группе. Если он равен нулю, то и не лезть внутрь группы - потому что там все равны 0. Эти группы можно объединять в над-группы с тем же порядком, затем в над-над-группы и т.д. И за счет разбиения всего баланса в такую "древовидную" структуру высотой в логарифм от числа ОУ, мы можем быстро пробежать и построить бух. баланс с подробностями из всех не зануленных ОУ для люого момента Т.

Однако, изложенная в предыдущем абзаце идея имеет ошибку в обосновании. Вот она:

" Если он равен нулю, то и не лезть внутрь группы - потому что там все равны 0".

Проблема в том, что разные ОУ могут быть как положительные (дебетовые), так и отрицательные (кредитовые). А их сумма - даже если она равна нулю - почти ничего не говорит о размере самих ОУ, из которых она сложилась. И нельзя просто так сложить долг в миллион долларов какому-нибудь Капоне, с тем, что Вася Пупкин должен мне тот же миллион и считать, что в сумме получился ноль и спать спокойно.

Вроде бы проблему можно решить, если для каждого ОУ суммировать дебетовые (положительные) сальдо отдельно от кредитовых. Тогда действительно, если у нас сумма по Дт и по Кт для группы ОУ дает ноль, то и каждый ОУ в группе равен 0.

Но тут возникает принципиальный вопрос - надо не только быстро посчитать результат по каждому ОУ, но и разнести его в соответствующую категорию - дебета или кредита. Притом разнести так, чтоб не проверяя конкретно этот ОУ, ты в любой момент времени получал этот ОУ в нужном (дебетовом или кредитовом) разделе бух. баланса - если этот ОУ вообще где-то есть в этот момент, если он не занулен. И это принципиально отличается от мгновенного получения суммы в заранее заданном проверяемом ОУ.

Мы же не можем проверять на факт наличия в момент Т все ОУ, которые мы хоть когда-то использовали -  это выродится в перебор зануленных - в своем большинстве - ОУ. Ведь объекты учета возникают, отрабатываются и исчезают из учета. И актуальные (не нулевые) в момент Т объекты учета - это малая часть от всех ОУ, которые были в бух. балансе, есть или будут.

Так вот, возникает вопрос - можно ли для ОУ так организовать данные и придумать такие алгоритмы, чтоб за небольшое число шагов (логарифм от всего числа операций - пусть в квадрате, кубе или еще какой фиксированной степени) отражалось любое изменение в этом ОУ "задним числом"? Притом отражалось так, чтобы это касалось всех балансов, время которых позже или равно времени данного изменения - и эти балансы можно было построить быстро.

Сформулированный вопрос мучил меня несколько лет. Казалось, что раз можно мгновенно иметь сумму на любой момент времени для отдельного ОУ, то должно найтись и решение для "чуть усложненной" задачи - когда этот результат заранее правильно попадает в Дт или Кт каждого последующего момента.

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

Мы можем представить себе ОУ как некую кривую в координатах оси Времени (X) и денег (Y). То, что находится выше 0 - это дебетовая часть графика. То, что ниже - кредитовая. Каждое изменение "задним числом" - это "поднимание" или "опускание" всей части графика, которая расположена от момента данного изменения включительно.

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

Всякие "зубья" (для упрощения говорим про верхнюю часть графика) этого графика могут как угодно распадаться на гроздья других "зубьев" сверху более крупных "зубов", а "мелкие зубья" - на еще более мелкие и т.д. И каждая сдвижка графика может радикально менять расположение областей Дт и Кт. В то же время логарифмическое число изменений (или даже степень от этого числа) не может обеспечить подобную сложность. А это и означает, что вопрос о быстром изменении структуры Дт и Кт при внесении даже одного изменения задним числом даже в один ОУ не может быть решен в общем случае.

Разумеется, я дал эвристическое доказательство и можно написать  строгое, но для практических нужд (не искать не находимое) и приведенного более чем достаточно. А строгое пусть пишут те, кому за работу математика деньги платят, а я бесплатно могу и с голода помереть :-)

В следующей заметке по бухучету я приведу вполне приемлемый алгоритм для правильного изменения Дт и Кт при изменении в ОУ задним числом. И обосную, почему это приемлемо и достаточно быстро при реальных (а не случайных, которые мог бы лепить генератор случайных чисел) бухгалтерских операциях.

Сведем вопрос к НЕ-постоянным ОУ

Но вернемся к нашему бух. балансу, к нашему изменяющемуся во времени "тексту".

Казалось бы, раз мы не можем в общем случае исключать зануленные в момент Т объекты учета заранее (еще до построения и проверки ОУ) из бух. баланса, то проблему минимизации  текста баланса невозможно решить быстрыми алгоритмами. Однако, вопрос минимизации текста, состоящего из разных ОУ, и вопрос опережающего не-включения в этот баланс произвольного зануленного ОУ - это все же разные вопросы.

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

Рассмотрим *постоянные ОУ", которые большую часть времени находятся в не-нулевом состоянии. Тогда в среднем в бух. балансе в произвольный момент времени таких постоянных ОУ будет примерно половина. И это количество не слишком большое для данного предприятия - оно в состоянии вести с этими ОУ хозяйственные дела, а уж на их учет у него тем более должны быть ресурсы. А это значит, что если мы добавим в баланс еще и все нулевые в рассматриваемый момент постоянные ОУ, то размер текста баланса станет примерно вдвое (обычно меньше чем вдвое) больше чем обычный приемлемый размер. А с алгоритмической и компьютерной т.з. - это незначительное увеличение.

Собственно, в качестве "постоянных ОУ" можем рассматривать и те, которые встречаются в учете (не нулевые) на протяжении 1/3, 1/4, 1/10 и т.д. всего времени учета. Просто тогда коэффициент увеличения текста бух. баланса при добавлении к нему даже нулевых в данный момент "постоянных ОУ" будет 3, 4, 10 и т.д.

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

Понятно, что для полного быстрого подсчета баланса может потребоваться организация распределенных вычислений - потому что каждое подразделение может заниматься лишь своей частью учета, однако, в принципе задача расчета бух. баланса со всеми подробностями для любого момента времени имеет быстрое решение, если удается решить задачу опережающего исключения из бух. баланса нулевых НЕ-постоянных ОУ.

А вот задача исключения зануленных (закрытых) НЕ-постоянных ОУ как раз вполне решаемая. Ведь НЕ-постояннынные ОУ это те, которые больше половины времени учета находятся в нулевом состоянии.

Если проводить аналогию с графиком время-деньги для ОУ, то нам нужно рассматривать не все возможные сдвижки графика вниз-вверх, а только те, которые приводят график в самое "дохлое" (максимально зануленное - притом на протяжении основной части времени) состояние. И такое состояние - только одно, если оно вообще есть. Если такого состояния нет, то перед нами - "постоянное ОУ".

Алгоритм для бух. баланса

Все это значит, что нам нужно отслеживать при работе с каждым ОУ вопрос - не появилось ли у этого ОУ какое-то типичное (одинаковое) для разных моментов времени сальдо. И если такое типичное сальдо встречается чаще, чем в половине случаев (можно ослабить условие до "чаще чем в 2/3, 3/4, ... 9/10  от всего времени учета"), то нужно иметь способ исключать это ОУ из учета для этих моментов времени в том случае, если ОУ изменится так, что это типичное сальдо превратится в ноль.

То есть, нам нужно построить для каждого ОУ некую RP-структуру (ранжированную по периодам), которая будет выделять и отслеживать типичное для данного ОУ сальдо - если такое типичное сальдо есть. Считаем, что у нас уже есть структура данных для быстрого вычисления значения данного ОУ в любой момент времени (это разбиралось в предыдущем тексте по бухучету).

Метод выделения типичного сальдо (если оно есть) такой: если оно есть, то оно обычно типично и для подпериодов. Т.е. большинство месяцев, лет, десятилетий и т.д. тоже имеют тогда внутри себя повторяющиеся сальдо. И упрощает задачу то, что неважно, какое сальдо было в начале периода - можно решать вопрос о типичном сальдо внутри периода так, словно в начале периода сальдо равно 0. А после выделения типичного сальдо в этом предположении - можно будет скорректировать его на величину начального - для всего периода - сальдо.

Если сальдо, которое мы берем за исходное - это сальдо на начало дня, то поищем типичное сальдо в месяце. Если мы исходим из посылки, что начальное сальдо месяца = 0, то "локальное сальдо" для дня номер i будет:

СдЛ(Месяц, i) = ОбДт(Месяц, i-1) - ОбКт(Месяц, i-1)

Где СдЛ - локальное сальдо на начало дня,

i - номер дня в месяце

ОбДт - дебетовый оборот с начала месяца до дня (i-1) включительно

ОбКт - кредитовый оборот для аналогичных условий

Как упоминалось ранее, ОбДт и ОбКт мы можем рассчитать моментально для любых ОУ и любых периодов.

Допустим, среди этих СдЛ(Месяц, i) мы обнаружили повторяющиеся резулдьтаты. Нас интересует, вообще говоря, если эти повторяющиеся результаты встречаются чаще, чем все остальные вместе взяты. Но можно брать и случай "самые частые", а если есть одинаково частые - то брать первый встретившийся из "самых частых". Возьмем такое сальдо как "локальное сальдо отсчета". И обозначим

СдО(месяц)

Если повторов не было, то можно считать СдО(месяц) = 0

И вот теперь мы можем расставить сальдо на начало дней относительно СдО(месяц). Обозначим эти сальдо локальные относительные как СдЛО(месяц, i), тогда:

СдЛО(месяц, i) = СдЛ(Месяц, i) - СдО(месяц)

При этом, если СдЛО(месяц, i) окажется равным 0 - мы его вообще не пишем в базу данных. И если этот ОУ занулен - то на уровне месяца (его дней) он заранее исключен из бух. баланса. И исключен так, что при изменении задним числом за пределами месяца - ничего не приходится переделывать. А если изменение внутри месяца - то СдО  может изменится, но и переделывать надо ничтожное количество сльдо.

Заметим, что

СдЛО(месяц, 1) = - СдО(месяц)

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

СдЛ(Год, i) = ОбДт(Год, i-1) - ОбКт(Год, i-1) + СдО(месяц_i)

Тут видно, что мы не просто посчитали локальное сальдо от начала года до предыдущего месяца включительно, но и увеличили его на "типичное изменение" (СдО(месяц_i)) в течение месяца. Так мы вытаскиваем "типичность" с уровня месяца на уровень месяцев в году для сравнения. А это уже рекурсивная формула, которая годится и для расчета СдЛ(десятилети, i) и т.д. Всяческие СдО() и СдЛО() считаются аналогично расчету внутри месяца.

Если у нас количество операций позволяет ограничиться уровнем десятилетий, то сальдо для ОУ на начало конкретного дня можно будет посчитать так:

Сд(месяц, день) =

СдО(десятилетие) + СдЛО(десятилетие, год) + СдЛО(год, месяц) + СдЛО(месяц, день)

При этом если данный ОУ занулен в данный момент, то ни одного слагаемого даже не появится. Будут отдельные исключения из данного правила (мы же ищем все же внутри локальных периодов, где иногда есть отклонения от глобальной статистики), но они незначительны.

Зануленный ОУ тогда заранее исключен (кроме случая постоянных оУ и редких исключений для непостоянных) из бух. баланса, что нам и требовалось. Притом если у нас ОУ имеет некое типичное сальдо, то оно будет "поднято" на самый верх RP-структуры и если это "типичное сальдо" в результате изменений "задним числом" зануляется в какой-то момент, то оно исчезает и с уровня десятилетия, а на других его и нет - кроме может самых мелких (непродолжительных).

Разумеется, составив баланс из "живых" ОУ, нам потребуется еше "раскидать" их в активную или пассивную часть баланса - но эта задача имеет меньшую сложность, чем первоначальная выборка ОУ и поэтому принципиального усложнения от разбора на Актив и Пассив уже не возникает.

Решили мы такой RP-структурой и вопрос ее быстрого изменения при изменении/добавлении в бух. учет операции "задним числом".  Ведь мы используем только локальные сальдо и менять нам приходится лишь сальдо дней в соответствующем месяце, сальдо месяцев в соответствующем году и т.д. - т.е. делать лишь порядка логарифма в квадрате операций от общего числа операций в бух. учете.

Сводка

Заметка получилась достаточно длинной, потому что потребовалось довольно много обоснований корректности работы алгоритмов. Было обнаружено несколько принципиальных моментов о свойствах бухгалтерского баланса, включающим все нужные ОУ:

1. Нет быстрого алгоритма для раздельного сохранения Дт и Кт сальдо в разные моменты времени для произвольного ОУ (объекта учета)

2. Составление бухгалтерского баланса фирмы, если заданы все его ненулевые ОУ на  заданный момент времени, может быть выполнено оперативно на базе вычислительных мощностей данной фирм.

3. Ошибки в учете фирмы не могут приводить к превращению значительной части объектов учета из закрытых (нулевых) в не-закрытые (не-нулевые), так как тогда вместо посильного для расчета набора реальных (не нулевых) объектов учета будет необходимо оперировать с количеством порядка всех ОУ за время учета. А это несопоставимо с приемлемым для вычисления силами фирмы количеством ОУ.

4. На основании п. 3 и того, что операция, приводящая к "закрытию" ОУ ничем не отличается от любых других операций, можно заключить, что количество ошибок "задним числом" является незначительным (фирма в состоянии выдержать расчет разбухшего от них баланса) - и это исходное условие, на которое можно опираться при составлении алгоритмов бух. учета.

5. Алгоритм, позволяющий быстро менять учет задним числом и при этом быстро составлять изменившиеся балансы - с включением в них только значимых (не нулевых) объектов учета и отсевом "мусора" соразмерного объема - найден.

Tags: ЖЖвЖЖ бухучет, ЖЖвЖЖ программирование, ИТ (информ. технологии), Мои алгоритмы
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments