Название: Объединить флажки Отправлено: Igors от Июль 14, 2012, 18:34 Добрый день
Должно быть просто но что-то не выплясывается. Есть такая структура Код Если бы было всего 2 экземпляра CData, то нужное объединение достигается так Код А как сделать для контейнера содержащего N элементов CData? (N может быть приличным) Спасибо Edit: виноват, забыл упомянуть важную деталь. Если один указатель mFlag присваивается другому, то это должно выполняться для всех элементов с таким mFlag. Другими словами - элементы контейнера с одинаковым mFlag принадлежат одной группе/множеству. Множества могут быть объединены если позволяет маска mFlag. Нужно выполнить объединение всех множеств которые имеют хотя бы 1 общий mFace. Название: Re: Объединить флажки Отправлено: DmitryM от Июль 14, 2012, 20:05 За O(n) при помощи std::for_each устроит?
Название: Re: Объединить флажки Отправлено: alexis031182 от Июль 15, 2012, 17:54 За O(n) при помощи std::for_each устроит? А как это будет выглядеть? Я так понял, что в задаче необходимо сравнение каждого флага каждой структуры с соответствующими флагами других структур. Тут по моему без разбиения основного условия на подусловия не обойтись.Название: Re: Объединить флажки Отправлено: Igors от Июль 15, 2012, 18:04 Тут по моему без разбиения основного условия на подусловия не обойтись. Я и разбил, но получается как-то длинно, и совсем не элегантно. Впрочем знатоки std показывают (или не показывают) обычный результат :) Название: Re: Объединить флажки Отправлено: alexis031182 от Июль 15, 2012, 19:18 Может быть такое имелось в виду. Псевдокод:
Код То есть по отдельному foreach на каждое подусловие. Название: Re: Объединить флажки Отправлено: trot от Июль 15, 2012, 19:33 Может быть я ошибаюсь, но я предлагаю следующее
1) с начало объединить абсолютно одинаковые структуры; 2) создать в каждой структуре одного множества вместо указателя mFlag, какую-то переменную, которая была одна для всех элементов этого множества; 3) выполнить объединение по условию (d0.mFace == d1.mFace && d0.mFlag && d1.mFlag && (*d0.mFlag & *d1.mFlag) == 0), при этом новое множество должно иметь одну разделяемую переменную вместо предыдущих двух для каждого множества. Может в этом направлении подумать. Название: Re: Объединить флажки Отправлено: Igors от Июль 15, 2012, 19:55 Может быть такое имелось в виду. Псевдокод: Мудрено и непонятно :)Код То есть по отдельному foreach на каждое подусловие. Может быть я ошибаюсь, но я предлагаю следующее Ну "объединить абсолютно одинаковые" наверное имеется ввиду "создать новую структуру которая будет представлять все одинаковые элементы исходного массива". Я так и сделал1) с начало объединить абсолютно одинаковые структуры; 2) создать в каждой структуре одного множества вместо указателя mFlag, какую-то переменную, которая была одна для всех элементов этого множества; 3) выполнить объединение по условию (d0.mFace == d1.mFace && d0.mFlag && d1.mFlag && (*d0.mFlag & *d1.mFlag) == 0), при этом новое множество должно иметь одну разделяемую переменную вместо предыдущих двух для каждого множества. Может в этом направлении подумать. Код Сортирую массив - первый ключ mFace, второй ключ mFlag. Создаю контейнер CJoinFrag, в каждом диапазоне элементы исходного массива с обоими равными mFace и mFlag. Однако на этом дело не кончается - элементы с одним mFlag могут иметь разный mFace. Приходится связать в списки CJoinFrag с одинаковыми mFlag (еще один временный контейнер + сортировка). В общем - работает, но длинновато, я недоволен :'( Название: Re: Объединить флажки Отправлено: DmitryM от Июль 15, 2012, 20:09 А как это будет выглядеть? Я так понял, что в задаче необходимо сравнение каждого флага каждой структуры с соответствующими флагами других структур. Тут по моему без разбиения основного условия на подусловия не обойтись. Когда писал пост, то не было поправки.Код Если правильно понял поправки, то Код Но тут уже O(n*log(n)) Название: Re: Объединить флажки Отправлено: Igors от Июль 16, 2012, 11:18 Последний вариант не может обсуждаться т.к. не видно кто такой first.
Код
Но тут уже O(n*log(n)) Если ничего не делилось пополам откуда же логарифм? То наверно "для наукообразности" :)Название: Re: Объединить флажки Отправлено: DmitryM от Июль 19, 2012, 12:50 Но тут уже O(n*log(n)) Если ничего не делилось пополам откуда же логарифм? То наверно "для наукообразности" :)Во втором случае идея такая: при помощи сортировки группируем элементы так, что бы те которые можно объединить шли друг за другом, а потом идти слева на право, выделяя интервалы в котором можно вызвать объединение и объединяем. |