Задачка. Надой найти кратчайшее решение.

← →
Verg © (2006-06-24 11:46) [0]

Дано: 1. набор непересекающихся диапазонов nD = [D1,D2...Dn] в области 0..MAX 2. число M в этой же области Задача: Получить набор диапазонов kX = [X1, X2 .... Xk] токой, что если Y = (X and M) (не)принадлежит nD то X (не)принадлежит kX где 0 <= X <= MAX, and - поразрядная коньюнкция (bitwise and) Все числа целые

← →
Юрий Зотов © (2006-06-24 11:52) [1]

Многа букафф, ниасилил...
:о)

← →
default © (2006-06-24 12:10) [2]

пятница была вчера, так что придётся ждать следующей пятницы:)
шутка

принципиальный момент, который не указан в условии
могу ли быть в множестве диапазонов kX такие диапазоны, числа в которых не выразимы ввиде X and M?

← →
default © (2006-06-24 12:10) [3]

← →
default © (2006-06-24 12:18) [4]

пардон, ошибся в формулировке
вот так правильно:
могу ли быть в множестве диапазонов kX такие диапазоны, для некоторых чисел X в которых X and M не принадлежит nD?

← →
default © (2006-06-24 12:22) [5]

блин, там же в скобочках указано это:)
вот что значит утро после хорошо отмеченной зашиты диплома

← →
Verg © (2006-06-24 12:26) [6]

> default © (24.06.06 12:10) [3]

> могу ли быть в множестве диапазонов kX такие диапазоны,
> числа в которых невыразимы ввиде X and M?

Могут.

Y вовсе не обязано принадлежать kX

По другому задачу можно поставить и так:

Есть функция
F(X) = (X and M) in kD;

надо преобразовать kD в kX зная M так, чтобы
функция

F(X) = X in kX;

давала те же результаты для любого X

← →
default © (2006-06-24 12:47) [7]

навскидку можно выделить следующие моменты:
1)учитывать, что X and M может давать один и тот же выход для разных входов X(чтобы по нескольку раз не проверять принадлежность одно и того же Y к nD), сохраняя результаты проверки на принадлежность или ещё как
2)отсортировать nD для ускоренной проверки принадлежности числа какому-либо диапазону из nD

больше нюансов в задаче я не вижу
кстати, что значит кратчайшее решение?

← →
default © (2006-06-24 13:04) [8]

кстати, память на массив длины MAX+1 типа Boolean можно взять?
если - да, то задача компактно и быстро решится

← →
Verg © (2006-06-24 13:06) [9]

> больше нюансов в задаче я не вижу

Задача не в быстром определении принадлежности X множеству диапазонов.
Это само собой все. Цена операции in пренебрежимо мала, зато
операция X and M для F(X) недопустима вовсе.

Потому и задача преобразовать диапазон nD в kX так, чтобы X in kX было эвивалентно (X and M) in nD

← →
Verg © (2006-06-24 13:08) [10]

> кстати, память на массив длины MAX+1 типа Boolean можно
> взять?

MAX ~>> 2 ^ 32

← →
Alx2 © (2006-06-24 13:33) [11]

Правильно ли я понял, что новое множество Xk для множества Dk будет составлено из элеметов x, таких что( x & M) in Dk? Время для построения одного множества Xk существенно ограничено? Сразу есть решение "в лоб", состоящее в переборе всевозможных значений разрядов у всех d in Dk, соответствующих нулевым разрядам в числе M и формирования из них мн-ва Xk.

← →
Alx2 © (2006-06-24 13:39) [12]

Время работы алгоритма будет O(N*2^p) где N - количество элементов множества nD. p - количество нулевых разрядов в числе M.
Нужно быстрее?

← →
Alx2 © (2006-06-24 13:50) [13]

Максимум, чего можно добиться в сокращении работы такого подхода - рассматривать только элементы, у которых не совпадают наборы на разрядах, соответствующие единичным разрядам M.
Тогда в контексте предыдущего поста N - количество попарно различных элементов. Различие понимается в смысле: x1 <> x2, если x1&M<>x2&M

