Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > выбор контейнера и не только

Автор: Paspartu 19.4.2009, 01:34

Доброго времени суток! Вот такой вопрос по эффективной реализации и вообще об STL: Имеем vector (пока вектор указателей на отрезки (есть POINT pt1, pt2 определяющие отрезки)), vector сортируется по наименьшему pt1.x каждого отрезка, тогда пусть есть вектор содержащий 10 таких отрезков Segment0(pt1, pt2)…. Segment9(pt1, pt2), пусть у всех отрезков длина равна 5(это в принципе пока не важно) а x увеличивается на 10 т.е.   Segment0.pt.x = 0, Segment1.pt.x = 10, Segment2.pt.x = 20…. Segment9.pt.x = 90 пока все OK, но допустим взяли Segment8.pt.x = 80 и сделали Segment8.pt.x = 15, тогда он должен при сортировке занять место между  Segment1.pt.x = 10 и Segment2.pt.x = 20 так оно и происходит но стал вопрос об эффективности т.к. при реализации уже известно что он будет между отрезком 1 и 2 есть ли алгоритмы STL которые позволяют это сделать? Будет ли более эффективно использовать контейнер list и делать что-то типа этого: изменять элемент удалять его из list а затем вставлять в нужной позиции? Или все же по прежнему использовать vector и при необходимости его тупо сортировать? Что эффективнее? Тогда получается если в отсортированном контейнере с 1 000 000 значений изменить одно и зная где оно должно находится все равно придется сортировать все значения? Ведь по сути надо известный диапазон значений заменить на одно (т.е.)  как в примере с отрезками: отрезки Segment0.pt.x = 0, Segment1.pt.x = 10 оставляем без изменения… отрезки Segment2.pt.x = 20… Segment7.pt.x = 70 как бы сдвигаем на один вправо (на место 8-го) Segment9pt.x = 90 оставляем без изменений, а в «свободное» место пихаем  Segment8.pt.x = 15, не ужели в STL нет такого? Ну или я по крайней мере не нашел… Для наглядности: Изначально:        Принудительно изменили 8-й отрезок:        После сортировки: Segment0.pt.x = 0            Segment0.pt.x = 0            Segment0.pt.x = 0 Segment1.pt.x = 10            Segment1.pt.x =10            Segment1.pt.x = 10 Segment2.pt.x = 20            Segment2.pt.x = 20            Segment8.pt.x = 15 Segment3.pt.x = 30            Segment3.pt.x = 30            Segment2.pt.x = 20 Segment4.pt.x = 40            Segment4.pt.x = 40            Segment3.pt.x = 30 Segment5.pt.x = 50            Segment5.pt.x = 50            Segment4.pt.x = 40 Segment6.pt.x = 60            Segment6.pt.x = 60            Segment5.pt.x = 50 Segment7.pt.x = 70            Segment7.pt.x = 70            Segment6.pt.x = 60 Segment8.pt.x = 80            Segment8.pt.x = 15    Segment7.pt.x = 70 Segment9.pt.x = 90            Segment9.pt.x = 90            Segment9.pt.x = 90 Просто возникает справедливый вопрос зачем сортировать отрезки 2-7 если они отсортированы? Или что если значений 1 000 000 ? И изменилось только одно (у меня ВСЕГДА изменяется только одно значение, но до изменения следующего контейнер должен быть отсортированным…) и возникает это довольно таки часто, поэтому стал вопрос об более эффективной реализации алгоритма нежели просто сортировать vector.  Будет ли эффективно копировать уже отсортированные значения во временный контейнер и затем их вставлять? Заменить на ассоциативный контейнер (set) и в качестве ключа использовать позицию начала (x, y) т.к. может быть что x – сы равны, но y – нет…? Это так… уже мысли вслух… возможно глупые….

Автор: maxim1000 19.4.2009, 09:06

если хочется что-то хранить в постоянно отсортированном виде, std::set вполне подходит впрочем, насколько я понял, интересует сортировка только по x, в данном случае можно использовать std::multiset, тогда можно не бояться наличия элементов с ключами, одинаковыми с точки зрения сравнения, и y тогда приплетать не надо (да и для уникальности его недостаточно) только не нужно изменять данные, хранящиеся в std::multiset, если это влияет на их порядок - лучше старые удалить, а новые вставить, иначе он их не пересортирует в случае с указателями тут, вроде, никаких страшных потерь производительности и не будет...

Автор: mes 19.4.2009, 13:19

