Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Хранение изменяющихся диапазонов целых чисел  (Прочитано 13186 раз)
0 Пользователей и 1 Гость смотрят эту тему.
baldr
Команда клуба

cy
Offline Offline
Пол: Мужской
Дорогие россияне


WWW
« : 13-08-2011 11:11 » 

Есть задача хранить непересекающиеся диапазоны целых чисел. Причем могут добавляться новые значения.
Простой пример:
* Есть существующий диапазон: [3, 8], [11, 15], [19, 20]
* Добавляется новый диапазон [5, 16] - он должен объединить два первых в один.

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

.NET Framework 3.0
Записан

Приличный компьютер всегда будет стоить дороже 1000 долларов, потому что 500 долларов - это не вполне прилично
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 13-08-2011 13:13 » 

HashSet<int>?
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 13-08-2011 13:56 » 

Цитата: baldr
SortedList не подходит по причине необходимости работы с предыдущими и последующими записями.
Вот этот пункт поподробнее. Что это значит? От некоего элемента получать доступ к предыдущему и следующему по порядку?
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
baldr
Команда клуба

cy
Offline Offline
Пол: Мужской
Дорогие россияне


WWW
« Ответ #3 : 13-08-2011 13:58 » 

HashSet<int>?

Нежелательно:

.NET Framework 3.0

По MSDN, HashSet<> появился в 3.5

Добавлено через 2 минуты и 17 секунд:
Вот этот пункт поподробнее. Что это значит? От некоего элемента получать доступ к предыдущему и следующему по порядку?
Да. Если реализовывать это самостоятельно, то встанет вопрос перебора элементов, их удаления или изменения внутри коллекции.
Если, конечно, ключом для SortedList<> делать начальную позицию диапазона.
« Последнее редактирование: 13-08-2011 14:00 от baldr » Записан

Приличный компьютер всегда будет стоить дороже 1000 долларов, потому что 500 долларов - это не вполне прилично
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 13-08-2011 17:05 » 

baldr, в БД есть такая вещь, как Nested Sets (вложенные множества). Это одна из возможных реализаций деревьев в реляционной базе. Я это рассказываю затем, что твоя задача имеет общие принципы с Nested Sets.
Каждый узел хранит границы начала и конца диапазона идентификаторов, входящих в множество. Причем начало - это его собственный идентификатор. Это можно описать так: struct set { int left; int right; /* ... */ };
Алгоритмы, используемые для работы с этими множествами могут тебе пригодиться.
Для ускорения используют left в качестве индекса. По этому тебе может подойти обычный Map.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #5 : 13-08-2011 19:51 » 

Я думаю, что ключевой проблемой здесь является решение следующей подзадачи.

Есть множество чисел, например, { 3, 11, 19 }. На вход подаётся число, например, 5. Нужно найти во множестве пару чисел, между которыми находится заданное (или пару одинаковых чисел, равных заданному, если заданное число присутствует во множестве) - в данном случае (3, 11).

С помощью чего такая задача решается оптимально?

На вскидку - это бинарный поиск (делением пополам) в упорядоченном множестве чисел. Реализуется он либо на массиве, либо на сбалансированном бинарном дереве.

И та, и другая структуры неоптимальны на вставку и удаление: массив нужно частично или полностью двигать, дерево - балансировать.

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #6 : 13-08-2011 20:21 » 

Есть взять структуру new(left, right), поиск пересечения с существующими диапазонами:
1. Пересечение левой частью: left <= new.left && right >= new.left
2. Пересечение правой частью: left >= new.left && left <= new.right
3. Вхождение в существующий диапазон: утверждение_1 && right >= new.right
4. Вхождение существующего диапазона: утверждение_2 && right <= new.right

Кстати, если числа целые положительные и их размер мал (например, умещаются в один байт), то, думаю, и битовые поля можно использовать. Это самое компактное и быстрое будет.

Дим, разве по дереву нельзя идти в обратном направлении?
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #7 : 14-08-2011 07:05 » 