← →
default © (2006-06-24 13:51) [14]

Verg © (24.06.06 13:06) [9]
так какие требования предъявляются к решению?
почему просто циклом по всем X не пройтись для решения задачи, если цена проверки на принадлежность пренебрежимо мала?
иксы прошедшие проверку будут идти в возрастающем порядке
массив диапазонов сформировать в этих условиях легко...
если иксы: 2,6,7,8,10,11,12, то диапазоны 2,6..8,10..12
не понятно, что сделать-то нужно...какое нужно решение...

← →
default © (2006-06-24 14:11) [15]

"где N - количество элементов множества nD"
элементы этого множества - диапазоны
тогда N должно быть равно числу чисел во всех диапазонах, видимо?

← →
Alx2 © (2006-06-24 14:15) [16]

> [15] default © (24.06.06 14:11)
> "где N - количество элементов множества nD"
> элементы этого множества - диапазоны
> тогда N должно быть равно числу чисел во всех диапазонах,
> видимо?

Да, действительно диапазоны. Тогда ой. С предложенным мной подходом вечность обеспечена :)

← →
default © (2006-06-24 14:29) [17]

Alx2 © (24.06.06 14:15) [16]
меня ещё вот что удивляет
в [10] сказано, что MAX может быть охрененном большим числом
как же хватает памяти для хранения nD, как он хранится,...
к тому же сказано, что "Цена операции in пренебрежимо мала"
как же так получается, что находится память для такого охренненного множества nD да ещё проверка на принадлежность числа к этому множеству имеет пренебрежимо малую цену

← →
Alx2 © (2006-06-24 14:40) [18]

> [17] default © (24.06.06 14:29)

Ну это уже несколько "в сторону". Пусть так хочется, например :)

Как я понял, очень долго работет "and". Вот если создать для него что-то вроде хэш функции, или построить структуру а-ля автомат для быстрого вычисления клятого "and". А на построение новой системы множеств таки уйдет вагон памяти и времени, так как ограничений практически нет.

← →
Verg © (2006-06-25 00:28) [19]

К теме "клятого and"

Есть классификатор данных.
Есть вектор данных размерностью в N.
Этот вектор нужно отнести к одному из тысяч правил, с которыми сопоставлены тысячи диапазонов значений полей того вектора. Долго объяснять....
....И все замечательно, пока некоторые из правил не выдвигают условий не принадлежности значеия некоемогу диапазону, а принадлежности некоей ф-ции над величиной (F(X)) тому диапазону.

> в [10] сказано, что MAX может быть охрененном большим числом
> как же хватает памяти для хранения nD, как он хранится,.
> ..

Это Вас , уважаемый, не должно беспокоить. Техника тут не при чем. Оно все решено, Главное - принцип: можно ли, а если можно, то предложи как (если не в лом).

Verg © (25.06.06 00:28) [19]
это понятно
кстати, "некоей ф-ции над величиной", X and M взяли для примера, или это не единственная функция которую нужно "устранить"?

поясните сначала в чём не подходит решение в лоб
цикл по всем X(в возрастающем порядке), в цикле Y = X and M считаем, вычисляем Y in nD(говорили что эта операция выполняется почти за даром)
и по ходу цикла формируем множество диапазонов kX
"иксы прошедшие проверку будут идти в возрастающем порядке
массив диапазонов сформировать в этих условиях легко...
если иксы 2,6,7,8,10,11,12, то диапазоны 2,6..8,10..12"

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

> X and M взяли для примера, или это не единственная функция
> которую нужно "устранить"?

Единственная функция.

