Смёржить отрезки

[DIzer]

блин, Сергей, для ответа на вопросы которые вы ставите достаточно нескольких сравнений к максимум всем элементам списка... если число элементов < 1000 может не стоит мозги компостировать сложными вариантами

[DIzer]

разве что отсортировать предварительно этот список по нижней границе...

[Губанов Сергей Юрьевич]

если число элементов < 1000 может не стоит мозги компостировать сложными вариантами

Ещё может быть 300 доменов/локаций. То есть триста раз по тысяче. А времени на это не должно тратится вообще ни сколько. Ну там 10 миллисекунд максимум.

Вобщем, мы тут сейчас уже сочинили алгоритм на сто строк для сборки нужной структуры. После сборки структура уже не изменяется. То есть отдельно билдер, отдельно структура. Билдер правда мусорит (основан на двухсвязных списках), но мы его потом доусовершенствуем, если захотим.

Билдер хранит в себе двухсвязный список точек (а не список диапазонов). Каждая точка может быть начальной, конечной или одиночной. Использование в билдере списка точек вместо списка диапазонов сильно поуменьшило комбинаторику. Результатом работы билдера является отсортированный список диапазонов.

[DIzer]

 ИМХО нет смысла заниматься  задачей.. если нет нормальной ее постановки..

[DIzer]

формально в 10 мили секунд можно уложиться простым поиском по списку... но  если скажем выяснится что требуется искать 100 раз в секунду..то это точно не прокатит..

[valexey_u]

К сведению: номера телефонные отлично сортируются поразрядной сортировкой. Сложность соответственно O(n).

[ilovb]

Билдер хранит в себе двухсвязный список точек (а не список диапазонов). Каждая точка может быть начальной, конечной или одиночной. Использование в билдере списка точек вместо списка диапазонов сильно поуменьшило комбинаторику. Результатом работы билдера является отсортированный список диапазонов.

Не очень понял. Вы заменили изначальную структуру (список диапазонов) или этот список точек генерится по запросу?
А профит я так понимаю в том, что список упорядочен, т.е. сделали быстрый поиск?

ps И еще интересно чем мой вариант не подходит? Там ведь один проход по списку... (Если изначальный список не меняется все время конечно.)

[ilovb]

Если нужен быстрый поиск, то мой код тоже возвращает упорядоченный список непересекающихся диапазонов... И сравнить два таких списка элементарно.

[Губанов Сергей Юрьевич]

Не очень понял. Вы заменили изначальную структуру (список диапазонов) или этот список точек генерится по запросу?

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

Билдер билдер = НовыйБилдер();

// получаем данные из БД и засовываем их в билдер:
билдер.Добавить(123, 456);
билдер.Добавить(987, 10000);

// А теперь билдим сразу правильный список:
Список список = билдер.Собрать();

Внутри билдера упорядоченный двухсвязный список точек. Уж больно легко их мёржить. Надо найти начальную head и конечную tail точку, затем все что между ними сколлапсировать вот так:
head.next = tail;
tail.prev = head;

Уже забилженный "Список" - неизменный, там внутри массив. По массиву можно делать бинарный поиск.

[ilovb]

Понятно.
А есть возможность ваш код тут запостить? Хотя бы в урезанном виде.

ps Кстати псевдокод можно было и на ангельском. Я полиглот и не совсем кошерный одинэснег

[albobin]

Любопытно - это часть какой задачи ? Биллинг мг/мн ?

[albobin]

Нет, мг./мн - как-то сомнительно,  наверное, всё же это нечто с базой абонентских номеров?
 

[Губанов Сергей Юрьевич]

А есть возможность ваш код тут запостить? Хотя бы в урезанном виде.

Конечно, только я его ещё разок обмозгую, потом запощу сюда.

Кстати, в твоём алгоритме смежные диапазоны вроде не мёржатся? Те что отличаются на единицу?

У меня мёрж {{10, 20}, {21, 30}} даёт {{10, 30}}.

[albobin]

У меня мёрж {{10, 20}, {21, 30}} даёт {{10, 30}}.

А я в подобных задачах использую интервалы такого рода [x0,x1[   ( т.е  x1 не входит) Удобнее получается.

[Губанов Сергей Юрьевич]

Любопытно - это часть какой задачи ? Биллинг мг/мн ?

Раздача телефонных номеров.

Владелец множества телефонных номеров (оператор связи) может продать их подмножество другому владельцу (более мелкому оператору связи), а тот может продать подмножество подмножества номеров третьему владельцу и т.д.

Или раздача может делатся в рамках одного владельца, но по географическому/административному признаку. Область - район - посёлок, область - город - район и т.п. из этой оперы.