Зависимые объекты и цепочка обновлений

[Dmitriy40]

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

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

Про память, Ваш список начинается с пустого и потом постепенно наполняется объектами (а потом снова усекается до нуля, причём не только с конца!). Т.е. его размер меняется динамически от нуля до в пределе полного количества объектов в сцене. У меня сигналы (точнее конечно сообщения) хранятся в и так существующей системной очереди сообщений процессу и отдельного места не занимают. А остальные переменные всего 3 штуки независимо от количества объектов.

EUgeneUS
Если не ошибаюсь, то этим дополнением Вы тоже задержали запуск начала пересчёта до момента окончания инвалидизации всех зависимых объектов. Т.е. те же две волны, инвалидизация и пересчёт. Тогда разница между нашими вариантами становится в мелких деталях реализации. Например мне не нравятся бродкаст сигналы, они слишком спамят (засирают сеть), сигналы точка-точка в этом плане намного экономнее. Хотя реально первые всё равно превращаются во вторые и кладутся в очередь сообщений каждому процессу (зато даже и тем кому не нужно), ну если конечно не пишем свой планировщик и систему обмена сообщениями.

-- 14.08.2020, 18:25 --

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

[EUgeneUS]

Dmitriy40 в сообщении #1479194 писал(а):

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

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

Dmitriy40 в сообщении #1479194 писал(а):

Например мне не нравятся бродкаст сигналы, они слишком спамят (засирают сеть), сигналы точка-точка в этом плане намного экономнее.

Мне тоже бродкасты не нравятся.

Dmitriy40 в сообщении #1479194 писал(а):

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

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

[rockclimber]

Dmitriy40 в сообщении #1479194 писал(а):

обмен сигналами это фактически часть ОС

А, эти сигналы. Что-то слышал, лет 10 назад даже что-то пробовал (на паскале). Перестал пробовать после того, как повесил нафиг систему. В WinXP пробовал ставить глобальные хуки на клавиатуру и мышь, а из них слал сообщения в свое приложение. Одно неосторожное движение - и усё
Вообще да, обычно использование чего-то, уже реализованного средствами ОС, полезнее, чем свой велосипед. Но тут, кажется, наоборот, помешает. Если сообщения передаются ОС, нам надо проверять их доставку и делать лишние проверки, а если все в один поток идет, то не надо. А еще мне кажется, что я смогу легко доработать свой код, чтобы он работал в несколько потоков. Давайте конкурс устроим. Нужно сгенерировать, например, 1 000 000 объектов, каждому случайным образом выбрать 100 потомков (только надо как-то проследить, чтобы циклов не было), пересчет каждого объекта - это просто какая-нибудь мелкая операция, типа инкремента глобальной переменной. И сравним. Вряд ли мне удастся выиграть по времени с джавой против С++, но надеюсь сильно не отстану. Или можно написать каждому версию в 1 поток и в несколько, и сравнить их скорости. У кого ускорение будет больше.

[EUgeneUS]

Dmitriy40 в сообщении #1479188 писал(а):

Причём вторая волна, валидации, должна посылаться почти всегда строго после полного затухания первой. Исключения возможны, но как определить их возможность в realtime (да ещё и на не обязательно статическом графе связей), а не априори, не вижу. Т.е. можно конечно, но фактически тогда будет происходить построение дерева взаимосвязей от начального узла до всех конечных. А это затратно, причём в каждом узле/объекте. Обмен сигналами почти наверняка менее требователен.

Кстати, вместо дерева можно построить матрицу $N \times N$, где
$N$ - количество объектов.
а элемент матрицы

$$ a_{ij} = \begin{cases} 1,&\text{если есть путь от i-го объекта к j-му}\\ 0,&\text{иначе} \end{cases}$$

Принятие решения о возможности пересчета какого-то объекта будет незатратным. Добавление строки и столбца при создании объекта - тоже. А вот незатратное удаление строки и столбца при удалении объекта не придумал.

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

-- 14.08.2020, 19:16 --

rockclimber в сообщении #1479203 писал(а):

Нужно сгенерировать, например, 1 000 000 объектов, каждому случайным образом выбрать 100 потомков (только надо как-то проследить, чтобы циклов не было), пересчет каждого объекта - это просто какая-нибудь мелкая операция, типа инкремента глобальной переменной.

ИМХО, судя по задаче, описанной ТС, скорее наоборот:
а) количество объектов не более нескольких тысяч.
б) а пересчет - тяжелая операция, типа перемножения больших матриц.

[mihaild]

rockclimber, кажется в вашем коде надо в update добавить проверку isValid. Иначе сигнал на обновление будет идти всеми возможными путями.