> поясните сначала в чём не подходит решение в лоб
> цикл по всем X(в возрастающем порядке), в цикле Y = X and
> M считаем, вычисляем Y in nD(говорили что эта операция выполняется
> почти за даром)
> и по ходу цикла формируем множество диапазонов kX
> "иксы прошедшие проверку будут идти в возрастающем порядке
> массив диапазонов сформировать в этих условиях легко...
> если иксы 2,6,7,8,10,11,12, то диапазоны 2,6..8,10..12"

Не подходит тем, что оно "в лоб". Это решение первое, что приходит в голову, но может существует более оптимальное. Слишком много X надо перебирать....

> быть может Вы хотите формировать kX на месте nD?(учитывая,
> что ранее говорили - памяти брать много нельзя)
> тогда надо знать как хранятся множества диапазонов(

Нет, не обязательно на месте. Диапазоны представлены сортированным списком объектов - парами чисел (объектов) start,end. Сортировка по start, диапазоны не пересекаются.

Проблема касается практически любых алгоритмов классификации (HyperCuts, RuleSets пр.), кроме алгоритма последовательного применения правил (т.е. "в лоб").

Пример:
В диапазонном классификаторе сетевых ethernet пакетов одно из правил хочет выделять из трафика все мультикасты и бродкасты для vlan тэгов от 64 до 100 или 300:

правило выглядит просто

dstmac & 01:00:00:00:00:00 in 01:00:00:00:00:00 vlan in 64-100, 300

если бы правилу было бы зпрещен модификатор &, то как бы оно выглядело?

128 диапазонов поля dstmac. Теоритически в этом нет ничего страшного, но хотелось бы, чтобы сие приеобразование выполнял компилятор классификатора автоматически. С другой стороны сколько операций and и in придется выполнить для построения диапазонного списка при "решении в лоб"? Mac адрес - 48 битов.

Verg © (25.06.06 14:51) [24]
а как операция in реализуется?
"in 01:00:00:00:00:00"
часто множество диапазонов "так убористо"?
почему операцию & хочется сменить диапазонами?(или просто надо и мне отстать с подобным вопросом?:))
ведь её убирание приводит к возрастанию числа диапазонов и, как следствие, к тормозам при обработке

> default © (25.06.06 16:26) [25]
> Verg © (25.06.06 14:51) [24]
> а как операция in реализуется?
> "in 01:00:00:00:00:00"

Двоичным поиском подходящего диапазона из сортированного списка.
Аналогично FindNearest в BDE.

> часто множество диапазонов "так убористо"?

Нет, это только пример. И таких правил от сотен до дес. тысяч

> почему операцию & хочется сменить диапазонами?(или просто
> надо и мне отстать с подобным вопросом?:))
> ведь её убирание приводит к возрастанию числа диапазонов
> и, как следствие, к тормозам при обработке

Для поиска подходящего правила применяются методы исключающие необходимость последовательного перебора. Но для этого заранее строится (компилируется) структура для разового поиска (гиперкуб или еще что-то в зависимости от алгоритма). Грубо говоря за одну операцию поиска диапазона сразу определяется множество правил, которым данная величина удовлетворяет. В таких алгоритмах, для того, чтобы определить набор правил, которым удовлетворяют все элементы вектора данных необходимо максимум K поисков, где K - размерность вектора (количество элементов).
Если бы правила применялись последовательно, то понадобилось бы K*N операций поиска, где N- количество правил.
Обычно K - 2..10, а N - от единиц до дес. тыс.
Как известно, при двоичном поиске скорость поиска зависит логарифмически (по основанию два) от количества элементов среди которых производится поиск. Т.о. от количества диапазонов (а значит и от N) скорость работы зависит достаточно слабо.

Я тут подумал, что есть такой выход:
Для того, чтобы изобразить в тех алгоритмах предварительную операцию над входными данными придется сделать K (размерность) переменной. т.е. Если существует хотя бы одно правило, требующее предварительного маскирования, к гиперкубу надо просто добавить размерность, соответствующую значением элемента вектора с наложенной маской.

Задачка. Надой найти кратчайшее решение. Найти похожие ветки