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

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

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

Сообщений: 11445


Просмотр профиля
« : Июнь 23, 2011, 10:22 »

Добрый день

Затеял изменения и хочу переделать базовый класс написанный (не мной) очень давно и работающий по сей день

Код
C++ (Qt)
struct CBase {
long mObjectID:   // уникальное ID объекта
 
CBase * mPrev;   // предыдущий объект (все объекты связаны в список)
CBase * mNext;   // следующий объект
 
CBase * mPrevTyped;   // предыдущий объект того же типа (унаследованного от CBase)
CBase * mNextTyped;   // следующий объект  того же типа
};
 
Требуемая ф-циональность
- находить объект по ID - сейчас, увы, это решается перебором всего списка 
- находить/вставлять/удалять объект по "общему" индексу
- находить/вставлять/удалять объект по индексу объектов такого типа  (сейчас головы/хвосты этих списков собраны в отдельном векторе)

Какие есть соображения ?

Спасибо
Записан
LisandreL
Птица говорун
*****
Offline Offline

Сообщений: 984


Надо улыбаться


Просмотр профиля
« Ответ #1 : Июнь 23, 2011, 11:02 »

- находить объект по ID - сейчас, увы, это решается перебором всего списка
Вариант 1:
Статический приватный QMap/QHash< long, CBase* > в который объект записывается в конструкторе и удаляется в деструкторе. Если возможна многопоточность, то статический же QReadWriteLock для защиты.

Вариант 2:
Если тип и генерация id не важны, то можно как mObjectID использовать сам указатель, т.е. size_t(this).
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #2 : Июнь 23, 2011, 11:42 »

Если тип и генерация id не важны..
Важны т.к. указатель не уникален для delete/undo

Статический приватный QMap/QHash< long, CBase* > в который объект записывается в конструкторе и удаляется в деструкторе.
Как говорит молодежь "решение должно быть комплексным" Улыбающийся Пристроить map (или др. контейнер) для быстрого поиска по ID я могу и сейчас, но по существу это не пере-планирование класса а заплатка, решающая одну проблему, да и то плохо. Зарегистрировав ID в конструкторе мы еще не добавили объект в "списки" (или в то что вместо них в новом классе) и получаем "неконсистентность" организации. объектов. Заметим что для локального объекта (созданного на стеке) пока неясно - стоит ли разрешать его регистрацию или нет.
Записан
LisandreL
Птица говорун
*****
Offline Offline

Сообщений: 984


Надо улыбаться


Просмотр профиля
« Ответ #3 : Июнь 23, 2011, 12:00 »

Зарегистрировав ID в конструкторе мы еще не добавили объект в "списки" (или в то что вместо них в новом классе) и получаем "неконсистентность" организации. объектов.
Почему б этот map и не считать глобальным списком объектов.

Заметим что для локального объекта (созданного на стеке) пока неясно - стоит ли разрешать его регистрацию или нет.
Про то, что объекты могут и не попадать в список вы не говорили в первом посте и это совершенно не очевидно.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #4 : Июнь 23, 2011, 12:18 »

Почему б этот map и не считать глобальным списком объектов.
А как из нее брать по индексам ? И где взять счетчик(и) объектов нужного типа ?

Про то, что объекты могут и не попадать в список вы не говорили в первом посте и это совершенно не очевидно.
Я этого и сейчас не утверждаю (самому неясно Улыбающийся). Просто здравый смысл говорит что локальному объекту там делать нечего.

Общее замечание: требуется тщательное обдумывание, т.к. класс базовый для довольно большого проекта. По-быстрому пристегнуть что-то прочитанное в Ассыстант - ну конечно хорошо если бы так получилось, но оно так получаться не обязано.
Записан
LisandreL
Птица говорун
*****
Offline Offline

Сообщений: 984


Надо улыбаться


Просмотр профиля
« Ответ #5 : Июнь 23, 2011, 14:38 »

А как из нее брать по индексам ?
map.value( mObjectID );
Доступ через функцию, а не на прямую, что бы локером защитить при надобности.

И где взять счетчик(и) объектов нужного типа ?
Вариантов много, один из - что-то вроде ещё одной коллекции QMap< type, list >.

type - здесь идентификатор типа. Им может служить type_info* (у классов должны быть виртуальные методы, например деструктор) или MetaTypeId или ещё что-то что придумаете и что сумете для нужного класса получать.

