Oberon space
General Category => Общий раздел => Тема начата: Губанов Сергей Юрьевич от Октябрь 23, 2012, 01:47:07 pm
-
На целочисленной (типа UInt64) прямой задан список отрезков {{начало1, конец1}, {начало2, конец2}, {начало3, конец3},...}. Отрезки могут соприкасаться, пересекаться и даже целиком поглощаться друг другом. Надо написать программу, которая быстро-быстро смёржит все пересечения/соприкосновения/поглощения и выдаст нормальный список отрезков (без пересечений/соприкосновений/поглощений).
Вопрос: как сделать это эффективно?
P. S.
Это списки диапазонов телефонных номеров. Всего номеров будет что-то около миллиона, списки конечно покороче. Не знаю точно, может быть 100 отрезков в списке, а может быть и 1000.
-
На самом деле не требуется выдавать ответ именно в виде списка.
В ответе должна быть некая "нормальная" структура данных, не обязательно список отрезков.
Эта структура данных должна способствовать быстрому ответу на вопросы:
1) равна ли она другой такой же структуре данных или не равна;
2) попадает ли некий номер в какой либо из диапазонов или нет.
-
Буквально на днях писал подобное:
// СписокПериодов: ТаблицаЗначений [Начало, Конец]
//
Функция СвернутьСписокПериодов(СписокПериодов)
Если СписокПериодов.Количество() > 1 Тогда
Набор = Новый Массив;
СписокПериодов.Сортировать("Начало");
ТекПериод = СписокПериодов[0];
Набор.Добавить(ТекПериод);
Для Каждого Период Из СписокПериодов Цикл
Если Период.Начало > ТекПериод.Конец Тогда
ТекПериод = Период;
Набор.Добавить(ТекПериод);
ИначеЕсли Период.Конец > ТекПериод.Конец Тогда
ТекПериод.Конец = Период.Конец;
КонецЕсли;
КонецЦикла;
ВОЗВРАТ СписокПериодов.Скопировать(Набор);
КонецЕсли;
ВОЗВРАТ СписокПериодов;
КонецФункции
-
а что значит смержит? например..
{4,8} ,{1,12}, {3,6}, {4,8}- что она должна сделать?
-
{1, 12}
-
Если я правильно пониманию, то это разновидность задачи о покрытиях:
http://oberspace.dyndns.org/index.php/topic,307.0.html
-
На целочисленной (типа UInt64) прямой задан список отрезков {{начало1, конец1}, {начало2, конец2}, {начало3, конец3},...}. Отрезки могут соприкасаться, пересекаться и даже целиком поглощаться друг другом. Надо написать программу, которая быстро-быстро смёржит все пересечения/соприкосновения/поглощения и выдаст нормальный список отрезков (без пересечений/соприкосновений/поглощений).
Вопрос: как сделать это эффективно?
P. S.
Это списки диапазонов телефонных номеров. Всего номеров будет что-то около миллиона, списки конечно покороче. Не знаю точно, может быть 100 отрезков в списке, а может быть и 1000.
Заполняй на прямой все точки из которых состоят отрезки. Потом можно пройтись по прямой и найти непрерывные куски.
Вот если бы отрезки состояли не из точек, а были бы непрерывными, тогда было бы хуже.
-
не нужно искать, для этого достаточно обратиться с к элементу массива с индексом равным номеру... если конечно нежирно иметь массив из 10^10 значений
-
Ежели без сортировки, то вариант Peter Almazov самый ходовой.
albobin тут:
http://oberspace.dyndns.org/index.php/topic,307.0.html
так и делал
-
Но такому способу нужно много памяти, раз там UInt64
add: DIzer уже упомянул этот момент
-
Но такому способу нужно много памяти, раз там UInt64
add: DIzer уже упомянул этот момент
НЕТ. там uint64 это всего лишь НОМЕР элемента массива , сам элемент может быть всего лишь однобитным(истина, ложь...0,1)
-
А... ну да... это ж додиез :)
ps У меня в 1с нет такой возможности, потому не мыслю этими категориями ;D
-
один хрен массив большой- больше сотни мегабайт, да и заполнять его "в тупую" очень,ОЧЕНЬ накладно... тут надо смотреть более детально на задачу... например разбивать номер на первую тройку (код оператора) и все остальное...
-
... так что , Ilovb, не спешите выкидывать вариант с сортировками на помойку.. ;)
-
Заполняй на прямой все точки из которых состоят отрезки.
Номер может быть из 18 десятичных цифр. 10^18 точек.
-
блин, Сергей, для ответа на вопросы которые вы ставите достаточно нескольких сравнений к максимум всем элементам списка... если число элементов < 1000 может не стоит мозги компостировать сложными вариантами
-
разве что отсортировать предварительно этот список по нижней границе...
-
если число элементов < 1000 может не стоит мозги компостировать сложными вариантами
Ещё может быть 300 доменов/локаций. То есть триста раз по тысяче. А времени на это не должно тратится вообще ни сколько. Ну там 10 миллисекунд максимум.
Вобщем, мы тут сейчас уже сочинили алгоритм на сто строк для сборки нужной структуры. После сборки структура уже не изменяется. То есть отдельно билдер, отдельно структура. Билдер правда мусорит (основан на двухсвязных списках), но мы его потом доусовершенствуем, если захотим.
Билдер хранит в себе двухсвязный список точек (а не список диапазонов). Каждая точка может быть начальной, конечной или одиночной. Использование в билдере списка точек вместо списка диапазонов сильно поуменьшило комбинаторику. Результатом работы билдера является отсортированный список диапазонов.
-
ИМХО нет смысла заниматься задачей.. если нет нормальной ее постановки..
-
формально в 10 мили секунд можно уложиться простым поиском по списку... но если скажем выяснится что требуется искать 100 раз в секунду..то это точно не прокатит..
-
К сведению: номера телефонные отлично сортируются поразрядной сортировкой. Сложность соответственно O(n).
-
Билдер хранит в себе двухсвязный список точек (а не список диапазонов). Каждая точка может быть начальной, конечной или одиночной. Использование в билдере списка точек вместо списка диапазонов сильно поуменьшило комбинаторику. Результатом работы билдера является отсортированный список диапазонов.
Не очень понял. Вы заменили изначальную структуру (список диапазонов) или этот список точек генерится по запросу?
А профит я так понимаю в том, что список упорядочен, т.е. сделали быстрый поиск?
ps И еще интересно чем мой вариант не подходит? Там ведь один проход по списку... (Если изначальный список не меняется все время конечно.)
-
Если нужен быстрый поиск, то мой код тоже возвращает упорядоченный список непересекающихся диапазонов... И сравнить два таких списка элементарно.
-
Не очень понял. Вы заменили изначальную структуру (список диапазонов) или этот список точек генерится по запросу?
Я сделал так, что изначального плохого списка вообще нет. Список сразу хороший по построению.
Билдер билдер = НовыйБилдер();
// получаем данные из БД и засовываем их в билдер:
билдер.Добавить(123, 456);
билдер.Добавить(987, 10000);
// А теперь билдим сразу правильный список:
Список список = билдер.Собрать();
Внутри билдера упорядоченный двухсвязный список точек. Уж больно легко их мёржить. Надо найти начальную head и конечную tail точку, затем все что между ними сколлапсировать вот так:
head.next = tail;
tail.prev = head;
Уже забилженный "Список" - неизменный, там внутри массив. По массиву можно делать бинарный поиск.
-
Понятно.
А есть возможность ваш код тут запостить? Хотя бы в урезанном виде.
ps Кстати псевдокод можно было и на ангельском. Я полиглот и не совсем кошерный одинэснег ;) ;D
-
Любопытно - это часть какой задачи ? Биллинг мг/мн ?
-
Нет, мг./мн - как-то сомнительно, наверное, всё же это нечто с базой абонентских номеров?
-
А есть возможность ваш код тут запостить? Хотя бы в урезанном виде.
Конечно, только я его ещё разок обмозгую, потом запощу сюда.
Кстати, в твоём алгоритме смежные диапазоны вроде не мёржатся? Те что отличаются на единицу?
У меня мёрж {{10, 20}, {21, 30}} даёт {{10, 30}}.
-
У меня мёрж {{10, 20}, {21, 30}} даёт {{10, 30}}.
А я в подобных задачах использую интервалы такого рода [x0,x1[ ( т.е x1 не входит) Удобнее получается.
-
Любопытно - это часть какой задачи ? Биллинг мг/мн ?
Раздача телефонных номеров.
Владелец множества телефонных номеров (оператор связи) может продать их подмножество другому владельцу (более мелкому оператору связи), а тот может продать подмножество подмножества номеров третьему владельцу и т.д.
Или раздача может делатся в рамках одного владельца, но по географическому/административному признаку. Область - район - посёлок, область - город - район и т.п. из этой оперы.
-
Короче, алгоритм добавления диапазона (begin, end) в двухсвязный список точек у меня такой:
Сначала ищем или создаём головную точку
Point head = null;
Point x = this.first;
while (begin > x.value)
{
x = x.next;
}
if (x.prev.type == PointType.Begin)
{
Попали в уже существующий диапазон, возвращаем его голову
head = x.prev;
}
else if ((x.prev.type == PointType.End) && ((x.prev.value == begin -1) || (x.prev.value == begin)))
{
Попали точно в конец существующего диапазона или в смежную с ним точку
head = x.prev.prev;
}
else if ((x.prev.type == PointType.Single) && ((x.prev.value == begin -1) || (x.prev.value == begin)))
{
Попали точно в существующую точку или в смежную с ней
head = x.prev;
}
else
{
Никуда не попали, создаём новую точку
head = new Point(begin);
head.next = x;
head.prev = x.prev;
head.next.prev = head;
head.prev.next = head;
}
Теперь ищем или создаём хвостовую точку
Point tail = null;
while (end > x.value)
{
x = x.next;
}
if (x.type == PointType.End)
{
Попали в уже существующий диапазон, возвращаем его хвост
tail = x;
}
else if ((x.type == PointType.Begin) && ((x.value == end + 1) || (x.value == end)))
{
Попали в самое начало существующего диапазона или непосредственно перед ним, возвращаем его хвост
tail = x.next;
}
else if ((x.type == PointType.Single) && ((x.value == end + 1) || (x.value == end)))
{
Попали в существующую одиночную точку или непосредственно перед ней
tail = x;
}
else
{
Никуда не попали, создаём новую точку
tail = new Point(end);
tail.prev = x.prev;
tail.next = x;
tail.next.prev = tail;
tail.prev.next = tail;
}
Коллапсируем всё что оказалось между головой и хвостом
if (head.value == tail.value)
{
Добавление одиночной точки, отбрасываем хвост
head.next = tail.next;
head.next.prev = head;
head.type = PointType.Single;
}
else
{
head.next = tail;
head.type = PointType.Begin;
tail.prev = head;
tail.type = PointType.End;
}
Точки бывают трёх сортов: Begin, End, Single. Для упрощения алгоритма в список помещены фэйковые граничные точки со значениями -2 и long.MaxValue. Да, тип номера сменил с UInt64 на Int64. Номерам разрешается быть >= 0 и < long.MaxValue - 1. Именно -2, а не -1 потому что -1 смежный с 0. Аналогично long.MaxValue-1.
После того как список точек построен по нему генерируется массив структур диапазонов. Но его менять уже нельзя. Далее используется только он. В частности, номера на массиве диапазонов ищутся бинарным поиском.
-
А есть возможность ваш код тут запостить? Хотя бы в урезанном виде.
Конечно, только я его ещё разок обмозгую, потом запощу сюда.
Кстати, в твоём алгоритме смежные диапазоны вроде не мёржатся? Те что отличаются на единицу?
У меня мёрж {{10, 20}, {21, 30}} даёт {{10, 30}}.
Не мёржатся. У меня там просто диапазоны дат по принципу [начало, конец)
Т.е. последний день периода исключается.
Там логика такая. Закрывается один период например на 10.10.2012 и открывается новый с этого же дня.
абстрактный пример:
01.09.2012 - 10.10.2012 -- старый тариф (тут 9 дней)
10.10.2012 - 01.01.2013 -- новый тариф
А у тебя так [начало, конец]