EUgeneUS в сообщении #1479204 писал(а):

Добавление строки и столбца при создании объекта - тоже.

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

[Dmitriy40]

EUgeneUS в сообщении #1479204 писал(а):

Кстати, вместо дерева можно построить матрицу $N \times N$, где
$N$ - количество объектов.

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

EUgeneUS в сообщении #1479204 писал(а):

А вот незатратное удаление строки и столбца при удалении объекта не придумал.

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

rockclimber в сообщении #1479203 писал(а):

Давайте конкурс устроим.
...
У кого ускорение будет больше.

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

[EUgeneUS]

Dmitriy40 в сообщении #1479208 писал(а):

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

Не проходит.
Пусть есть цепочка $A \to B \to C$. Есть путь из $A$ в $C$, в клетке $a_{AC}$ матрицы стоит единица.
Удаляем объект $B$, путь из $A$ в $C$ пропал. Нужно обнулить клетку $a_{AC}$. Но она не лежит ни в B-м столбце, ни в B-й строке.

[rockclimber]

mihaild в сообщении #1479207 писал(а):

rockclimber, кажется в вашем коде надо в update добавить проверку isValid. Иначе сигнал на обновление будет идти всеми возможными путями.

Да, немного надо подправить:

Используется синтаксис Java

    public void update(boolean fromParent) {
        if (isValid) {
            isValid = false;
            for (int i = 0; i < children.size(); i++) {
                children.get(i).update(true);
            }
        }
        if (fromParent) {
            invalidParents++;
        }
    }
 

В предыдущей версии объект С обновил бы своих потомков два раза, и у них была бы некорректная информация о количестве инвалидных родителей. Баг не вылез, потому что у С не было потомков.

[mihaild]

А еще у вас recalculate может квадратичное от размера графа время занимать, да еще и список фигур поддерживать. ИМХО лучше просто второй обход запустить, который будет заходить в объект, если мы были его последним невалидным родителем.

[rockclimber]

Так и было задумано. Я исходил из предположения, что пересчет - дорогая операция, а уведомления наследников об окончании пересчета - дешевые. Соответственно, сам по себе пересчет будет выполняться один раз, а много раз будут только уведомления вызываться, а там только одна операция декремента.

mihaild в сообщении #1479222 писал(а):

ИМХО лучше просто второй обход запустить, который будет заходить в объект, если мы были его последним невалидным родителем.

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

[mihaild]

rockclimber в сообщении #1479236 писал(а):

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

Дешевая-то дешевая, но за асимптотикой следить надо.

rockclimber в сообщении #1479236 писал(а):

Я не представляю себе вариант проще, если честно.

Как-то так.

Используется синтаксис C++

struct TObject {
  bool IsValid = true;
  int InvalidParents = 0;
  void Invalidate();
  void Update();
  void Recalc();
  TVector<TObject*> Children;
};

void Update(TObject& object) {
  object.Invalidate();
  object.Update();
  GlobalRedraw();
}

void TObject::Invalidate() {
  if (IsValid) {
    IsValid = false;
    for (auto& child : Children) {
      ++(child->InvalidParents);
      child->Invalidate();
    }
  }
}

void TObject::Update() {
  Recalc();
  IsValid = true;
  for (auto& child : Children) {
    if (--(child->InvalidParents) == 0) {
      child->Update();
    }
  }
}
 

[george66]

rockclimber в сообщении #1479163 писал(а):

При каждом изменении isValid всем прямым потомкам увеличиваем invalidParents на 1

А как мы это делаем? Если рекурсивно (сначала детям, потом детям детей и т.д.), то что делать, если у двух детей общий внук (он увеличится два раза). Придётся сначала составить список всех потомков без повторений. Или мы только детям увеличиваем?
Кстати, интересный вариант задачи: если объект уничтожается (фигура удаляется), он шлёт сигнал "умер" (destroyed). Его дети от этого сигнала тоже умирают и шлют сигнал destroyed и т.д. Рисовальная машинка на каждый сигнал перерисовывает картинку (правда, пересчитывать ничего не надо, просто его не рисовать). Как подождать, пока они все умрут? Тут особенность в том, что умерший объект уже никаких сигналов воспринимать не будет и никакой учёт вести не может.
P.S. Хотя тут ведь сработает общий счётчик сигналов. Каждый объект, прежде чем умереть, меняет переменную signals. Когда все сигналы пришли, можно перерисовать. Замечательно, что здесь такой фонтан идей прекрасно забил!

[EUgeneUS]

george66 в сообщении #1479242 писал(а):