list - собственно список нужного типа. Если нужен и с известным классом доступ по индексу можно тот же QMap/QHash< long, CBase* > использовать. Если не нужно можно QList< CBase * > (или другую коллекцию смотря какие действия критичны по времени выполнения).

P.S. Вынужден признать, что не помню, должно ли type_info правильно работать в конструкторе базового класса. Надо смотреть по стандарту, где заполняется виртуальная таблица.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #6 : Июнь 23, 2011, 15:34 »

Многопоточность не требуется, требования к скорости вполне лояльны - ну конечно не прямой перебор чтобы найти объект по индексу. Технические подробности (как использовать указатель на typeinfo и.т.п.) сейчас несущественны, нужно спланировать надежную и хорошо инкапсулированную структуру данных чтобы потом не пришлось "ловить блох"
А как из нее брать по индексам ?
map.value( mObjectID );
Доступ через функцию, а не на прямую, что бы локером защитить при надобности.
Так это поиск по ID, индекс здесь ни при чем. Примеры использования индексов (псевдокод)
Код
C++ (Qt)
CBase * obj = GetFirstTypedObject(TYPE_1);
while (obj) {
// do something with obj
obj = GetNextTypedObject(obj);
}
....
CBase * obj = GetNthTypedObject(TYPE_1);
if (obj != NULL) ..
...
InsertTypedObject(newObj, thePosition);
 
Записан
LisandreL
Птица говорун
*****
Offline Offline

Сообщений: 984


Надо улыбаться


Просмотр профиля
« Ответ #7 : Июнь 23, 2011, 16:08 »

QMap< type, QList< CBase* > >;

Код
C++ (Qt)
static QMap< type, QList< CBase* > > typedMap
 
QList< CBase* >* list = GetTypeList( typeID )
{
   if ( !typedMap.contains( typeID ) )
   {
        typedMap.insert( typeID, QList< CBase* >() );
   }
   return &typedMap.value( typeID );
}
 
CBase* GetFirstTypedObject( type typeID )
{
   QList< CBase* >* list = GetTypeList( typeID );
   return list.first();
}
 
CBase* GetNextTypedObject( CBase* obj )
{
   if ( obj == 0 )
   {
       return 0;
   }
   QList< CBase* >* list = GetTypeList( typeOf( obj ) );
   int index = list.indexOf( obj );
   if ( ( index == -1 ) || ( ( index+1 ) == list.length() ) )
   {
        return 0;
   }
   else
   {
       return list.at( index + 1 );
   }
}
ну и т.п.

Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #8 : Июнь 23, 2011, 16:27 »

LisandreL, спасибо за ответы, но давайте не торопиться - быстрое решение (из головы-справочника) не нужно - нужно надежное и хорошо продуманное
Код
C++ (Qt)
CBase* GetNextTypedObject( CBase* obj )
{
 ...
   int index = list.indexOf( obj );
 ...
}
Согласитесь что теперешняя реализация (которая, как я вижу, была изначально написана на Pascal а потом (абы-как) переведена на С) бьет Ваш "модерн" по всем статьям - ведь перескочить на следующий элемент списка - ну максимум 4-5 машинных команд, а у Вас indexOf может съесть много тысяч. Не торопитесь.
Записан
LisandreL
Птица говорун
*****
Offline Offline

Сообщений: 984


Надо улыбаться


Просмотр профиля
« Ответ #9 : Июнь 23, 2011, 19:48 »

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

Согласитесь что теперешняя реализация (которая, как я вижу, была изначально написана на Pascal а потом (абы-как) переведена на С) бьет Ваш "модерн" по всем статьям - ведь перескочить на следующий элемент списка - ну максимум 4-5 машинных команд, а у Вас indexOf может съесть много тысяч. Не торопитесь.
Зато GetNthTypedObject будет выполняться за O(1) (ну точнее O(log(type))*O(1)).
А в той реализации с указателями наверняка за O(n).
Next() и Prev() напротив выполняться за O(n) вместо O(1) в старой реализации. То есть в одном выигрываем, в другом проигрываем.
Вы же так и не сказали какие из функций более критичны по времени.

Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #10 : Июнь 23, 2011, 21:24 »

Знаете проект только вы и никто другой дать вам готовый ответ не сможет.
А я готового ответа и не прошу, интересуюсь как бы Вы решали

