Russian Qt Forum
Март 29, 2024, 09:44
Добро пожаловать,
Гость
. Пожалуйста,
войдите
или
зарегистрируйтесь
.
Вам не пришло
письмо с кодом активации?
1 час
1 день
1 неделя
1 месяц
Навсегда
Войти
Начало
Форум
WIKI (Вики)
FAQ
Помощь
Поиск
Войти
Регистрация
Russian Qt Forum
>
Forum
>
Программирование
>
Общий
>
Объединение диапазонов/отрезков
Страниц: [
1
]
Вниз
« предыдущая тема
следующая тема »
Печать
Автор
Тема: Объединение диапазонов/отрезков (Прочитано 7163 раз)
Igors
Джедай : наставник для всех
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
Сообщений: 1175
Re: Объединение диапазонов/отрезков
«
Ответ #1 :
Февраль 02, 2018, 20:46 »
https://stackoverflow.com/questions/4748184/how-to-efficiently-merge-int-ranges-in-a-stream
не ?
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Объединение диапазонов/отрезков
«
Ответ #2 :
Февраль 03, 2018, 10:20 »
Не, но тут есть название "interval tree". Выходим на boost::interval_map, вроде "оно", но, как всегда, задрочено
Ладно, обойдусь великом, может в след раз. Спасибо за наводку
Записан
sergek
Гипер активный житель
Offline
Сообщений: 861
Мы должны приносить пользу людям.
Re: Объединение диапазонов/отрезков
«
Ответ #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
Сообщений: 11445
Re: Объединение диапазонов/отрезков
«
Ответ #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
Сообщений: 2679
Я работал с дискетам 5.25 :(
Re: Объединение диапазонов/отрезков
«
Ответ #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
Сообщений: 600
Re: Объединение диапазонов/отрезков
«
Ответ #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
Сообщений: 11445
Re: Объединение диапазонов/отрезков
«
Ответ #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
Сообщений: 600
Re: Объединение диапазонов/отрезков
«
Ответ #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
Сообщений: 11445
Re: Объединение диапазонов/отрезков
«
Ответ #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
Сообщений: 600
Re: Объединение диапазонов/отрезков
«
Ответ #10 :
Февраль 19, 2018, 09:59 »
Можно без дополнительного диапазона. Хранить 2 числа(текущее и предыдущее значение) и бит четности(для каждого диапазона, чтобы знать начало это или конец) из первого диапазона и из второго. Увеличивать итератор для диапазона с меньшим числом. Смысл тот же, просто копирования в отдельный диапазон нет.
Записан
Страниц: [
1
]
Вверх
Печать
« предыдущая тема
следующая тема »
Перейти в:
Пожалуйста, выберите назначение:
-----------------------------
Qt
-----------------------------
=> Вопросы новичков
=> Уроки и статьи
=> Установка, сборка, отладка, тестирование
=> Общие вопросы
=> Пользовательский интерфейс (GUI)
=> Qt Quick
=> Model-View (MV)
=> Базы данных
=> Работа с сетью
=> Многопоточное программирование, процессы
=> Мультимедиа
=> 2D и 3D графика
=> OpenGL
=> Печать
=> Интернационализация, локализация
=> QSS
=> XML
=> Qt Script, QtWebKit
=> ActiveX
=> Qt Embedded
=> Дополнительные компоненты
=> Кладовая готовых решений
=> Вклад сообщества в Qt
=> Qt-инструментарий
-----------------------------
Программирование
-----------------------------
=> Общий
=> С/C++
=> Python
=> Алгоритмы
=> Базы данных
=> Разработка игр
-----------------------------
Компиляторы и платформы
-----------------------------
=> Linux
=> Windows
=> Mac OS X
=> Компиляторы
===> Visual C++
-----------------------------
Разное
-----------------------------
=> Новости
===> Новости Qt сообщества
===> Новости IT сферы
=> Говорилка
=> Юмор
=> Объявления
Загружается...