Цитата: RXL
Дим, разве по дереву нельзя идти в обратном направлении?
Это просто так вопрос, или я что-то такое сказал, наводящее на эту мысль?

Во-первых, под "обратным" в дереве я понимаю "от листьев к корню". Во-вторых, конечно можно, если каждый дочерний узел хранит ссылку на родителя.


С помощью структуры "сбалансированное бинарное дерево" задача решается при помощи множества структур "Диапазон" и двух деревьев - одно для левых границ диапазона, другое - для правых. Каждый узел каждого дерева ссылается на соответствующий диапазон.

Тогда для [5, 16] нужно:
1) В дереве левых границ найти узел, ближайший и меньший 5 - это 3, и диапазон [3, 8].
2) В дереве правых границ найти узел, ближайший и больший 5 - это 8, и диапазон [3, 8].
3) Если найденные границы указывают на один и тот же диапазон, значит 5 попала в существующий диапазон - запомнить его как крайний левый. Если найденные границы указывают на разные диапазоны, значит 5 попала в "дыру" между существующими диапазонами - тогда от вершины, найденной в 1, нужно перейти к следующей в порядке обхода в глубину (либо это правый сын, либо, если его нет, родитель), и по этой вершине запомнить диапазон как крайний левый. Это [3, 8].

Аналогично с другого конца
4) В дереве левых границ найти узел, ближайший и меньший 16 - это 15.
5) В дереве правых границ найти узел, ближайший и больший 16 - это 20.
6) Если найденные границы указывают на один и тот же диапазон, значит 16 попало в существующий диапазон - запомнить его как крайний правый. Если найденные границы указывают на разные диапазоны, значит 16 попала в "дыру" между существующими диапазонами - тогда от вершины, найденной в 5, нужно перейти к предыдущей в порядке обхода в глубину (либо это левый сын, либо, если его нет, родитель), и по этой вершине запомнить диапазон как крайний правый. Это [11, 15].

7) По дереву левых (правых) вершин найти все диапазоны, у которых левая (правая) граница находится между левыми (правыми) границами найденных диапазонов (включительно). Это [3, 8], [11, 15]. Результатом может быть и пустое множество, если левая граница крайнего левого диапазона окажется больше левой границы крайнего правого диапазона. Тогда новый диапазон целиком умещается в "дыру". Может так быть, что нет крайнего левого или крайнего правого диапазонов - тогда вместо их левых (правых) границ взять, соответственно, наименьшее и наибольшее возможные значения границ для диапазонов.
8 ) Удалить все найденные диапазоны и их границы из деревьев.

9) Добавить новый диапазон [5, 16], добавить 5 в дерево левых границ, добавить 16 в дерево правых границ.
10) Сбалансировать деревья.
« Последнее редактирование: 14-08-2011 07:10 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #8 : 14-08-2011 07:15 » 

Диапазон значений ограничен, или допускаются любые целые?
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #9 : 14-08-2011 07:29 » 

Дим, извиняюсь - это я криво прочел. Вопрос отменяется.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
baldr
Команда клуба

cy
Offline Offline
Пол: Мужской
Дорогие россияне


WWW
« Ответ #10 : 16-08-2011 10:42 » 

Диапазон значений ограничен, или допускаются любые целые?
Если мы все еще говорим про мою задачу, то числа - это отрезки в файле. То есть это положительная ветка диапазона long. То есть числа довольно большие - это для RXL - к вопросу про 1 байт.

Все же изначально вопрос был такой - существуют ли в C# базовые возможности сделать это - какой-то готовый класс или паттерн.
За алгоритмы спасибо, но это был бы следующий шаг.
Записан

Приличный компьютер всегда будет стоить дороже 1000 долларов, потому что 500 долларов - это не вполне прилично
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #11 : 16-08-2011 11:18 » new

Описанные мною деревья скорее всего реализованы при помощи SortedDictionary. Поскольку у него декларируется логарифмическая сложность по поиску. У него же есть метод Where, позволяющий организовывать поиск (как часть LINQ).
« Последнее редактирование: 16-08-2011 11:27 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines