Алгоритмы распределения сумм (наивная методика, Алгоритм Кэхэна)

08.07.21

Разработка - Математика и алгоритмы

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

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

Исходные данные:

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

2. За данную транзакцию банк взял комиссию в размере 72,01

 

 

Задача заключается в распределении (удержании) комиссии банка с контрагента

Варианты решения:

1. Многие, в том числе и я до сие поры), сказал бы что надо просто  распределить пропорционально суммам (наивный алгоритм), давайте попробуем.

Получаем следующую картину, здесь мы строку заказа/сумму заказа*сумму комиссии и применили математические правила округления

 

 

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

Хм... и это не проблема сказали мы, просто учтем разницу в определенной строке, к примеру в последней.

 

 

По цифрам вроде все красиво, задача решена, а решена ли?

Давайте посмотрим со стороны бизнеса и взаиморасчетов с клиентами.

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

Мы ведь с вами занимаемся учетом, зайдите в бухгалтерию и скажите что копейка это не важно, что они вам ответят?

2. Алгоритм Кэхэна

суть алгоритма можно почитать в википедии, а также в телеграмм канале "Радио 1С Энтерпрайз" где я и услышал первый раз (думаю я не один) о существовании этого алгоритма, если в двух словах то мы вводим дополнительную переменную для накопления распределенной суммы, и вносим правки на округление при каждой итерации.

Получаем:

 

 

Сама формула в эксель выглядит следующим образом

=ОКРУГЛ(((B3+F3)*$D$2)-G3;2)

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

Чтоб было привычно и не чуждо 1сному глазу, приведу пример процедуры.

Процедура АлгоритРаспределенияКэхэна(МассивЗначений, СуммаЗаказа, СуммаКомиссии)
	ОбработаноЗаписейНакопительно = 0;
	РаспределеноЗаписейНакопительно = 0;
	КоэфРаспределения = СуммаКомиссии/СуммаЗаказа;
	Для каждого ЭлементМассива ИЗ  МассивЗначений Цикл
	СуммаРаспределения = ОКР(ЭлементМассива+ОбработаноЗаписейНакопительно)*КоэфРаспределения-РаспределеноЗаписейНакопительно,2);	
	ОбработаноЗаписейНакопительно = ОбработаноЗаписейНакопительно+ЭлементМассива;
	РаспределеноЗаписейНакопительно = РаспределеноЗаписейНакопительно+ СуммаРаспределения;
	КонецЦикла;
КонецПроцедуры

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

Многие, может, давно применяют такой алгоритм, просто не знали, что он так красиво называется, лично для себя я положил его в копилку новых знаний.

Ремарка после прочтения комментариев.

Разница в одну копейку в данном примере не так выразительна, и при такой вводной не так однозначно преимущество второго алгоритма и недостатки первого, на последнею запись или по весу.

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

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

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4422    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7464    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

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

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4446    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8840    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7806    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. vano-ekt 123 08.07.21 07:00 Сейчас в теме
2. TMV 14 08.07.21 07:08 Сейчас в теме
Обычно последнюю копейку учитывают в наибольшей сумме,а не в последней.
Да и клиентам всеравно каким алгоритмом вы обосновываете это "удержание/начисление" копейки.
И конечно же совершенно не понятно как понимать фразу
более правильным со стороны учета
как вы определили степень правильности?
torbeev; wolfsoft; booksfill; RustIG; +4 Ответить
5. con-men 182 08.07.21 09:08 Сейчас в теме
(2)Понятно что за копейку в данном примере тебе не предъявят, но разница может и больше при других условиях, и то что эту разницу учтем не в последней строке а а в строке с большим весом принципиально ситуацию не изменит.
прочтите текст по ссылке, лучше мне не сказать. https://t.me/radio1c/117
3. vano-ekt 123 08.07.21 07:43 Сейчас в теме
(2) ТС, видимо, не решал базовую задачу распределения сумм списания в РасходнойНакладной из каркасной конфы) пора Спеца с авторов трясти 🤣 и да, если говорить о правильном распределении, то в примере из статьи, логичней отнести последнюю копейку на бОльшую базу, на Контрагента7, тогда относительное отклонение будет минимальным
4. AnryMc 849 08.07.21 08:46 Сейчас в теме
Встречал разные методы.

И хочу "напомнить" о методе которому не одна сотня лет (встречал названия: "старого еврея", "старого банкира", ...)