Кстати, интересный вариант задачи: если объект уничтожается (фигура удаляется), он шлёт сигнал "умер" (destroyed). Его дети от этого сигнала тоже умирают и шлют сигнал destroyed и т.д. Рисовальная машинка на каждый сигнал перерисовывает картинку (правда, пересчитывать ничего не надо, просто его не рисовать). Как подождать, пока они все умрут?

Если в ориентированном графе без циклов распространяется какой-то "пожар", то в качестве "индикатора пожара" можно использовать счетчик, предложенный тут
Для работы индикатора необходим флаг на объекте - пожар уже был, или еще нет.
Для удаления объектов таким флагом является само существование объекта.

-- 15.08.2020, 07:43 --

george66 в сообщении #1479242 писал(а):

P.S. Хотя тут ведь сработает общий счётчик сигналов. Каждый объект, прежде чем умереть, меняет переменную signals. Когда все сигналы пришли, можно перерисовать.

А как понять, что пришли все сигналы? Если известно количество тех, кто должен умереть, то да - хватает инкрементального счетчика, а если не известно?

[Dmitriy40]

У меня в коде уже реализован такой счётчик signals, используемый для ожидания прихода всех сигналов инвалидации всех зависимых объектов. Всё что нужно, это добавить третий тип сигналов и его обработку сделать ровно как сигнала invalidate (но без модификации objects если не надо подсчитывать количество удалённых объектов). Как только signals обнулился — все затронутые объекты пересчитаны (и умерли) (и последний умерший должен обнулить objects после отсылки накопленного значения куда-то если оно подсчитывается).

[rockclimber]

george66 в сообщении #1479242 писал(а):

rockclimber в сообщении #1479163 писал(а):

При каждом изменении isValid всем прямым потомкам увеличиваем invalidParents на 1

А как мы это делаем? Если рекурсивно (сначала детям, потом детям детей и т.д.), то что делать, если у двух детей общий внук (он увеличится два раза). Придётся сначала составить список всех потомков без повторений. Или мы только детям увеличиваем?

Вот еще раз мой код, но теперь с комментариями:

Используется синтаксис Java

public void update(boolean fromParent) {   // этот метод вызывается из родителя и сообщает, что родитель стал невалидным
        if (isValid) {                     // если текущий объект был валидным, то:
            isValid = false;               // делаем его невалидным и потом
            for (int i = 0; i < children.size(); i++) {
                children.get(i).update(true);    // оповещаем каждого потомка, что у него один родитель стал невалидным
            }
        }
        // счетчик невалидных родителей увеличиваем на единицу
        if (fromParent) { 
            invalidParents++;
        }
    }
 

В сумме это работает так: каждый родитель вызывает метод update у потомка; потомок становится невалидным и передает информацию дальше по цепочке. Оповещение потомков срабатывает только при первом вызове от родителя (пока у самого объекта isValid = true), а invalidParents++; срабатывает каждый раз - чтобы корректно посчитать количество невалидных родителей. В первоначальной версии у меня была ошибка, о которой вы говорите, на нее же указывал mihaild, а это - исправленная версия.

george66 в сообщении #1479242 писал(а):

Кстати, интересный вариант задачи: если объект уничтожается (фигура удаляется), он шлёт сигнал "умер" (destroyed). Его дети от этого сигнала тоже умирают и шлют сигнал destroyed и т.д. Рисовальная машинка на каждый сигнал перерисовывает картинку (правда, пересчитывать ничего не надо, просто его не рисовать). Как подождать, пока они все умрут? Тут особенность в том, что умерший объект уже никаких сигналов воспринимать не будет и никакой учёт вести не может.

Мммм... Я сначала написал длинный ответ, а потом удалил. Удаление дочернего объекта должно случиться, только если у него "умерли" все родители, правильно? Тогда алгоритм усложняется, надо подумать. Кажется, тогда стоит вместо логической переменной isValid сделать статус с тремя возможными значениями (Valid, Invalid, Dead), обновлять всех потомков (и у каждого считать количество мертвых и невалидных родителей отдельно), потом сначала все объекты, у которых все родители мертвые, удалить, а потом пересчитать невалидные объекты.
В любом случае, как мне кажется, асинхронные сигналы тут не очень удобны (как я понял из объяснений Dmitriy40, они асинхронные), потому что вам мало отправить сигнал, вам нужна гарантия, что он получен и обработан. Поэтому я предлагаю вместо сигналов делать прямые вызовы методов потомков. Как только метод завершился, вы точно знаете, что все обработано.
Хотя возможно я просто не привык к работе с сигналами.