Алгоритм топосорта который я знаю просто запускает дфс из какой-то не посещенной ноды

Если проблема с тем что это лес то оно вроде решает ее

Да, сорри, это я затупил.
Большое спасибо.

А в двоичном дереве поиска структура проекции элемента сохраняется для ключа или для значения?

Зачем так сложно?

Есть же более проще вариант

Хз куда проще чем просто дфс

И потом развернуть

Подсчёт степеней по входящим+последовательное удаление вершин без входящих

По коду звучит длиннее

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

observe():
  new_avg_up_time = grow_up ? window_width : 0; //in case last measurment was long ago (more than window size)
  if (from_last_measurment < window_width) {
    inflation = (previous_avg_up_time / window_width) * from_last_measurment;
    new_avg_up_time = previous_avg_up_time - inflation + (grow_up ? from_last_measurment : 0);
  }

Как мне оценить насколько это точно считает среднее? Вообще адекватное решение или нет? Проконсультируйте пожалуйста по теме насколько возможно подробно.
(условно у меня ресурс или занят на 100% или свободен и я хочу считать loadavg его утилизации)

https://en.m.wikipedia.org/wiki/Moving_average

EMA

проверить - запусти идеальный алгоритм и сравни

начало и конец окна не важны если у тебя есть хотя бы 1 число с прошлого окна

играйся с "затуханием" пока не получишь нужный ответ в твоем отрезке времени

тупое решение - иметь 2 переменных и через случайные промежутки времени смотреть. Занято? a+=1. Свободно? b+=1. Потом сравни их. и оба \2 чтобы не было переполнения

Спасибо. Вроде то, что я вывел - сводится к EMA, а эксперименты  вроде показывают адекватные данные.

если у тебя либо 0 либо 100% то действительно лучше считать суммарное время работы на 100% и делить на общее время, если ты хочешь честное среднее получить

Вообще, если подумать, то мы должны уметь строить весовые функции вида poly(t)*e^(-at) локальными формулами, и я удивлюсь, если задачу апроксимации окна такими функциями никто не решал

Здравствуйте! Подскажите пожалуйста, как находить остаток от деления отрицательных чисел на C++.

Число % делитель = остаток