Суть метода крайне проста: если последнее число четное - округляется "вверх", нечетное - "вниз" (ну или наоборот)
т.к. от 0 до 9 четных и нечетных 50:50 то чем больше строк округляется тем выше статистическое "схождение"...
7. TMV 14 08.07.21 09:13 Сейчас в теме
(4) Зачем округлять, если последняя цифра 0? Соответственно от 1 до 9 нечетных числе больше, чем четных.
21. АртемВС 09.07.21 10:38 Сейчас в теме
(4)Если память не изменяет, в цифровой обработке сигналов используется нечто подобное. Правда не уверен, что этот метод годится для решения именно этой задачи. В ЦОС он позволяет избежать постоянного смещения при округлении.
6. RustIG 1351 08.07.21 09:11 Сейчас в теме
за публикацию спасибо.

это известная "задача копейки":
1) списание себе/стоим по ФИФО
2) распределение общего НДС по строкам позиций
3) расчет бонусов по строкам чекам - начисление и списание
и т.д.

ваш метод Кэхона не корректно использовать уже только потому , что в первом случае необоснованно снизили Контрагенту11 - своим методом распределения,
а потом в методе Кэхона необоснованно увел. Контр2 и снизили Контр3.
8. RustIG 1351 08.07.21 09:18 Сейчас в теме
в 1с стандартна ситуация проведения-перепроведения документа, затем через месяц еще раз перепровдение групповое за весь период, через год можно еще раз перепровести
тоже самое касаетс ярасчета- перерасчета- и т.д.
у вас всякий раз выборка по контрагентам должна быть одинаково отсортирована - чаще всего берут упорядочение по суммам или по кол-ву (или еще по какой величине) - тогда при перерасчетах, при перепроведениях - где бы не использовался этот механизм выборка будет постоянной в плане последовательности контрагентов - и уже на нее можно накладывать любые формулы...
Например, сажать копейку на служебного Контрагента0 - копить по нему копейки, и списывать комиссию банка на собственные затраты организации, а не сажать на контрагентов.
24. rovenko.n 15.07.21 08:22 Сейчас в теме
(8)
на собственные затраты организации,
вот это улыбнуло. Я вчера как раз у клиента был и финдир прямым текстом заявил, что он готов списывать эту копейку на убытки всегда. Потому что зарплата за время бухгалтера, который сводил эту "нехорошую" копейку несоизмерима с самой копейкой.
Но я не уверен, что вслух такое бухгалтерам смогу сказать :-)
CheBurator; +1 Ответить
25. RustIG 1351 15.07.21 08:57 Сейчас в теме
(24)вам кажется , что вас понимают, но я вас не понял.
26. rovenko.n 15.07.21 13:50 Сейчас в теме
(25)проблемы с копейками существовали всегда. Бухгалтер, чтобы закрыть эту копейку, тратит кучу своего рабочего времени, которое стоит денег. Мне финдиректор клиента сказал, что он готов эту копейку воспринимать как убыток чтобы не забивать бухгалтера бесполезной работой.
starik-2005; +1 Ответить
27. RustIG 1351 15.07.21 16:05 Сейчас в теме
(26) так я и предложил так же, как ваш финдир предложил.
а вы написали:
(24)
вот это улыбнуло.

что значит "улыбнуло" - такого слова в русском языке даже нет...
осталось непонятным - какая связь ваше "улыбнуло" с моим постом выше?
28. rovenko.n 15.07.21 16:35 Сейчас в теме
(27)немногие так как вы, я и этот финдир, понимают выгоду от сведения лишней копейки. "Улыбнуло" - это сленг. То есть я улыбнулся, потому что вспомнил момент, когда финдир, так же как и Вы проявил смекалку и понял, что это невыгодно.
9. RustIG 1351 08.07.21 09:20 Сейчас в теме
сам по себе алгоритм Кахэна - очень интересный, спасибо за поднятие темы! ознакомился, понравилась идея
rovenko.n; +1 Ответить
10. con-men 182 08.07.21 10:03 Сейчас в теме
(6) Если взять для примера
5,0149 5,01
10,015 10,02
5,0149 5,01
10,015 10,02

Сумма

4508,97 4509

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

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

Тот же ФИФО это тоже распределение копейки на последнею партию (если количество списания = количеству остатка списываем всю сумму)
11. RustIG 1351 08.07.21 10:20 Сейчас в теме
(10) охота вам голосом записать или позвонить...
писать не удобно

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

по ФИФО это исключено - там четко закреплена последовательность по дате прихода

у вас же выборка по контрагентам всегда меняется.... ну не по названию же вы список контрагентов формируете? - что тоже ошибочно с точки зрения методологии учета
12. con-men 182 08.07.21 10:22 Сейчас в теме
(11) В тексте публикации у меня сказано ,про порядок записей.

"Важно отметить что порядок распределения сумм зависит от порядка записей, чтоб нам обеспечить неизменность распределения при каждой попытке, порядок всегда должен быть идентичен."
13. RustIG 1351 08.07.21 10:24 Сейчас в теме
(12) какой принцип вы закладываете в свой порядок? это не очевидно....