Next() и Prev() напротив выполняться за O(n) вместо O(1) в старой реализации. То есть в одном выигрываем, в другом проигрываем.
Вы же так и не сказали какие из функций более критичны по времени.
Ну а почему хоть какие-то вызовы должны выполняться "грубой силой"? Можно спорить что там лучше (типа QMap или QHash) но никак не решать линейным перебором. Так что "диалектика" здесь ни при чем.
Записан
LisandreL
Птица говорун
*****
Offline Offline

Сообщений: 984


Надо улыбаться


Просмотр профиля
« Ответ #11 : Июнь 23, 2011, 23:25 »

Ну а почему хоть какие-то вызовы должны выполняться "грубой силой"?
Потому что так всё устроенно. Нельзя все 3: последовательный доступ (prev-next), произвольный доступ (по индексу) и добавление/удаление сделать очень быстро (за O(1)). Ну и как четвёртый параметр можно взять простоту реализации.
Поэтому надо посмотреть на имеющуюся программу и оценить, что же приоритетно.
При этом надо учесть, что скажем цикл по всему множеству легко реализуется как через последовательный доступ, так и через индексный, поэтому такие циклы можно переписать на более  быстрый вариант в данной реализации.

Ну и в итоге:
1) если у нас важен индексный доступ: самое простое - List, Vector или банальный массив.
O(1)      O(n)      O(n)      элементарно в реализации
2) если важен последовательный доступ и удаление: двунаправленный список, как уже и реализованно.
O(n)      O(1)      O(1)      элементарно в реализации
3) если важен и последовательный и индексный доступ - комбинируем первый и второй вариант:
O(1)      O(1)      O(n)      чуть сложнее в реализации
4) если одинаково важна скорость по всем параметрам - список из 2 + дерево
O(log(n))   O(1)      O(log(n))   сложно в реализации
Деревьев много различных видов. Для гарантированной логорифмичности подойдут, скажем, RB- и AVL- деревья.
Записан
brankovic
Гость
« Ответ #12 : Июнь 24, 2011, 01:58 »

O(log(n))   O(1)      O(log(n))   сложно в реализации

я так понимаю boost::multi_index можно превратить в что-то такое, задав 2 ordered-индекса и один random access (этими не пользовался). Будет O(log(n)) на деревянные поиски/вставки/удаления, O(1) на индексный поиск и O(1) на итерацию.

Кстати, а почему нельзя все 3 сделать за O(1)? hash_map даёт на поиск (грубо говоря) O(1), на удаление O(1), при этом в нём есть последовательная итерация за O(1). Осталось прикрутить ортогональные хэши к группам типов, я не прав?
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #13 : Июнь 24, 2011, 10:14 »

Никогда не понимал всех этих "O" Улыбающийся Требования к скорости невысоки, логарифм прекрасно устраивает - не было бы перебора. Приоритеты надежность и удобство использования

Осталось прикрутить ортогональные хэши к группам типов, я не прав?
А кто такие "ортогональные хэши" ?
Наверное лучше прикидывать структуры напр в std::. Посмотрим простой вариант

Код
C++ (Qt)
typedef long TID;
std::map <TID, CBase *> theMapID;  // поиск объекта по ID
 
typedef std::vector <TID> TVecID;
TVecID theVecAllID;  // вектор всех объектов
 
std::map <type, TVecID *>  theMapTypeID;  // поиск по типу объекта
 
Так нет проблем с прямым доступом по индексу как ко всем объектам, так и конкретного типа. А вот получить индекс объекта - увы, перебором. Также теперешний код  содержит много сотен вызовов GetNextObject(obj) и, конечно, хотелось бы их не трогать - но так не получается и придется менять на итератор.

Изменения затеяны для развязки зависимостей между объектами. Пример
Код
C++ (Qt)
class MyObj {
 ...
 MyTarget * mTarget;
};
 
Это вызывает массу проблем с delete/undo и load/save. Задумка сделать так
Код
C++ (Qt)
MyTarget * GetDependentObject(ID(), DEPENDENCY_TYPE_1);
size_t NumDependentObjects(ID(), DEPENDENCY_TYPE_1);
 
ID объектов неуклонно растут. delete реально удаляет объект, но не вычеркивает его из theMapID, а просто устванавливает value() = NULL. Undo создает новый объект (со старым ID) и устанавливает value() на него. Ну это пока "так хочется"  Улыбающийся
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  


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