Цитата(Paspartu @  19.4.2009,  00:34 ) Просто возникает справедливый вопрос зачем сортировать отрезки 2-7 если они отсортированы? Или что если значений 1 000 000 ? И изменилось только одно (у меня ВСЕГДА изменяется только одно значение, но до изменения следующего контейнер должен быть отсортированным…) и возникает это довольно таки часто, поэтому стал вопрос об более эффективной реализации алгоритма нежели просто сортировать vector.  если известно что вектор отсортирован, и не надо портить его сортированность,  то можно вытащить с вектора старый и вставить в нужное место новый элемент.  например нам надо изменить 15й элемент,  находим (std::find_if) что после изменения он будет 8м,  перемещаете (std::copy) с 8 по 14й на один элемент вперед, т.е затираете 15й и освобождаете место под 8й  и вставляете (std::vector::insert) на 8 место нужное.

Автор: Paspartu 19.4.2009, 13:45

To maxim1000 и mes... спасибо за свои соображения... только опять вопрос выбора... так что же лучше использовать set || veсtor?  Если поможет… Вообще сортировка проводиться по двум значениям по и X и Y, если представить, допустим что начало системы координат – левый верхний угол, то на первом месте должен быть отрезок с X -> 0 и Y->0 далее идет по возрастанию X и Y в несколько уровней по Y т.е. на последнем должен быть с наибольшим X и наибольшим Y т.е. правый нижний угол. И количество может быть разным может быть 2 а может и 100 поэтому хотелось бы одинаковой эффективности, по крайней мере соизмеримой… Вдогонку…  При изменении 8-го отрезка ообще необходимо запоминать соседей т.е. какие были (слева/справа) и какие будут… т.е. необходимо изначально проделать некоторые действия с отрезками 1-0 (именно в таком порядке сначала с 1 потом с 0), затем с 2-7 (отрезки должны раздвинуться если начало вставляемого отрезка попадает на конец 1-го, а 0 – й должен уступить место 1 – му если тот залезет на него и т.д. и в другую сторону аналогично для отрезков 2-7, также нужно перед сортировкой проделать некоторые действия с отрезками 7 – 0 и 9 и возможно далее… эти отрезки должны сдвинуться слева и справа на место 8 – го, т.е. надо знать какие соседи были… но если использовать vector то при удалении элемента итераторы будут съезжать, а искать заново тоже не хотелось бы…

Автор: mes 19.4.2009, 14:30

Цитата(Paspartu @  19.4.2009,  12:45 ) Вдогонку… Вы лучше чем части решения озвучивать, осветили бы первоначальную задачу. Мне например вобще непонятно для чего Вам нужен сортированный массив, и зачем будут меняться отрезки. А без понимания самой задачи предложить что нибудь трудно

Автор: Paspartu 19.4.2009, 16:36

Поясню… вот посмотрите на логику работы панелей инструментов в той же студии или в MS Office XP и так далее… Если панелей инструментов достаточно много то они упорядочены в своем докере от левого верхнего угла до правого нижнего, для простоты представим что имеем десять панелей расположенных на одном уровне (изменение Y не учитываем) пусть имеем ToolBar0, ToolBar1, … , ToolBar9, пусть у 8-й панели X = 500, резко тащим ее мышью влево X = 100, пусть она встанет между 0 и 1-й, тогда, если позволяет место 0 и 1 раздвинуться, а 7 и 8 сдвинуться (если они изначально были сдвинуты 8-й то бишь находились под ее «прессингом»)… Аналогично и в моем случае, правда объектов больше а изменяется значение в зависимости от некоторого условия, я не знаю как там это устроено и насколько это эффективно т.к. как правило панелей не так много и пользователь не так часто их двигает, но если «от балды» натыкать достаточно много панелей, а затем одну схватить и ей покружить так чтобы другие разъезжались и съезжались… то работает достаточно быстро. В моем случае все оналогично, правда объектами являются отрезки и их может быть и 100 и 200 и т.д.  В принципе пнели (ToolBar) можно представить как теже отрезки в высотой равной 1. С vector-ом все работает находим итератор _it текущего отрезка, находим соседей на новом месте находим соседей на старом месте  и двигаясь от нового и старого места ++_it || --_it гуляем и производим сдвиги, но в результате все рано в конечном итоге приходится сортировать… хотя изменил свое положение только один… вот и решил как то повысить эффективность…

Автор: mes 19.4.2009, 20:25

Цитата(Paspartu @  19.4.2009,  15:36 ) вот посмотрите на логику работы панелей инструментов в той же студии или в MS Office XP и так далее…  ну если на примере панелей, то общая логика примерно такая : ToolBar хранит указатели на панели в списке. Не список сортирован по координатам, а координаты представлены относительно положения панели в списке. При изменении координат/размеров панели, все видимые панели пересчитываются. Цитата(Paspartu @  19.4.2009,  15:36 ) В моем случае все оналогично, Ваше объяснение ясности не внесло.

Автор: Paspartu 20.4.2009, 00:35

Цитата(mes @  19.4.2009,  20:25 ) ToolBar хранит указатели на панели в списке. Не список сортирован по координатам, а координаты представлены относительно положения панели в списке. ... Так хорошо, но тогда как задается(определяется) положение ToolBar-а в списке? Можно подробнее? Пусть есть 3 ToolBar-а пусть они в списке идут изначально по порядку в зависимости от X, но что будет с порядком списка если одна перескочит другую? Несколько?  Если порядок списка не изменится, а изменяться лишь указатели prev/next? Тогда каким образом это происходит? Может мне поступить аналогично? P.S. Честно говоря изначально логика с отрезками строилась на поведении именно ToolBar-ов, еще до меня и почему то решили что они ToolBar-ы(указатели на них) хранятся в отсортированном vector-е. А я лишь пытаюсь сделать оптимизацию.

Автор: mes 20.4.2009, 00:54

Цитата(Paspartu @  19.4.2009,  23:35 ) Пусть есть 3 ToolBar-а пусть  Toolbar - эта общая панель, а "кнопкa" на ней - Tool. Цитата(Paspartu @  19.4.2009,  23:35 ) но что будет с порядком списка если одна перескочит другую? Несколько?   как это перескочат ? Если "кнопку" к примеру закрыли, или другим способом изменили ее относительное положение в списке, то Toolbar проходит по всем детям и корректирует их координаты. Если все дети фиксированной длины, то тогда и проходиться не надо, координата каждой "кнопки" получается переумножением коэфицента на ее порядковый номер. Цитата(Paspartu @  19.4.2009,  23:35 ) Может мне поступить аналогично? Цитата(mes @  19.4.2009,  13:30 ) без понимания самой задачи предложить что нибудь трудно smile Цитата(Paspartu @  19.4.2009,  23:35 ) изначально логика с отрезками строилась на поведении именно  может просто расскажите что представляет собой Ваш конторл и какая логика от него требуется, без упоминания текущей реализации, чтоб можно было понять что Вы трам делаете ?

Автор: Earnest 20.4.2009, 13:17

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

Автор: Paspartu 20.4.2009, 19:54

To mes & Earnest  спасибо, но задача связана с телеметрией и распознаванием сигналов предварительно оцифрованных как все работает в совокупности я только разбираюсь, если бы не начальство… а им приспичило вынь да положь… оптимизируй… Вот сижу и ковыряюсь в чужих исподниках…  И мне задачу поставили примерно как я вам, почти дословно… вот такая вот беда… Речь не идет о замени интерфейсов они этого не переживут, да и я тоже   , а речь идет только об оптимизации отдельного блока кода…   To mes, Вы не совсем верно меня поняли, возможно это моя ошибка под ToolBar-ми я имел ввиду панели инструментов кнопки на них значения не имеют… Откройте ту же студию 2005, возможно в 2003 они такие же… или Word (XP)  Spy++ -> свойства: Class: MsoCommandBar – вот именно они, посмотрите за их перемещением вот такая же логика мне нужна, без учета изменения размеров, повторюсь, отрезки можно представить как эти же CommandBar-ы (судя по названию класса окна)  с высотой равной 1. На данный момент все реализовано именно так, я Вам и писал про упорядоченный вектор (если это вектор в котором храняться указатели на CommandBar   ) по наименьшему X и Y до правого нижнего угла (наибольший X и Y) затем поиск соседей на новом месте и на старом + сдвиг…  По этому меня и заинтересовало: Цитата(mes @  19.4.2009,  20:25 ) ToolBar хранит указатели на панели в списке. Не список сортирован по координатам, а координаты представлены относительно положения панели в списке. При изменении координат/размеров панели, все видимые панели пересчитываются.

Автор: mes 20.4.2009, 23:00

Цитата(Paspartu @  20.4.2009,  18:54 ) To mes, Вы не совсем верно меня поняли, возможно это моя ошибка под ToolBar-ми я имел ввиду панели инструментов кнопки на них значения не имеют…  Большой разницы нет, за панельками управляет "фрейм-менеджер" (просто внутреннее устройство посложней, чем у просто Toolbar) и он точно также пересчитывает размеры и полжение остальных панелей при изменении одной. Цитата(Paspartu @  20.4.2009,  18:54 ) как все работает в совокупности я только разбираюсь, Вы хоть скриншот тогда покажите и участок кода -тот блок который надо оптимизировать. может тогда хоть понятно станет чем Вас загрузило начальство

Автор: Paspartu 22.4.2009, 20:51

Да я рад был бы, но участок довольно таки большой, вынести исходники - проблематично у нас с этим строго... да и у системников все закрыто, об этом позаботились.  Тогда, если Вас не затруднит, могли бы «на пальцах» изложить принцип работы, или хотя бы какой тип контейнера используется в данном случае, если это не вектор в котором храниться  указатели на панели, которые при изменение положения (одна панель при скачкообразном перетаскивании «препрыгнула» своих соседей), а затем вектор отсортировался бы согласно новых координат? Т.е. меня интересует вопрос, если это не упорядочный вектор (по наименьшим X & Y панелей) тогда что? Просто возможна другая реализация, мне бы хотя бы принцип… дальше я уже разовью…  Вот, нацарапал кое-что, может поможет понять суть работы…

Автор: Paspartu 22.4.2009, 20:55

Что то я с размером картинки погорячился

Автор: mes 22.4.2009, 23:27

А что получилось бы если бы в 5. пункте переносили бы не E, a C  (на 170)? B осталась бы под прессингом E ?

Автор: sdukshis 23.4.2009, 10:39

Если подобные операции приходится проводить часто, то использование vector действительно не разумно. Я бы предложил использовать set или list совместно с find_if Пример с set Код #include <iostream> #include <set> #include <algorithm> using namespace std; void print(int d){     cout << d << " "; } int main(){     int a[]={1,3,5,7,9,11};     const size_t n = sizeof(a)/sizeof(int);     set<int> S(a,a+n);     cout << "S = [";for_each(S.begin(),S.end(),print); cout << "]\n";     set<int>::iterator i = S.find(7);     S.erase(i);     cout << "S = [";for_each(S.begin(),S.end(),print); cout << "]\n";     S.insert(2);     cout << "S = [";for_each(S.begin(),S.end(),print); cout << "]\n";     return 0; } Пример с list и find_if Код #include <iostream> #include <list> #include <algorithm> using namespace std; void print(int d){     cout << d << " "; } int main(){     int a[]={1,3,5,7,9,11};     const size_t n = sizeof(a)/sizeof(int);     list<int> L(a,a+n);     // меняем 7 на 2         cout << "L = ["; for_each(L.begin(),L.end(),print); cout << "]\n";     // Находим и удаляем 7     list<int>::iterator i = find(L.begin(),L.end(),7);     L.erase(i);     cout << "L = ["; for_each(L.begin(),L.end(),print); cout << "]\n";     // Находим место для 2 и вставляем её     i=find_if(L.begin(),L.end(),bind2nd(greater<int>(),2));     L.insert(i,2);     cout << "L = ["; for_each(L.begin(),L.end(),print); cout << "]\n";     return 0; }

Автор: Paspartu 23.4.2009, 23:33

To mes. Извините, что отвечаю с такими задержками на работе Интернета нет только локалка без выхода в мир… Да, совершенно верно, в данном случае, если в 5 пункте сдвинуть С на позицию X = 170, то отрезок С стал бы «чисто» ничего раздвигать и сдвигать не надо, после перемещения происходит только сортировка. Причем у отрезка сбросился бы сохраненный отрезок под чьим прессингом он находился для данного случая сбросилось бы упоминание об отрезке E. Т.е. тот отрезок который переносится считается основным, а все остальные работают под него (если происходит сдвиг). А вот если бы после того как подвинули С на 170, придет событие что надо отрезок E установить в позицию 75 то естественно отрезок B сдвинется на освободившееся место Bx = 45… Ex = 80 -> Bx = 50… Ex = 85-> Bx = 50… т.е. отрезок B будет двигаться вслед переносимому отрезку E, пока не будет полностью погашено его смещение вызванное именно этим отрезком (E), после чего вся информация об смещении у отрезка B сбрасывается. Но здесь все просто, когда нет перескоков, то сортировка не нужна, а вот с перескоками дела обстоят сложнее. To sdukshis. Спасибо за отзыв, постараюсь разобраться с предложенным вариантом. Склоняюсь в сторону std::list, а дальше видно будет…

Автор: mes 27.4.2009, 09:40

Цитата(Paspartu @  23.4.2009,  22:33 ) Но здесь все просто, когда нет перескоков, то сортировка не нужна, а вот с перескоками дела обстоят сложнее. Сортировка никогда не нужна, если есть перескок, то и в контейнере делайте перескок элемента. В общем виде Вам нужно изготовить свой контейнер, который будет являться надстойкой над обычным и осущесвлять всю логику, которую Вы описали. Сами элементы лишь хранят необходимую для этого информацию, в частности значение координат отображания,  и реальных, относительно которых произошел сдвиг под прессингом.

Автор: Paspartu 28.4.2009, 18:25

Огромное спасибо mes и sdukshis! Вопрос закрыт!

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)