Russian Qt Forum
Март 28, 2024, 12:08 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1]   Вниз
  Печать  
Автор Тема: Отслеживание счетчиков  (Прочитано 6332 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Ноябрь 01, 2017, 12:05 »

Добрый день

Есть такая структурка
Код
C++ (Qt)
struct Node {
 ...
 Node * m_owner;
 QList<Node *> m_child;   // чайлв ноды
 
 QScopedPointer<Container> m_data;  // контейнер данных
};
Нод может быть или "папкой" (тогда mData = null) или "листом" (есть m_data но нет чайлдов), но не тем и другим вместе.

Для UI нужно знать максимальное число эл-тов что сидят в ноде m_data. Для нода-листа это просто m_data->size(). Для узла это макс из всех его чайлдов рекурсивно. Ну и надо знать макс по всем нодам. Дерево довольно развесистое, поэтому пробегаться по всему для каждого запроса UI не годится. Какие есть предложения?

Спасибо  
« Последнее редактирование: Ноябрь 01, 2017, 14:22 от Igors » Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #1 : Ноябрь 01, 2017, 13:03 »

Добавить int m_nodesCount в структуру, изначально и каждый раз при изменении данных рекурсивно устанавливать для "родителей" m_owner->m_nodesCount=-1.

При запросе макс. числа нодов обновлять m_nodesCount свой и рекурсивно чайлдов, пока m_nodesCount<0.
Иначе вернуть m_nodesCount.

Записан

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #2 : Ноябрь 01, 2017, 14:33 »

Добавить int m_nodesCount в структуру, изначально и каждый раз при изменении данных рекурсивно устанавливать для "родителей" m_owner->m_nodesCount=-1.

При запросе макс. числа нодов обновлять m_nodesCount свой и рекурсивно чайлдов, пока m_nodesCount<0.
Иначе вернуть m_nodesCount.
Тогда уж что-то типа m_MaхDataСount. Но вот так запросто добавлять новый (полноценный) член данных только для мелочи в UI - не западло ли?

И тут такая неприятность: отследить "факт изменения" из класса Container можно, но непросто - там масса всяких clear, erase и др. А вот отследить из класса Node практически нереально. А делать у Container член Node * m_owner ну очень не хочется - придется все время заботиться о нем при копировании и.т.п.
Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #3 : Ноябрь 03, 2017, 00:33 »

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

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #4 : Ноябрь 03, 2017, 12:11 »

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

Ну это ж стандартная вещь - или памятью жертвовать (кэш же), или скоростью.
Ну а почему не кеш? Правда придется редактировать его в деструкторе Node - переживу. Только вот что (или как) хранить в кеше?
Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #5 : Ноябрь 04, 2017, 00:57 »

Поскольку важен не контент нодов, а только их количество, то m_nodesCount для каждого нода и будет кэшем.
Записан

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #6 : Ноябрь 04, 2017, 11:27 »

Поскольку важен не контент нодов, а только их количество, то m_nodesCount для каждого нода и будет кэшем.
Хмм,,, А может так
Код
C++ (Qt)
typedef QPair<Node *, int> TCount;
typedef QHash<Node *, TCount> THash;
 
Счетчик изменился для нода - если этот нод был с макс счетчиком у родителя, то second = -1 (нужен пробег для новой установки макс). В хеш храним только узлы + 1 общий. Покритикуйте
Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #7 : Ноябрь 05, 2017, 23:42 »

Наверное, можно еще проще - каждый нод знает своего нода-родителя, и если нод изменился, то инвалидирует счетчики всех предков по цепочке до верхнего нода. А верхний уже делает пересчет, если надо.
Записан

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #8 : Ноябрь 06, 2017, 08:10 »

Наверное, можно еще проще - каждый нод знает своего нода-родителя, и если нод изменился, то инвалидирует счетчики всех предков по цепочке до верхнего нода. А верхний уже делает пересчет, если надо.
Чтобы инвалидировать родителю нужно хранить указатель на макс чайлд, Поэтому и заводится пара TCount.
На удаление - вроде тоже все норм, отрабатывается так же как и изменение счетчика. Еще проблемы? 
Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #9 : Ноябрь 06, 2017, 10:20 »

ну, "в теории" должно работать, вроде как...
теперь надо писать Кодъ, может что и вылезет Улыбающийся
Записан

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #10 : Декабрь 03, 2017, 13:12 »

теперь надо писать Кодъ, может что и вылезет Улыбающийся
Кот написан (и даже работает  Улыбающийся). Но, боже, почему получилось так сложно (и много)? Вкратце повторю задачу

В дереве нужно быстро (не проходя каждый раз по всем нодам) определять максимальное число данных. Аналогия: в файловой системе/менеджере встали на папку/мамку - должен быть выдан максимальный размер файла внутри этого фолдера

Может есть способ попроще чем обсуждался выше?
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.087 секунд. Запросов: 23.