Комментарии 49
Алгоритм выглядит интересно, обязательно проверю его на досуге. В своё время делал его через раскрашивание рёбер, и не для просто инициализации, а в целом для потока вычислений. Вопрос: на зацикленных вариантах проверяли? типа a->b->a.
Вот кстати да. Что должна делать прошивка с циклической зависимостью? Зависать? Падать?
Если есть цикл, то тупо невозможно проинициализировать это все в порядке, не нарушая зависимости. Это будет продетектировано любым из стандартных алгоритмов, когда как алгоритм автора, похоже, повиснет.
Один из ночных кошмаров - программа для микроконтроллера компилируется но залипает где то на инициализации.
Это будет продетектировано любым из стандартных алгоритмов, когда как алгоритм автора, похоже, повиснет.
Тогда всегда можно выполнить топологическую сортировку утилитой make
make тоже заметит циклическую зависимость и даже цикл выведет, насколько я помню. Но вообще, там рекурсия, если вам важно.
А так да, make отлично эту задачу решает. Правда, это весьма остроумно додуматься его тут применять.
Кстати о рекурсии, с которой автор боролся. Я почему-то решил, что нужно экономить байты, потому что алгоритм должен работать на микроконтроллере. А если на компе.. Блин, у вас никогда не будет столько периферии, чтобы вышел такой огромный граф, чтобы ему не хватило стека на компе. Даже если постараться и реализовать комбо из рекурсии и О(N^3).
phony целями?
Вот автор разобрался и сделал так: https://habr.com/ru/articles/818917/comments/#comment_26897515
Наверняка, есть более красивые и/или кошерные варианты.
Да прошивка-то про графы ничего знать не знает.
Ей только готовый массив указателей на функции скармливают.
Это PC для прошивки хороший init подбирает (кодогенерация) и пытается распетлять ситуацию.
Чтобы не выполнять приседания с кодированием зависимостей, рекурсией и прочими ограничениями, порядок инициализации нужно определять на этапе сборки прошивки. Утилита make умеет в топологическую сортировку ;)
Все что можно сделать в compile time - нужно делать в compile time.
А если нужно динамически изменять необходимые в данный момент компоненты прошивки? Не собирать же прошивки со всеми возможными комбинациями.
Утилита make умеет в топологическую сортировку ;)
Гениально! Спасибо за идею!
Утилита make умеет в топологическую сортировку ;)
Да. Хотя бы вот так
ADC: GPIO NVIC DMA AdcChannels
@echo $@
$(eval INIT_ORDER += $@)
@echo $@ >> init.txt
UnitTest :Cli UDS Param
@echo $@
$(eval INIT_ORDER += $@)
@echo $@ >> init.txt
WatchDog :Clk
@echo $@
$(eval INIT_ORDER += $@)
@echo $@ >> init.txt
Writer :Stream
@echo $@
$(eval INIT_ORDER += $@)
@echo $@ >> init.txt
INIT_ORDER +=
SW_COMP += UnitTest
SW_COMP += StartPause
SW_COMP += AdcChannels
....
SW_COMP += NVIC
SW_COMP += ADC
include sw_comp_dep.mk
init: $(SW_COMP)
@echo $@
@echo $(info ORDER:[$(INIT_ORDER)])
@echo $(info SET:[$(SW_COMP)])
запускаем
make.exe --always-make -i -k init
и готово
Удалось составить консольную Cи утилиту, которая находит топологическую сортировку для графа на основе списка смежности.
интересная тема, осталось только выяснить откуда берутся списки смежности. Как вы определяете от чего эта библиотека/компонента/кусок кода зависит? в какой форме хранятся у вас зависимости в компонентах? или вы какую то отдельную базу данных зависимостей поддерживаете, тогда как к этой базе из прошивки обращаться?
осталось только выяснить откуда берутся списки смежности. Как вы определяете от чего эта библиотека/компонента/кусок кода зависит?
Автор программного компонента создает graphviz файл, где указывает от чего зависит его программный компонент.
Про это есть отдельный текст
Генерация зависимостей внутри программы
https://habr.com/ru/articles/765424/
надо же разработка софта для микроконтроллеров доросла до компонентного подхода! У меня к сожалению нет доступа к енвайронменту с такими возможностями (правилами, правила создают возможности, как ни странно). Но я таким пользовался в мире других компонент не связаных с ембедед разработкой еще 20 лет назад.
Интересно!
То есть надо обойти граф в порядке увеличения количества зависимостей. В дискретной математике эту процедуру называют Топологическая Сортировка графа.
Неверная формулировка. Тут надо обойти граф так, чтобы все зависимости были от следующих вершин к предыдущим. Количество зависимостей тут не важно.
Есть специальные алгоритмы для построения этого обхода. Однако они требуют динамического выделения памяти и рекурсию. Мне, как программисту микроконтроллеров,
Но при этом вы пишите консольную утилиту! Да, у вас привычки, но это всего-лишь привычка, а не ограничения для задачи. Можно скопировать тот же код из википедии.
А так, рекурсию всегда можно реализовать через ручной стек. При этом вы заранее знаете его максимальный размер, поэтому вам не надо будет даже никакого динамического выделения памяти. Нужен лишь один массив для стека + один массив, где для каждой вершины будет храниться, сколько ее соседей уже обработано. При доставании из стека, если у вершины не все еще обработано, кладете ее назад в стек, увеличиваете счетчик для вершины и кладете в стек очередную зависимость. Если все обработано, то выводите вершину в ответ.
Потом, есть другой подход, основанный на обходе в ширину. Сначала запустите обход в ширину со всех ваших целевых вершин. Пометьте все вершины, которые вы обойдете. Это будут вершины, которые в итоге придется проинициализировать (а вообще незадетые компоненты не обойдутся). Подсчитайте для каждой компоненты, от скольки она зависит. Так же постройте обратный граф - где записаны не зависимости, а кто зависит от каждой вершины.
Потом поместите в очередь те нужные компоненты, у которых 0 зависимостей. При доставании из очереди выводите вершину в ответ и уменьшайте счетчик зависимостей для всех вершин, которые от текущей зависят. Если там получился 0 (и вершина "нужная"), то добавляйте ту вершину в очередь.
Первый обход в ширину можно опустить, если у вас все компоненты так или иначе используются.
В обоих случаях удобно сначала преобразовать граф к числам. Составьте массив строк и каждую строку замените на ее номер в массиве.
Эти оба алгоритма работают гарантированно за O(V+E). Правда, могут быть проблемы с заменой произвольных строк на числа, если не использовать Trie. Но у вас там все идентификаторы - символы. Когда как ваш алгоритм, похоже, работает за O(V^3).
Для избавления от динамической памяти можно хранить граф в виде матрицы смежности, или в виде списков в массиве, для экономии памяти:
int beg[kMaxEdges]; // начало ребра
int en[kMaxEdges]; // конец ребра
int next[kMaxEdges]; // следующее ребро в списке для начала ребра
int rnext[kMaxEdges]; // следующее ребро в обратном графе для конца ребра
int first[kMaxNodes]; // первое ребро в списке для вершины в графе
int rfirst[kMaxNodes]; // первое ребро в списке для вершины в обратном графе
// инициализация
int num_edges = 0;
memeset(first, -1, sizeof(first));
memeset(rfirst, -1, sizeof(first));
void AddEdge(int b, int e) {
beg[num_edges] = b;
en[num_edges] = e;
next[num_edges] = first[b];
first[b] = num_edges;
rnext[num_edges] = rfirst[e]
rfirst[e] = num_edges;
++num_edges;
}
// обойти все вершины, от которых зависит v
for (int e = first[v]; e != -1; e = next[e]) {
int u = en[e];
}
// обойти все вершины, котрые зависят от v
for (int e = rfirst[v]; e != -1; e = rnext[e]) {
int u = beg[e];
}
Ничего, скоро таких статей в интернете сильно поубавится.
ChatGPT Code Copilot гораздо понятней объясняет алгоритмы и пишет код
Вот пример сортировки (DAG - Directed Acyclic Graphs)
Топологическая сортировка графа выполняется только для ацикличных направленных графов (DAG - Directed Acyclic Graphs). Этот алгоритм упорядочивает вершины так, что для каждого ребра uv, вершина u предшествует вершине v в отсортированном порядке.
#include <stdio.h>
#define MAX_VERTICES 100
typedef struct {
int V;
int E;
int adj[MAX_VERTICES][MAX_VERTICES];
int indegree[MAX_VERTICES];
} Graph;
void createGraph(Graph* graph, int V, int E) {
graph->V = V;
graph->E = E;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
graph->adj[i][j] = 0;
}
graph->indegree[i] = 0;
}
}
void addEdge(Graph* graph, int src, int dest) {
graph->adj[src][dest] = 1;
graph->indegree[dest]++;
}
void topologicalSort(Graph* graph) {
int V = graph->V;
int queue[MAX_VERTICES];
int front = 0, rear = 0;
int topOrder[MAX_VERTICES];
int index = 0;
for (int i = 0; i < V; i++) {
if (graph->indegree[i] == 0) {
queue[rear++] = i;
}
}
while (front < rear) {
int u = queue[front++];
topOrder[index++] = u;
for (int v = 0; v < V; v++) {
if (graph->adj[u][v] == 1) {
if (--graph->indegree[v] == 0) {
queue[rear++] = v;
}
}
}
}
if (index != V) {
printf("Граф содержит цикл\n");
} else {
printf("Топологический порядок: ");
for (int i = 0; i < index; i++) {
printf("%d ", topOrder[i]);
}
printf("\n");
}
}
int main() {
Graph graph;
int V = 6, E = 6;
createGraph(&graph, V, E);
addEdge(&graph, 5, 2);
addEdge(&graph, 5, 0);
addEdge(&graph, 4, 0);
addEdge(&graph, 4, 1);
addEdge(&graph, 2, 3);
addEdge(&graph, 3, 1);
topologicalSort(&graph);
return 0;
}Хотя автор не показал, что он действительно имеет дело с DAG.
И выбрал довольно сомнительный вариант применения сортировки графов.
У этого решения 3 проблемы: он не работает со списком начальных вершин, как в статье, он обходит весь граф, а не только достижимые вершины (инициализирует вообще все, а не только нужное), тут граф храниться в виде матрицы смежности, что может быть слишком много.
Ну и, тут ничего не объяснено. А так, GPT почти воспроизвел мое предложение с методом на основе обхода в ширину. Правда, тут ребра развернуты.
Ну и главное, если гпт тут где-то что-то нагаллюционировал, то вы этого даже не заметите.
Сегодня ChatGPT лагает, поэтому выложил первый же его ответ.
И там все объяснено, просто я выложил не весь ответ. Полный ответ от ChatGPT потянет на хорошую статью.
А так там можно тюнингировать код под любые хотелки.
Человек так не сможет.
Никогда не пологайтесь на ответ от GPT нейросеток по теме, в которой вы не эксперт. Как удобный инструмент для экономии времени в поиске или написании каких-то простых вещей - оно отлично работает. Пока вы можете полностью понять весь ответ и сразу распознать галлюцинации. Но как источник знаний - нет, из-за сильно ненулевого количество ложных и очень прадоподобных ответов (ведь сетка натренерована давать правдоподобные ответы).
Это и есть простая вещь. Только граница простых вещей у AI сдвигается вверх каждый день.
ChatGPT напишет и проверочный код если надо и исправит ошибки если надо.
А так приведенный код достаточно примитивен. Быть "экспертом" в этом алгоритме это в все равно что быть экспертом по арифмертике.
Я сейчас с помощью ChatGPT уже успешно осваиваю SDK от Infineon. Еще месяц назад такое трудно было представить.
Это и есть простая вещь
Простая вещь = вы понимаете каждое слово и строчку в коде. В конкретном случае, вы должны знать про обход в ширину и понимать, почему он работает, чтобы понять, что GPT предложил вам его модификацию.
ChatGPT напишет и проверочный код
Иногда может допустить одну и ту же ошибку и в проверочном коде. Например, я как-то спрашивал его написать класс, чтобы он принимал числа и выдавал максимальное среди K последних пришедших. GPT уверено писал код, который искал k-ое максимальное с конца каждый раз. И тесты под этот код сделал правильные. А в комментариях копировал мой вопрос и даже название функции дал, вроде MaxOfLastK().
Быть "экспертом" в этом алгоритме это в все равно что быть экспертом по арифмертике.
Ну не совсем. Это простой алгоритм да, но доказательство, что он, например, проинициализирует все, в случае если это возможно - чуть сложнее, чем 2+2. Тут нужна математическая индукция.
Я сейчас с помощью ChatGPT уже успешно осваиваю SDK от Infineon.
Вот как раз обучение - это тот самый кейс с ускорением поиска. Если он вам выдает несуществующий метод из документации, вы это сразу заметите.
Вы свой код привели без проверочных тестов и без тестовых данных и без понятного описания.
И именно поэтому я обратился к ChatGPT. От человека не добиться такого подробного, структурированного и ясного описания.
Вы свой код зачем выложили? Наверно чтобы немного просвятить автора. (я отметаю другие эгоистичные мотивы). Ну так ChatGPT это делает лучше. Вот и все. И не важно как ChatGPT устроен и для чего он нужен по чьему-то мнению.
Ну так ChatGPT это делает лучше.
Вот как раз нет, часто наоборот.
Люди тоже иногда ошибаются, но чаще потому что что-то забыли или не заметили что-то, а не галлюционируют вообще не имеющие отношения к реальности утверждения (шизофреников игнорируем - их пренебрежимо мало). Потом, с людьми можно вступить в конструктивный диалог, когда как GPT будет бесконечно говорить "да, вы абсолютно правы, вот новая версия с новыми галлюцинациями".
Вы свой код привели без проверочных тестов и без тестовых данных и без понятного описания.
Код там - это лишь структура данных с исчерпывающими примерами, как ее использовать.
И толку от этих тестов, если они тоже нагаллюционированы бывают?
От человека не добиться такого подробного, структурированного и ясного описания
Это да. Но надо помнить, что он может подробно, ясно и структурированно объяснять галлюцинации. Поэтому связка GPT+человек, разбирающийся в теме - это очень продуктивный подход. Копипастить ответы GPT по интернету - в основном засорение интернета.
Если бы вы спросили у него, узнали про такой алгоритм, поняли его и сказали "Вот такой вот алгоритм на основе BFS есть. Вот код от chatgpt (я проверил)", то я бы к вам не придирался.
Кстати, возвращаясь к вашему комментарию:
Ничего, скоро таких статей в интернете сильно поубавится.
Скорее наоборот. Скоро в интернете будет экспоненциально расти мусор собранный из копипасты выхлопа от ботов без какого-либо осмысления и проверки.
И еще, а зачем копипастить ответ от GPT, если автор сам может у него все спросить?
Код похож на перевод с Си++ кода с гиксов.
Давайте я вам расскажу, почему меня ваш комментарий просто бесит. Я тоже могу скормить загловок статьи и пару пожеланий ChatGPT и скопировать сюда его ответ. И вы можете. И вообще все пользователи хабра. И мы все можем так сделать вообще в любой теме на хабре и вообще на любом сайте! Поскольку ответы случайны - с 100 разных вариаций на каждую тему наберется легко. В том числе взаимнопротиворечащих. Из них, правда, с десяток или с два будут правдоподобным бредом. И это не потребует никаких знаний или множества действий. Ctrl-C, Ctrl-V + одна фараза от себя. Мозг не задет, как говорится.
Но если так сделают все, то интернет кончится. Это только повышает энтропию и засоряет инфосферу. Редко несет пользу. И очень часто - вред. В политических темах уже давно бот на боте ботом погоняет. Через chatGPT вы на тот же уровень опускаете инженерные темы.
На всяких stackoverflow и qna.habr.com это уже проблема. Каждый второй любитель GPT просто копипастит ответы оттуда. Очень часто невпопад и неправльные. За это уже давно сразу банят. И хорошо, если они еще ленятся и просто копипастят. А ведь некоторые гады еще и просят ответ краткий выдать или редактируют его, и тогда даже по стилю не сразу видно, что это GPT.
В конкретном случае он выдал вам правильный алгоритм. Но вам надо помнить, что это вам тут повезло. Это вероятностый инструмент.
Вам нравится им пользоваться - на здоровье. Используете его как источник знаний для себя, а потом уже свои знания, проверенные и переработанные постите где хотите, как свои знания, мысли и идеи. Будьте готовы их аргументировать, о них спорить и отвечать за них. А тут вы просто что-то скопировали, мол "мопед не мой, я просто разместил объяву". Иначе, ну зачем нам тут посол от GPT. Кому надо, может и сам спросить у него. Опять же, представьте, что так делают все. Думаете, будут комментарии на хабре все еще так же интересны?
Согласен с вашим возмущением. Неприятно когда постят непроверенный код.
Но знаете, интернет давно уже выработал рефлекс не верить никакому коду если нет сторонних источников доверия. Нет веры и авторам, даже если они клянуться, что всё проверили.
С ChatGPT у меня очень счастливая история. А получаю от него просто класные безошибочные скрипты на Python, да и на C простые функции он отлично выдает.
Генерил функции с API OpenSSL, тоже отлично. Да, там встречались опечатки в именах функций API, но такие очевидные, что грех жаловаться.
А вот так просто получить нужный код от ChatGPT не выйдет. Нужно точно и тонко задать вопрос или даже цепочку вопросов. В этом и проявляется компетенция.
Автор не спросил и не спросит у ChatGPT. Потому что тот ему не ответит нужным образом. А знаете почему? Потому что сама тема галюциногенная (какой-то раздутый граф инициализации периферии, рисуемый вручную). Такой проблемы, как в статье просто не существует в малых встраиваемых системах, если там сознательно её не культивировать.
Чота я не смог понять суть задачи. Есть у вас компонент А и компонент B, который зависит от A. Ну и делаем:
A* a = init_a();
B* b = init_b(a);
Всё, мы красавчики. Куда тут прилеплять ваш алгоритм? Вы конечно можете попытаться сказать что функция init_b не принимает на вход никаких аргументов. Но простите, откуда она тогда возьмёт зависимость a?
Тут под зависимостью подразумевается то, что компонент B вызывает API из компонента A.
Какой апи? Статические функции без состояния? Так в них ничего инитить не надо. А если там структурки с данными, то возвращаемся к вопросу - откуда зависящий компонент собрался взять ссылку на экземпляр зависимого компонента?
Вы пишете что описываете текстовыми файликами что от чего зависит. Зачем? Зависимость и так уже выражена кодом. Нельзя дернуть init_b раньше чем init_a, потому что иначе вам нечего передавать в init_b.
API это функции. Вот например драйвер кнопок для своей работы вызывает функции из GPIO и Time.
Значит у программного компонента Button две зависимости GPIO и Time
откуда зависящий компонент собрался взять ссылку на экземпляр зависимого компонента?
У зависящего компонента в конфиге есть натуральное число на номер экземпяра зависимого компонента.
У каждого программного компонента есть функция, которая по номеру экземпляра выдает структуру.
DmaChannelHandle_t* DmaChannelGetNode(uint8_t num);
const DmaChannelConfig_t* DmaChannelGetConfig(uint8_t num);
DmaChannelInfo_t * DmaChannelGetInfo(uint8_t num, DmaChannel_t channel);
DmaChannelHandle_t * DmaChannelGetNodeItem(uint8_t dma_num, DmaChannel_t channel);
DmaChannelHandle_t* DmaChannelGetNode(uint8_t num);
Как это работает? Откуда возникает DmaChannelHandle_t*? Там внутри статическая мутабельная переменная условного вида DmaChannelHandle_t handles[NUM_HANDLES]? Если да - ну штош, вы сами себе создали проблему, потому что к этой переменной действительно можно обратиться до её инициализации чем-то содержательным. Не делайте так :) Делайте dependency injection, когда не компонент лазит по всей памяти, доставая свои зависимости, а они явным образом передаются в него.
У меня и используется Dependency injection. Код PWM3 по натуральному числу 20 получает структуру TIMER20.
Там внутри статическая мутабельная переменная условного вида
DmaChannelHandle_t handles[NUM_HANDLES]
На каждый канал DMA (их там 12) есть своя структураDmaChannelHandle_t
Если да - ну штош, вы сами себе создали проблему, потому что к этой переменной действительно можно обратиться до её инициализации чем-то содержательным. Не делайте так :)
Никакой проблемы нет. Структура хранит флаг is_init. Getter выдаст NULL если false=is_init
del
Как составить функцию инициализации микроконтроллера (Топологическая сортировка графов утилитой Make)