7865
Рейтинг

ildarovich

Регистрация: 19.04.2008 (16 лет назад)
Был(а) на сайте: сегодня в 13:27

Друзья

Подписчики 390

Дополнительная информация

Группы

Профессиональный разработчик

IE 2019 Докладчик

Лауреат Infostart Awards

Рейтинг 7865

Улучшение пооперационного планирования в 1С:ERP 2.4 внешними средствами
+56 –

Статья Программист Бесплатно (free) Нет файла HighLoad оптимизация Математика и алгоритмы

Задача построения оптимального производственного расписания требует сравнения тысяч и десятков тысяч вариантов. Выполнять такие вычисления средствами платформы 1С Предприятие нецелесообразно. Как реализовать пооперационное планирование с использованием генетических алгоритмов и параллельных вычислений в докладе на конференции Infostart Event 2019 Inception рассказал генеральный директор компании «ИНТЕХ» Сергей Сафаров.

02.03.2020 10360 ildarovich 8

Иерархия без "В ИЕРАРХИИ"
+187 –

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

Говорится о том, как эффективно представлять иерархию в СУБД, как получать и использовать эти представления при решении задач в запросной технике. Уточняются и дополняются запросы из статьи "Уровни, глубина, прародители, циклы и аналоги запросом" [https://infostart.ru/public/160707/].

22.08.2019 21743 ildarovich 26

187

Интернет-бухгалтерия
+17 –

Статья Для всех Платформа 1С v8.3 Бесплатно (free) Нет файла О жизни

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

17.07.2019 5268 ildarovich 5

"Взлом" теста "1С:Профессионал" методом машинного обучения
+96 –

Статья Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free) Внешний отчет (ert,erf) Математика и алгоритмы

Нейронные сети – не единственная модель, реализующая принципы машинного обучения. Есть еще байесовская модель, которая математически строже и определеннее, поскольку построена на надежном фундаменте теории вероятностей. Применению байесовского вывода к решению интересной теоретической задачи и посвящена данная статья. Слово "взлом" в заголовке использовано для привлечения внимания. Речь идет исключительно о математическом методе, показанном на примере знакомой всем задачи.

12.03.2018 24604 122 ildarovich 44

Минимализмы 3
+436 –

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

