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

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

Russian Qt Forum > Forum > Программирование > Общий > Объединение диапазонов/отрезков
Страниц: [1]   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Объединение диапазонов/отрезков  (Прочитано 7821 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Февраль 01, 2018, 07:06 »
Добрый день

Есть QVector<int> хранящий "отрезки" или "диапазоны", напр номера страниц. Пример

{ 1, 10, 15, 20 };  // страницы с 1 по 10 включительно и с 15 по 20

Вектор всегда сортирован и имеет четное числр эл-тов. Требуется пополнять этот вектор новыми отрезками, при этом сливая их если необходимо. Примеры

{ 1, 10, 15, 20 } + { 25, 30 } = { 1, 10, 15, 20, 25. 30 } 
{ 1, 10, 15, 20 } + { 21, 30 } = { 1, 10, 15, 30 } 

Может в std есть что-нибудь "эдакое"? Или это и так легко написать (тогда покажите как, у меня получается как-то не очень легко)

Спасибо
Записан
qate
Супер
******
Offline Offline

Сообщений: 1177


Просмотр профиля
« Ответ #1 : Февраль 02, 2018, 20:46 »
https://stackoverflow.com/questions/4748184/how-to-efficiently-merge-int-ranges-in-a-stream
не ?
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #2 : Февраль 03, 2018, 10:20 »
Не, но тут есть название "interval tree". Выходим на boost::interval_map, вроде "оно", но, как всегда, задрочено  Плачущий
Ладно, обойдусь великом, может в след раз. Спасибо за наводку
Записан
sergek
Гипер активный житель
*****
Offline Offline

Сообщений: 872


Мы должны приносить пользу людям.


Просмотр профиля
« Ответ #3 : Февраль 03, 2018, 23:42 »
Мне кажется, если вектора разделить на отдельные отрезки ({ 1, 10, 15, 20 } -> { 1, 10}, {15, 20 }), отсортировать, то задача будет решаться значительно легче. Если уже не решена. А потом все слить в кучу.
Записан
Qt 5.13.0 Qt Creator 5.0.1
Win10, Ubuntu 20.04
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #4 : Февраль 04, 2018, 14:58 »
Цитата: sergek от Февраль 03, 2018,  23:42
Мне кажется, если вектора разделить на отдельные отрезки ({ 1, 10, 15, 20 } -> { 1, 10}, {15, 20 }), отсортировать, то задача будет решаться значительно легче.
Не уловил идею, за счет чего легче? По-моему все равно возня с lower_bound  (контейнер всегда сортирован)

Цитата: sergek от Февраль 03, 2018,  23:42
Если уже не решена.
Конечно решена, но это час-другой довольно кропотливой работы, да и нет уверенности что где-то не насвистел. Поэтому "попастись" конечно хотелось бы.   
Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


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


Просмотр профиля
« Ответ #5 : Февраль 08, 2018, 12:46 »
Ну есть примитивное решение, основанное на двоичной карте (собственно принцип z-буфера).
Все диапазоны разворачиваются в 1-мерное двоичное пространство (от 0 до max), каждое имеющееся значение помечается как 1, иначе 0. Затем повторяем для другого вектора и т.д. В конце делаем обратную операцию - все подряд установленные биты конвертируем в диапазоны.
Будет работать, естественно, только для целых чисел и когда max заранее известен.
Записан
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 не волк, в лес не уйдёт
deMax
Хакер
*****
Offline Offline

Сообщений: 600



Просмотр профиля
« Ответ #6 : Февраль 09, 2018, 15:34 »
Закидываем в отсортированный список первый диапазон, который хранит время и бит(1=начало или 0=конец диапазона). Потом в этот список добавляем аналогично второй диапазон(список уже отсортирован).
А потом из списка считываем в ответ,
Код:
int deep = 0;
for(const auto &item: items) {
  if(item.bit) { // начало диапазона
    if(deep++) anser << item.time; } // тут лучше уйти от постинкримента(if(deep)...;++deep;), просто так нагляднее
  else // конец диапазона
    if(--deep) answer << item.time; }
}
а потом пройтись по списку и удалить пары одинаковых чисел. (в цикле наверное сложнее будет)
« Последнее редактирование: Февраль 09, 2018, 15:46 от deMax » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #7 : Февраль 10, 2018, 07:33 »
Цитата: Racheengel от Февраль 08, 2018,  12:46
Ну есть примитивное решение, основанное на двоичной карте (собственно принцип z-буфера).
Все диапазоны разворачиваются в ...
Ну все-таки примитивизм имеет какие-то (разумные) границы  Улыбающийся

Цитата: deMax от Февраль 09, 2018,  15:34
Закидываем в отсортированный список первый диапазон, который хранит время и бит(1=начало или 0=конец диапазона). Потом в этот список добавляем аналогично второй диапазон(список уже отсортирован).
А потом из списка считываем в ответ,
Код:
int deep = 0;
for(const auto &item: items) {
  if(item.bit) { // начало диапазона
    if(deep++) anser << item.time; } // тут лучше уйти от постинкримента(if(deep)...;++deep;), просто так нагляднее
  else // конец диапазона
    if(--deep) answer << item.time; }
}
а потом пройтись по списку и удалить пары одинаковых чисел. (в цикле наверное сложнее будет)
Совершенно не понял этот набросок. Как это будет работать для примеров стартового поста?
Записан
deMax
Хакер
*****
Offline Offline

Сообщений: 600



Просмотр профиля
« Ответ #8 : Февраль 12, 2018, 08:46 »
Igors
первый диапазон 1-6, второй 3-4, 5-7. слили в один список сохранив флаги (o-open, c-close) 1o 3o 4c 5o 6c 7c. глубина вначале - (0) открывая диапазон глубина увеличивается и наоборот, тогда (0) 1o (1) 3o (2) 4c (1) 5o (2) 6c (1) 7c (0) в диапазон попадают только переходы 0->1 и 1->0. итого 1 7
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #9 : Февраль 13, 2018, 15:07 »
Цитата: deMax от Февраль 12, 2018,  08:46
первый диапазон 1-6, второй 3-4, 5-7. слили в один список сохранив флаги (o-open, c-close) 1o 3o 4c 5o 6c 7c. глубина вначале - (0) открывая диапазон глубина увеличивается и наоборот, тогда (0) 1o (1) 3o (2) 4c (1) 5o (2) 6c (1) 7c (0) в диапазон попадают только переходы 0->1 и 1->0. итого 1 7
Теперь понял, спасибо. Вполне рабочий вариант, но может оказаться громоздким/неуклюжим т.к. надо сливать контейнеры а потом удалять. Для "массового" слияния это оправдано, но если добавляется 1-2 (как в стартовом посте) то нет.
Записан
deMax
Хакер
*****
Offline Offline

Сообщений: 600



Просмотр профиля
« Ответ #10 : Февраль 19, 2018, 09:59 »
Можно без дополнительного диапазона. Хранить 2 числа(текущее и предыдущее значение) и бит четности(для каждого диапазона, чтобы знать начало это или конец) из первого диапазона и из второго. Увеличивать итератор для диапазона с меньшим числом. Смысл тот же, просто копирования в отдельный диапазон нет.
Записан
Страниц: [1]   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


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