уточните , пож-та
15. con-men 182 08.07.21 10:33 Сейчас в теме
(13)Задача была продемонстрировать алгоритм, и прописать вводные, думаю принцип сортировки в данном примере не так важен, пусть даже он будет по наименованию, главное обеспечить неизменный порядок. В итоге набор полей сортировки будет зависеть от конкретной задачи.
17. RustIG 1351 08.07.21 11:10 Сейчас в теме
(15) ладно, договорились, я понял
14. RustIG 1351 08.07.21 10:27 Сейчас в теме
(12) вы в любом случае кому -то снизите или увеличите копейку.
а вы сами назвали это необоснованным фактом - когда написали про первый случай.

то есть какой бы метод не использовали - вы всегда будете необоснованно кому-то дописывать копейку или убирать....
какая разница как это назвать - метод Кахэна или классический способ?
16. con-men 182 08.07.21 10:39 Сейчас в теме
(14)При моем примере согласен, надо было рассмотреть более выразительный случай, с большей разницей, для понимания.
Одну копейку, как я писал выше (10), так и так нужно будет пристроить от этого не уйти, а если разница будет уже в 10 копеек к примеру, тут уже думаю однозначно второй алгоритм предпочтительней
18. TMV 14 08.07.21 14:27 Сейчас в теме
(16) нет, не будет, т.к. не определены критерии "правильности."
19. DmitriyTih 08.07.21 14:33 Сейчас в теме
(16) Для начала спасибо, что познакомили с таким методом распределения, запомню, может где-то для какой-то исключительной задачи и пригодится его использовать. Мне кажется, суть комментариев сводится не к разбору работы методов на конкретном примере. Все проще - нет метода, который даст распределение во ВСЕХ случаях с нулевым остатком. А в учете "распределять пропорционально суммам" - все понимают как это работает (порядок следования сумм не важен, что упрощает понимание в разы)))), а если когда и возникают исключительные ситуации с распределением, то в дело включается эксперт в виде человека, заинтересованные лица общаются/договариваются/ если нужно делается корректировка - от чего собственно и метод Кэхэна не защищен.
Что касается примеров, вот вам вопрос: какой метод будет предпочтительнее при распределении суммы = 1 на три суммы 0.1, 0.1, 0.1 при распределении распределенную сумму округлять до целых?
20. con-men 182 08.07.21 15:24 Сейчас в теме
(19) в данному случае разницы принципиальной нет, если на входе только эти данные и нет других разрезов по которым возможна сортировка строк, в обоих случаях будет стабильный, неизменный результат.
0 0
0 1
1 0
Тут интересней вопрос, какой алгоритм будет более стабильным с наименьшей погрешностью в различных условиях? какой алгоритм легче сломать? Вот тут опять склоняюсь ко второму варианту.
22. vano-ekt 123 09.07.21 13:54 Сейчас в теме
да, как правило, задача эта про учет партий, или про затраты предприятия, или про распределение этапов оплаты в рамках отгрузки/заказа одного клиента, и о справедливости распределения последней копейки решать вам или внутреннему заказчику.
задача сферическая ведь, вы же комиссию банка не перевыставляете контрагентам?) списываете на затраты, распределяя на себестоимость или сумму продаж
23. vano-ekt 123 09.07.21 13:57 Сейчас в теме
ну, а если вы за справедливую справедливость, то не храните суммы в целых числах, храните дробями, главное договоритесь с клиентами 😅
rovenko.n; +1 Ответить
29. skyboy13 13 01.09.21 15:24 Сейчас в теме
нужно подарить копейку клиенту и все контрагенты довольны
30. ixijixi 1775 12.10.21 11:34 Сейчас в теме
Коллеги, а что делать с отрицательными суммами?
Вот пограничный пример (рис. 1)
Реальный пример (рис. 2) - распределить сумму РК 12 180,00 по остальным начислениям
Прикрепленные файлы:
31. starik-2005 3033 19.10.21 11:37 Сейчас в теме
(30) https://infostart.ru/1c/articles/416217/ - в принципе то же самое, фактически меняется коэффициент, который на последней итерации будет Х/Х = 1.
32. user830227 11.09.23 23:26 Сейчас в теме
О! Я такой метод сам придумал году в 2009, когда начинал в 1С. Оказывается, его Кэхэн зовут.
33. CheBurator 3119 15.02.24 23:27 Сейчас в теме
"зайдите в бухгалтерию и скажите что копейка это не важно, что они вам ответят?" и в БУ и в НУ при проверках есть такое понятие как "критерий незначимости"
Оставьте свое сообщение