Очередная серия "минимализмов" [http://infostart.ru/public/306536/, https://infostart.ru/public/460935/]. Также, как и в предыдущих статьях, здесь приведена подборка коротких оригинальных авторских решений некоторых задач. Ранее эти решения были разбросаны по моим комментариям к чужим публикациям.

19.02.2018 57421 ildarovich 47

436

Простой способ индексирования интервалов
+214 –

Статья Программист Платформа 1С v8.3 Абонемент ($m) Конфигурация (md, cf) Математика и алгоритмы

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

1 стартмани

28.09.2016 45607 44 ildarovich 22

214

Простая и быстрая эмуляция операций с битовыми строками
+74 –

Статья Программист Платформа 1С v8.3 Бесплатно (free) Нет файла Механизмы платформы 1С

Битовые строки могли бы упростить реализацию некоторых алгоритмов на языке платформы «1С: Предприятие 8». Но пока в платформе операций с битовыми строками нет. В то же время уже сделанные попытки смоделировать эти операции преобразованиями над числами опираются на циклы обработки отдельных битов, что плохо сказывается на скорости их работы. Предлагается новое простое решение, основанное на представлении битовых строк строками символов «0» и «1». Приводится примеры кода выполнения основных логических операций AND, OR, XOR, NO без использования циклов. В качестве прикладной задачи рассмотрено получение последовательных значений кода Грэя, который можно использовать для ускорения перебора вариантов.

22.06.2016 32147 ildarovich 14

Настраиваемый генератор числовой последовательности для запроса
+45 –

Статья Программист Платформа 1С v8.3 Бесплатно (free) Нет файла Запросы

В большинстве широко известных решений для генерации числовой последовательности в запросе порядок длины последовательности должен быть определен при написании текста запроса. Это вызывает определенные трудности при его модификации. Предлагается решение, свободное от этого недостатка. Решение ориентировано на модификацию запроса с использованием объекта "схема запроса".

08.05.2016 19947 ildarovich 6

Еще один способ расчета остатков на каждый день в запросе
+150 –

Инструменты и обработки Программист Платформа 1С v8.3 Абонемент ($m) Внешний отчет (ert,erf) Математика и алгоритмы

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

1 стартмани

24.04.2016 49635 64 ildarovich 23

150

Минимализмы 2
+379 –

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

Следующая серия "минимализмов" [http://infostart.ru/public/306536/]. Также, как и в предыдущей статье, здесь приведена подборка коротких оригинальных решений некоторых задач. Ранее эти решения были разбросаны по моим комментариям к чужим публикациям.

23.02.2016 57590 ildarovich 84

379

Смотреть все

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

Dev › Неоплаченные долги при распределении оплаты по правилу ФИФО одним запросом и намного быстрее, чем Вы думали › #142 14.09.23 14:59

(140) Если я правильно понял вопрос, то речь идет о связывании отгрузок с оплатами в пределах заданного периода. То есть о FIFO но для денег. В (52) я отвечал на подобный вопрос и приводил ссылки. На Инфостарте много статей на эту тему, в том числе в чисто запросной технике. Но там речь идет о том, чтобы сделать как-нибудь, то есть проблема скорости для больших баз не решается.

У меня были заготовки для быстрого ФИФО, где не только нарастающий итог по отгрузкам и оплатам считается, но и делается связывание. Но запросы получаются головоломными. А так как, кроме академического, интереса не увидел, не стал публиковать.

Сейчас, после появления функции АВТОНОМЕРЗАПИСИ() и других, они, возможно, бы и упростились, но большого оправданного интереса по прежнему не вижу. Как-то фокус внимания публики переместился в другую сторону.

Публикации › Нахождение уникальных наборов строк таблицы запросом › #77 29.07.23 18:58

(58)

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

Код
СУММА(SIN(НомерПП)),

либо функция

Код
СУММА(COS(НомерПП)).

Любопытно, что это преобразование, фактически, является расчетом одного из коэффициентов ДПФ. То есть у него есть логическая основа.

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

Для этого используем центральную предельную теорему теории вероятностей, которая говорит, что

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

Цитата

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

Это как раз наш случай.

То есть значение ХЭШ функции СУММА(SIN(НомерПП)) как случайная величина будет иметь нормальное распределение.

Математическое ожидание µ случайной величины СУММА(SIN(НомерПП)) будет равно нулю. И, исходя из формы графика плотности распределения вероятности (перевернутый колокол), ноль будет самым частым значением ХЭШ функции. Дисперсия σ^2 итогового распределения будет равна сумме дисперсий исходных распределений.

Дисперсия σ^2 случайной величины SIN(X) равна 0.5.

Потому, что рассчитывается как СРЕДНЕЕ(sin^2(x)) и известно, что СРЕДНЕЕ(sin^2(x)) = СРЕДНЕЕ(cos^2(x)) и sin^2(x) + cos^2(x) = 1.

Значит, дисперсия σ^2 случайной величины СУММА(SIN(НомерПП)) будет равна 0.5 N, а среднее квадратичное отклонение σ равно √(0.5 N), где N - число членов суммы.

Проверка показала, что значение СУММА(SIN(НомерПП)) считается в запросе с точностью девяти десятичных знаков.

Также у нас есть функция ошибок Гаусса erf(x), которая позволяет рассчитать вероятность того, что значение суммы будет отклоняться от математического ожидания (нуля) на вес младшего разряда ε = 10^(-9). А это и есть удвоенная вероятность того, что ХЭШ функция будет принимать значение ноль с точностью девяти десятичных знаков.

Таким образом, максимальная вероятность коллизий будет равна

0.5 erf (ε / (σ * √2 ) ).

Есть разложение

erf(x) = ( 2 / √π ) ( x - x^3 / 3 + x^5 / 10 - ... ).

Учитывая, что x в нашем случае x очень мало, формулу можно предельно упростить, оставив только первое слагаемое.

В итоге максимальная вероятность коллизий окажется равной

ε / ( √(0.5 N) * √(2 π)) = ε / √( π N) = 10^(-9) / √( π N),

и, значит, укладывается в заданные пределы. А в среднем будет еще меньше.

Публикации › Нахождение уникальных наборов строк таблицы запросом › #74 27.07.23 13:51

(72)

Цитата
SQRT(НомерПП + SQRT(2)) - результат всегда иррациональный

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

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

Проблема в агрегатной функции СУММА. Сумма большого количества аргументов дает нормальное распределение. Это означает, что срединные значения ХЭШ-функции будут более вероятны, чем крайние. То есть разряды ХЭШ будут использоваться не с максимальной эффективностью.

Вообще, когда за вами гонятся, можно закидать преследователя всем чем под руку попадется. Это я о решении из (59). Оно "на скорую руку". Но если такой спешки нет, лучше подыскать что-то из области более бережливого программирования.

Публикации › Нахождение уникальных наборов строк таблицы запросом › #68 26.07.23 14:58

(67) Приятно, что здесь наши точки зрения совпадают. Я тоже считал бы достаточным (по многим причинам) CRC32.

Хорошо, берем за основу.

Публикации › Нахождение уникальных наборов строк таблицы запросом › #66 26.07.23 14:15

(65) Думаю, MD5 не посчитать. Во всяком случае, запросом разумной сложности. Но все свойства MD5 (кроме вероятности коллизий) нам не нужны. Это не задачи криптографии.

В хорошей хэш-функции требуется тщательно перемешивание битов входных аргументов. Сгодилось бы и CRC128 (если потребовать 2^(-128)).

Публикации › Нахождение уникальных наборов строк таблицы запросом › #64 26.07.23 13:38

(58) (63) Есть интересный вопрос, связанный с обсуждаемой темой. Но довольно общего характера.

Начну издалека.

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

Теперь предположим, что правильная хэш-функция дает вероятность коллизий 10^(-38).
То есть работает как MD5.
Это значит, что если все время жизни Вселенной (4,35*10^17 сек) каждую секунду выполнять запрос к таблице из миллиона наборов строк,
то только в одной из квадриллиона (10^15) параллельных вселенных один раз может появиться коллизия.

То есть весь код запроса второго этапа всегда будет работать зря!

Так вот, вопрос: готовы ли вы выкинуть этот код за его ненадобностью или нет?

А если упростить хэш-функцию до CRC32 с вероятностью коллизий 2^(-32)?

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

Публикации › Нахождение уникальных наборов строк таблицы запросом › #63 26.07.23 13:35

(58)

Цитата
Жду уже 2-й день когда ты явишь ее нам и обоснуешь вероятность коллизий =)

Честно говоря, таких намерений у меня не было, но если интерес есть, подумаю над этим.

Пока просьба над моим вопросом подумать.
Он в следующем посте.

Публикации › Нахождение уникальных наборов строк таблицы запросом › #57 25.07.23 11:48

(20) Коллизии будут обязательно.

Мы не можем взаимно однозначно отобразить множество разных сочетаний значений в группе, которых 2^(max(НомерПП)) и диапазон значений агрегатной функции 10^38.

А вообще формулы

Код
SUM(SQRT(НомерПП))

Код
SUM(SQRT(НомерПП)) + SUM(LOG10(НомерПП))

по зрелому размышлению, недостаточно эффективны (кстати, в последней формуле лучше тогда не суммировать, а отдельно считать ХЭШ1 и ХЭШ2).

Так как не используют весь диапазон возможных значений ХЭШ [0, 10^38] (упрощенно). А также не дают равную "плотность" этого отображения (которая определяет вероятность коллизии).

Так что лучше пользоваться проверенными преобразованиями типа приведенных в той статье, на которую я уже ссылался. Но можно изобрести что-то новое на базе появившихся функций. Минимальную вероятность коллизий (минимальную максимальную вероятность) обеспечит равномерное отображение на весь диапазон возможных значений ХЭШ.

7865 Рейтинг

ildarovich

Рейтинг 7865

Комментарии

7865
Рейтинг