Я часто вижу в интернете дискуссии, а должен ли True-разработчик знать теорию алгоритмов и стандартные алгоритмы. Про алгоритмические собеседования вообще молчу - мнения на этот счет у всех разные, оно и понятно.
Я занимаюсь коммерческой backend разработкой уже 7 лет и в какой-то момент остро ощутил нехватку теоретических знаний. В потоке постоянной работы и дедлайнов времени на «академическое» образование не хватало.
В один момент чаша терпения переполнилась и я твердо решил «начать учиться». Выписал список тем и пошел штудировать литературу из интернета по пунктам. Тут я дошел до теории алгоритмов. Эта область компьютерной науки мне сильно понравилась и я потихоньку начал разбираться. Скажу честно, задачки давались очень тяжело, я все время ощущал, что мой мозг как будто «не настроен на волну» решения таких задач.
Тоже самое, бывало и на работе, когда тебе нужно написать какую-то функцию, а ты в голове не можешь придумать и реализовать алгоритм.
В общем увидел, что у Яндекс Практикума есть курс по алгоритмам, задумался стоит ли идти. Смотрю подробнее, 4 месяца, хм, вроде недолго. Открываю список тем - весь «джентльменский набор» по алгоритмам присутствует. Ну, думаю, ладно, надо пробовать.
Курс я успешно закончил, но история не об этом. Через некоторое время столкнулся на работе с одной проблемой. Опишу в общих чертах:
Я занимался разработкой системы электронного документооборота. Есть документ, который может менять статус. Статусов несколько и в некоторые из них документ может возвращаться по второму кругу. Например: начальнику что-то не понравилось и он отправил в статус «коррекция» - все по новой до начальника.
При этом, в каких-то статусах нужно подписание ответственного, а в каких-то нет. В БД подпись для каждого статуса только одна (хранится как закодированная строка), поэтому нужно определить, может ли документ в этом статусе подписываться несколько раз. Если да - обновлять подпись, если нет - выдавать ошибку.
Первый подход к «снаряду»
Что бы я сделал раньше? Да, ничего особенного, скорей всего написал бы «костыльное» решение, подогнанное под тест-кейсы. Просто потому что не нашел бы другого.
Но тут вдруг, смотрю я на эти статусы и понимаю - «Черт побери, да это же односторонне связный направленный граф» (Вообще графы крутая штука, любые отношения между сущностями в природе можно описать через них). А что значит «Найти повторяющиеся статусы?» - спрашиваю себя и тут же отвечаю - «Точно, найти циклы в графе». Получается нам всего лишь остается найти вершины графа, которые входят в какой-либо цикл и наша задача решена.
Решение №1. Поиск вершин, входящих в цикл графа.
Вспоминаю, что на курсе была похожая задача по поиску циклов. Не долго думая, вооружившись DFS (поиск в глубину), классическим алгоритмом обхода вершин графа, предполагаю, что для решения, нужно «запустить» поиск в глубину для каждой вершины и если нам встречается уже обработанная/пройденная вершина - значит мы попали в цикл. Собираем массив таких вершин и задачка решена. Так как я пишу на php, приведу пример реализации алгоритма на нем:
/**
* @var $arGraph array - Граф, представленный, списком смежности.
* Ключ массива - вершина, а значения смежные вершины.
*
* 2 - вершина посещена
* 1 - вершина в очереди на обработку
* 0 - вершина еще не встречалась
*/
$arVertexColors = [];
$arUpdateCodes = [];
foreach (array_keys($arGraph) as $vertex) {
$arStack = [$vertex];
$arColors = $arVertexColors;
/** Поиск в глубину */
while ($arStack) {
$currentVertex = array_pop($arStack);
$arColors[$currentVertex] = 2;
foreach ($arGraph[$currentVertex] as $neighbourVert) {
if (!$arColors[$neighbourVert]) {
$arStack[] = $neighbourVert;
$arColors[$neighbourVert] = 1;
} elseif ($arColors[$neighbourVert] == 2) { // цикл обнаружен
$arUpdateCodes[] = $neighbourVert;
}
}
}
}
return $arUpdateCodes;И вроде бы, все хорошо. Результат на выходе получается верный. Логически тоже наверно не подкопаться. Но очевидно, в этом решении что-то не так. Для каждой вершины мы запускаем поиск в глубину и посещаем все вершины заново. У такого алгоритма будет квадратичное время работы O(N2). Интуитивно, кажется, нам должно быть достаточно обойти граф один раз, чтобы найти все циклы.
Тут я вспоминаю, что есть такое понятие, как сильно связный компонент у направленного графа - это такой подграф, в котором от любой вершины v1 до любой вершины v2 есть путь как от v1 до v2, так и обратно. Такой подграф является циклом.
Я не любитель придумывать велосипеды, поэтому сразу же подумал «Наверняка какие-нибудь умные дядьки давно решили эту задачу максимально оптимальным способом". Набираю в гугле «Поиск сильно связных компонентов в направленном графе» и оказывается уже придумано 3 алгоритма решения этой задачи за линейное время:
Алгоритм Косарайю
Алгоритм Тарьяна
Алгоритм поиска компонент сильной связности с двумя стеками Дейкстры
Решение №2. Алгоритм сильно связных компонентов Тарьяна
Расскажу об алгоритме Тарьяна. Помимо описания из википедии попробую объяснить его своими словами.
Как и многие алгоритмы он основан на поиске в глубину. Мы начинаем обход каждой вершины по очереди в глубину и как только встречаем уже посещенную вершину, либо отсутствие смежных - значит мы находимся в одной из компонент сильной связности, а именно нашли корень.
Поэтому теперь нужно понять, в какой из компонент мы находимся, для этого мы как бы делаем «задний ход», восстанавливая свой прошлый путь на каждой вершине, при этом проверяем не принадлежит ли эта вершина другой компоненте. Чтобы осуществить «задний ход» на каждом шаге, мы должны сохранять наш путь в памяти, для этого заведем массив indexes и будем помечать на каком шаге пришли в вершину.
Еще надо сохранять индекс «корня» компонента связности, которому принадлежит текущая вершина, для этого используем массив lowlinks. Для хранения уже пройденных вершин воспользуемся стеком stack. Когда мы делаем «задний ход» при обнаружении корня компонента связности, извлечем из stack все вершины до корневого, тем самым добавим в массив strong_components очередную компоненту сильной связности.
На gif-ке представлена работа алгоритма. Первое число рядом с вершиной - массив indexes, второе lowlinks.
Алгоритмические задачки я решаю на python. Поэтому приведу реализацию на этом языке. При необходимости его легко можно переписать на php или на любой другой.
from collections import defaultdict
def strong_connect(vertex):
indexes[vertex], lowlinks[vertex] = len(indexes), len(indexes)
stack.append(vertex)
in_stack[vertex] = True
# Обход вершин через поиск в глубину
for neighbour_vertex in graph[vertex]:
if indexes[neighbour_vertex] == 0:
strong_connect(neighbour_vertex)
lowlinks[vertex] = min(lowlinks[vertex], lowlinks[neighbour_vertex])
elif in_stack[neighbour_vertex]:
lowlinks[vertex] = min(lowlinks[vertex], indexes[neighbour_vertex])
# Попали в корень компонента связности, извлекаем вершины потомки
if lowlinks[vertex] == indexes[vertex]:
scc = []
neighbour_vertex = None
while vertex != neighbour_vertex:
neighbour_vertex = stack.pop()
scc.append(neighbour_vertex)
in_stack[neighbour_vertex] = False
strong_components.append(scc)
if __name__ == "__main__":
# Граф списка смежности
graph = {
'A': {'B'},
'B': {'C'},
'C': {'B', 'D'},
'D': {'E'},
'E': {'F'},
'F': {'D'},
}
stack = []
indexes = defaultdict(lambda: 0)
lowlinks = defaultdict(lambda: 0)
in_stack = defaultdict(lambda: False)
scc = []
strong_components = []
# Обход оставшихся вершин
for vertex in graph:
if indexes[vertex] == 0:
strong_connect(vertex)
print(strong_components)Во время поиска описания работы алгоритма, мне было недостаточно тех материалов, которые есть в интернете. Их было буквально штук 10, которые объясняли в общих чертах. Возможно, кому-то поможет мое объяснение и пример кода :)
Итоги
В сухом остатке имеем следующее: наш граф статусов мы представим в виде списка смежности и «скормим» его алгоритму Тарьяна. На выходе получаем самое оптимальное решение нашей задачи за линейное время исполнения O(V + E), где V - это количество вершин графа, а E - количество ребер.
Я описал свой опыт полезности знания теории алгоритмов и применение их на практики. Даже просто знание каких-то основ, как в моем случае, может сильно сэкономить ваше время как в работе, так и в повседневной жизни. Поэтому вопрос «нужности» таких знаний, для меня, кажется, стал риторическим :)
Комментарии (47)
v1000
04.01.2023 17:28+12Как так, ведь почти идеальная шутка была...
iig
04.01.2023 18:22Каждая правильная шутка про рекурсию порождала бы 2 идентичные шутки про рекурсию.
Willy64
05.01.2023 07:54Это более похоже на бесконечный цикл, чем на рекурсию
klis
05.01.2023 09:10+6Это вообще ни на что не похоже. Почему фраза "Шутить про рекурсию" запускает следующую итерацию?
Тут лучше подошла бы шутка "Сколько лет нужно коммерческому PHP-разрабочику, работающему с документооборотом, чтобы узнать про конечные автоматы". Интересно, что там за костыли были до того костыля, который описан в статье.
wataru
04.01.2023 17:43+10Тут больше похоже, что нужна просто матрица "в какое состояние можно перейти из каждого", с пометками, чья подпись делает этот переход.
Автор, не могли бы вы поподробнее расписать исходную задачу?
rukhi7
04.01.2023 19:25+8Автор, не могли бы вы поподробнее расписать исходную задачу?
вы не понимаете, если поподробнее расписать исходную задачу, то придется решать исходную задачу, тогда никак не получится приплести теорию графов.
На всякий случай, задача сформулирована вот так:
нужно определить, может ли документ в этом статусе подписываться несколько раз. Если да - обновлять подпись, если нет - выдавать ошибку.
в какой момент обновлять подпись, кому выдавать ошибку - фиг его знает! зачем вообще нужна подпись если достаточно (обычно) разрешения (прав) для перевода статуса? - тоже фиг его знает
QviNSteN
05.01.2023 05:24+3Ощущение что у челика спросили почему он потратил неделю на такую задачу, а он решил в оправдание написать статью на Хабре))
aktuba
04.01.2023 19:03Изучение алгоритмов - ОЧЕНЬ хорошо. Категоричность - нет:
Вообще графы крутая штука, любые отношения между сущностями в природе можно описать через них
Это не так. Попробуйте описать через граф "не имеет ничего общего с другими узлами".
wataru
04.01.2023 19:28+1Попробуйте описать через граф "не имеет ничего общего с другими узлами".
У узла нет ребер в другие узлы?
Хуже всякие групповые отношения описываются. Вроде как тройки элементов могут обладать каким-то свойством, а могут не обладать. Например вот такие наборы первого блюда, второго блюда и десерта сочетаются. Это графом не запишешь. Можно, конечно граф обобщить, сделав множество ребер подмножеством V^3, но практически ни один из существующих алгоритмов там работать не будет.
aktuba
04.01.2023 19:42-1Конечно есть... Я предложил описать в графе их отсутствие ;)
wataru
04.01.2023 20:20+4Нет. Факт отсутствия ребер в графе как раз описывает "не имеет ничего общего с другими узлами".
aktuba
04.01.2023 20:26-1Верно. Вот только через граф это описать никак нельзя ;)
wataru
04.01.2023 20:28Не понимаю. Есть ребра — есть отношение. Изолированная вершина никаких отношений не имеет. Все описано.
aktuba
04.01.2023 20:37-2Реально считаете, что "отсутствие описания" === "отсутствие отношений"?
Давайте так: человек-сантехник-работа. Тут нет отношения к "робот", верно? Может ли "робот" быть сантехником? А человеком? А может-ли он делать работу?
Предположим, на вопрос "может ли быть сантехником" вы ответили "да" - значит ли это, что любое "существо", починившее кран - человек? Нет, верно?
Наличие/отсутствее ребер - не показатель ;)wataru
04.01.2023 20:45Я так и не понял, что вы имеете ввиду под "не имеет ничего общего с другими узлами".
В примере выше можно провести направленное ребро "является" между человеком и сантехником. Можно провести ребро между сантехником и работой. Ребра между работой и человеком нет. Факт того, что "человек" не является работой, ни "работа" является человеком в графе записан.
Тут нет отношения к "робот", верно? Может ли "робот" быть сантехником?
Зависит от того, что мы в графе рисуем. Если это "любой объект X является У", то ребра нет. Не любой робот является сантехником. И все записанно. Если вас напрягает, что тут не записано, что некоторые роботы могут быть сантехниками, то надо вводить ребра разных цветов (или смотреть на 2 графа сразу. Один говорит о "могут быть", другой — "всегда являются").
Предположим, на вопрос "может ли быть сантехником" вы ответили "да" — значит ли это, что любое "существо", починившее кран — человек? Нет, верно?
Сами сделали какой-то логически противоречивый переход и теперь радуетесь, что поймали меня на противоречии. Как вы из "робот может быть сантехником" сделали вывод, что "любое "существо", починившее кран — человек" и как это относится к ребрам — вообще неясно.
aktuba
04.01.2023 20:53-2Это троллинг? о_О
В примере выше можно провести направленное ребро "является" между человеком и сантехником.
Нельзя. Ну вообще никак нельзя. По вашему - любой человек === сантехник? Как вообще вы провели такую связь?
Факт того, что "человек" не является работой, ни "работа" является человеком в графе записан.
Нет, не "записан". Покажете где эта "запись"?
Зависит от того, что мы в графе рисуем.
Как "данные" могут зависеть от "того, что мы в графе рисуем"?! о_О
Если это "любой объект X является У", то ребра нет. Не любой робот является сантехником. И все записанно.
Нет))). Не записано. Давайте так: наличие графа - связь? Отсутствие графа - отсутствие графа или отсутствие связи? Мне реально интерено.
то надо вводить ребра разных цветов
"Выводить"?! Т.е. "вывод" === связь?! Вы вообще о чём?!
или смотреть на 2 графа сразу
Чего?! А как "2 графа сразу" влияют на связи? о_О
Сами сделали какой-то логически противоречивый переход и теперь радуетесь, что поймали меня на противоречии
ЭЭмммм... Нет. Но вот теперь поймал...
Как вы из "робот может быть сантехником" сделали вывод, что "любое "существо", починившее кран — человек" и как это относится к ребрам — вообще неясно.
Почитайте про "логику", плз...
wataru
04.01.2023 21:46Судя по карме, не я один считаю, что вы троль. Больше я на ваш троллинг отвечать не буду.
aktuba
04.01.2023 22:00-1Не, передумал… У меня к вам 1 вопрос: вы на хабре с 11-го года (если верить профилю), но меня посчитали троллем (я с 7-гр, лично знаком с некоторыми пользователями и с Бурумом)? Что я упускаю?
aktuba
04.01.2023 22:05-1Вопрос отпал, кажется - я понял.
https://habrastorage.org/webt/ra/9a/aw/ra9aawy3mukmzezpxk3exrzypz8.png
@Boomburumобрати внимание плз
wataru
04.01.2023 23:13У вас карма отрицательная. Значит, скорее всего, общение с вами вызывает у приносящих пользу на этом ресурсе пользователей желание нажать кнопочку "пусть этот пользователь лучше помолчит". Значит более вероятно, что у нас тут с вами не какое-то недопонимание, а вы спорите, ради того чтобы поспорить.
Зачем вы в соседнем ответе мне дали ссылку на профиль автора статьи, я торже не знаю.
iig
05.01.2023 09:28+1карма = показатель человека?
В некоторых условиях принято считать что да. Как вес == показатель массы.
wataru
05.01.2023 11:01А, так карма = показатель человека?
Нет, конечно. Это полностью независимая от человека и его поведения случайная величина. /s
Ares_ekb
05.01.2023 06:50Реально считаете, что "отсутствие описания" === "отсутствие отношений"?
Давайте так: человек-сантехник-работа. Тут нет отношения к "робот", верно? Может ли "робот" быть сантехником? А человеком? А может-ли он делать работу?
Это зависит от того какая модель используется: основанная на open-world assumption или на closed-world assumption.
Если первая (RDF, OWL, ...), то, да, вы правы: если в модели что-то не описано, то это не значит, что этого не может быть (заранее извиняюсь, если при чтении этого предложения с тремя отрицаниями сломаются какие-нибудь англоязычные люди, зачем-то забредшие сюда).
А если вторая (UML, ER, ...), то отсутствие описания действительно означает отсутствие отношения. Например, в банке отсутствует запись о наличии у меня счетов. По вашему это ничего не значит? Вполне возможно, что у меня всё-таки есть там счёт может быть на тысячу долларов, а может быть и на миллион? Или другой пример: есть граф описывающий кто на кого подписан в социальной сети. Если там есть узел, который не связан с другими, то значит он действительно ни с кем не связан.
В общем, вы спорите о разном. Вы говорите о первом типе моделей, а ваш оппонент - о втором. И вы оба правы.
В общем-то и в RDF никто не запрещает сделать какой-нибудь базовый класс "Объекты, не имеющие отношения с другими объектами" и интерпретировать его соответствующим образом. Или сделать аналогичное свойство.
Всё зависит от интерпретации (семантики) графа. Сами по себе узлы и связи вообще ничего не значат.
Maccimo
04.01.2023 23:32Например вот такие наборы первого блюда, второго блюда и десерта сочетаются. Это графом не запишешь.
Гиперграф, многодольный граф?
wataru
04.01.2023 23:37Ну да, это гиперграф и есть. Я про это как раз и упомянул в конце (правда, без общепринятого названия). Но это уже не граф. И алгоритмы почти никакие из графовых на нем не работают.
А вот многодольный граф тут не подходит. Он все-равно только пары описывает. А я же говорил про тройки. Ибо может быть что {a,b,c} — обладает свойством, а {a,b,d} — нет. Что делать с ребром между a и b из соответствующих долей?
Maccimo
05.01.2023 00:06Но это уже не граф. И алгоритмы почти никакие из графовых на нем не работают.
С точки зрения теории графов — граф. Множество алгоритмов, работающих с ориентированными и неориентированными графами тоже разное, никто не ропщет.
Что мы, кстати, хотим с этим знанием сочетаемости блюд делать?
Может всё там нормально с алгоритмами. Для какого-нибудь кафе с бизнес-ланчами банально готового списка хватит.wataru
05.01.2023 00:23С точки зрения теории графов — граф.
Нет, в теории графов определение графа дано. И гиперграф сюда не натягивается. Там есть слово "парных" перед "связями".
Множество алгоритмов, работающих с ориентированными и неориентированными графами тоже разное, никто не ропщет.
Почти все алгоритмы, работающие на ориентированных графах, работают и на неориентированных (кроме алгоритмов для ациклических графов). Тут пересечение настолько обширное, да и сами ориентированные и неориентированные графы настолько похожие объекты, что их считают разновидностями одного типа.
Что мы, кстати, хотим с этим знанием сочетаемости блюд делать?
Неважно, это был просто пример небинарного отношения. Может, вам надо составить набор хороших троек на неделю без пересечения по вершинам. Или найти подмножество где наибольшее количество троек сочетается. Пример, возможно, не практичный. В википедии написано, что гиперграфы применяются в рассчетах электрических сетей. Какие-то применения у этих структур наверняка есть.
Maccimo
05.01.2023 00:56Неважно, это был просто пример небинарного отношения.
От решаемой задачи зависит выбор оптимальной структуры данных.
В конце концов, мы можем в дополнение к типам узлов «первое», «второе» и «десерт» добавить четвёртый тип, «сочетающийся набор» и без проблем выразим нужное нам отношение.
Ares_ekb
05.01.2023 06:25+1тройки элементов могут обладать каким-то свойством, а могут не обладать. Например вот такие наборы первого блюда, второго блюда и десерта сочетаются. Это графом не запишешь.
Это легко описать. Добавляется ещё одна вершина "комплексный обед" или что-то подобное. Она связана с первым и вторым блюдом и с десертом, и может сама иметь какие-то дополнительные свойства и связи. Есть языки типа RDF или Object-role modeling. Я не могу придумать какие-то реальные вещи, которые нельзя на них описать.
Да, и в обычных ER-моделях N-арные отношения между объектами просто моделируются ещё одной сущностью. Грубо говоря, если нужно связать 3 таблицы, просто добавляем к ним ещё одну.
wataru
05.01.2023 11:01+1Да, вы правы. В такой конструкции даже гиперграф можно описать простым графом.
Hrodvitnir
04.01.2023 19:38+4Звучит так, будто мы могли использовать Паттерн "состояние"
И будто бы даже решение было интуитивно понятнее:)Но ваш подход тоже интересный
Ksoo
04.01.2023 20:58+4Выглядит как одну мелкую проблему, решают в другом месте и сильно сложнее.
Если документ изменился после подписи, то подпись больше не действительна.
gdt
04.01.2023 21:01+6В лоб можно было сделать конечный автомат с каким то состоянием. Заодно и графы там органично смотрятся.
BugM
05.01.2023 04:13+2Так обычно это и делают. И без графов обычно даже. Список запрещенных именно для него переходов в стейте каждого объекта и хватит.
Видимо в курсе про конечные автоматы не рассказали.
santjagocorkez
05.01.2023 00:09+1create type doc_states AS ENUM ('S1', 'S2', 'S3', 'S4'); create type doc_state_flags AS ENUM ('S4_REACHED', 'S4_REACHED_TWICE'); create table docs ( id bigserial not null primary key, status doc_states default 'S1', status_flags int default 0, signature bytea ); create or replace function doc_reached_s4() returns trigger as $$ begin NEW.status_flags = NEW.status_flags | array_length(enum_range(NULL, 'S4_REACHED'::doc_state_flags), 1); return NEW; end $$ LANGUAGE plpgsql; create trigger mark_s4_reached_trigger before insert OR update on docs for each row when ( NEW.status_flags & array_length(enum_range(NULL, 'S4_REACHED'::doc_state_flags), 1) = 0 AND NEW.status = 'S4') execute FUNCTION doc_reached_s4(); create function disallow_signature() returns trigger as $$ BEGIN raise exception 'The document with the ID % has already reached status S4 and thus cannot get signed once more during transition to status S2', OLD.id; end $$ LANGUAGE plpgsql; create trigger prohibit_re_signing_trigger before update on docs for each row when (NEW.signature != OLD.signature AND OLD.status_flags & array_length(enum_range(NULL, 'S4_REACHED'::doc_state_flags), 1) != 0 AND NEW.status = 'S2') execute FUNCTION disallow_signature(); create function doc_reached_s4_twice() returns trigger as $$ begin NEW.status_flags = NEW.status_flags | array_length(enum_range(NULL, 'S4_REACHED_TWICE'::doc_state_flags), 1); return NEW; end $$ LANGUAGE plpgsql; create trigger mark_s4_reached_twice_trigger before insert OR update on docs for each row when ( NEW.status_flags & array_length(enum_range(NULL, 'S4_REACHED'::doc_state_flags), 1) != 0 AND NEW.status = 'S4' AND OLD.status != 'S4') execute FUNCTION doc_reached_s4_twice(); alter table docs add constraint docs_s4_final CHECK ( status_flags & array_length(enum_range(NULL, 'S4_REACHED_TWICE'::doc_state_flags), 1) = 0 OR status = 'S4');Проверяем
insert into docs (signature) values (NULL); select * from docs; update docs set status = 'S2', signature = '\x00' where id = 1; select * from docs; update docs set status = 'S3', signature = '\x01' where id = 1; select * from docs; update docs set status = 'S4', signature = '\x02' where id = 1; select * from docs; update docs set status = 'S1', signature = '\xFF' where id = 1; select * from docs; BEGIN; update docs set status = 'S2', signature = '\x00' where id = 1; select * from docs; ROLLBACK; update docs set status = 'S3', signature = '\x01' where id = 1; select * from docs; update docs set status = 'S4', signature = '\x02' where id = 1; select * from docs; BEGIN; update docs set status = 'S1', signature = '\xFF' where id = 1; select * from docs; ROLLBACK; BEGIN; update docs set status = 'S2', signature = '\x00' where id = 1; select * from docs; ROLLBACK; BEGIN; update docs set status = 'S3', signature = '\x01' where id = 1; select * from docs; ROLLBACK;Какие подводные (конечно, кроме 'ALTER TYPE doc_states ADD VALUE ... BEFORE...', который, например, документацией запрещается и на всех ревью отсекается)?
QtRoS
05.01.2023 00:39+5Тут "надводный", SQL. В эти дни бизнес-логику в БД стараются класть в минимальном объеме. Дискуссии ведутся, есть за и против у обоих вариантов, но "умная" база потихоньку сдает позиции. Удобно, когда средства БД позволяют контролировать целостность и эффективно манипулировать данными, а высокоуровневая логика находится в прикладном слое.
Плюс можно вспомнить про сложность написания тестов, рефакторинга, масштабирования на большое количество типов документов, смены движка БД и т.д.
santjagocorkez
06.01.2023 00:58-2Я не спорю ни с одним сказанным вами словом. Если я уберу DEFAULT из DDL таблицы и заменю там же SERIAL на INTEGER, тогда принимается (с поправкой на обработку случаев, когда status / status_flags не инициализированы)?
Только не говорите мне, что "это бизнес-логика только потому, что там написано CREATE FUNCTION". В этих триггерах бизнес-логики не больше, чем в NOT NULL, PRIMARY KEY (UNIQUE CONSTRAINT), FOREIGN KEY и так далее. Ну, или покажите мне, какое место занимается бизнес-логикой в приведенном куске DDL.
Впрочем, я не настаиваю на реализации этого именно в СУБД, коли хочется закатывать солнце вручную. Можно и в код вынести, благо, код самоочевиден и его реализация на любом более-менее распространённом языке тривиальна. Разве что тогда коду придётся начать знать про поле status_flags, которое к бизнес-логике не относится.
В любом случае, реализация в СУБД или в коде, это приведет к печальному факту: имя этой статье "как я наоверинжинирил".
Rukis
05.01.2023 13:46+2Правила переходов состояний - логика приложения, а не системы хранения данных. В конечном итоге окажется, что во первых приложение всё равно должно гарантировать соблюдение этих правил на своей стороне, а бд в свою очередь не гарантирует выполнение других/новых реализация которых на её уровне может оказаться делом затруднительным/невозможным/накладывающим ограничения.
Не говоря уже о зависимости от sql хранилища, удобства тестировании и тд.
aamonster
Вообще не очень понятно, при чём тут графы, если у документа есть линейная история изменения состояний. Почему нельзя просто пройти по ней от конца к началу, складывая статусы вершин в хэшмап?
Более того: вершины добавляются по одной, так что даже хэшмап не нужен. Просто при переходе в очередное состояние проверить – может, мы в нём уже были?
ArkadiyShuvaev
Например, есть 4ре состояния документа: Статус1 - Статус2 - Статус3 - Статус4
Есть условия: а) можно перейти из Статуса4 обратно в Статус1 не более одного раза. б) Статус2 при второй итерации можно пропустить.
1 итерация: Статус1 - Статус2 - Статус3 - Статус4
2 итерация: Статус1 - Статус3 - Статус4
3 итерация: запрет
Что здесь можно сделать? Не совсем понятна идея с хэшмапом. Там же без if-else для Статус2 не обойтись.
aamonster
Тут не три итерации, а 6 отдельных переходов (и один запрет перехода). Проверка требуется при переходе. Задача куда проще описанной вами, каждый переход проверяется за линейное время, если не оптимизировать (для оптимизации понадобится хранить состояние чуть сложнее, чем просто номер текущего).
Я не спорю насчёт полезности графов, но по вашему описанию задача из другой области)
Кстати, насчёт хэшмапа я погорячился, набор состояний фиксированный, хватит массива бит или чего-то подобного.
Возможно, для вашей задачи действительно полезен алгоритм поиска циклов. Но описали вы задачу, в которой он не нужен. Тогда вы знаете, какой скилл прокачивать следующим: постановку задач.
Format-X22
В такой задаче можно хранить флаг что был подписан второй раз, а кейс с пропуском Статус2 проверять по наличию подписи, ведь мы её храним. Кстати, в этом случае и историю переходов можно не хранить, если этого в бизнес-логике не требуется. Оно всё это ещё и быстрее работать будет, даже если храним таки историю - никаких хождений по графам, читаем данные из колонки в базе, причем в момент выгрузки документа, потому что явно обработка статуса предполагает выгрузку каких-то данных о документе. Заодно аналитикам удобно будет и прочей логике если понадобится - один запрос в базу без рекурсий и мы получили все документы, которые подписаны были дважды. Или только единожды. Быстро и эффективно. Опыт энтерпрайза.