Форум: "Прочее";
Текущий архив: 2006.07.23;
Скачать: [xml.tar.bz2];
Вниз
Задачка. Надой найти кратчайшее решение. Найти похожие ветки
← →
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]пятница была вчера, так что придётся ждать следующей пятницы:)
шутка
принципиальный момент, который не указан в условии
могу ли быть в множестве диапазонов kX такие диапазоны, числа в которых невыразимы ввиде X and M?
← →
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)) тому диапазону.
← →
Verg © (2006-06-25 00:39) [20]
> Юрий Зотов © (24.06.06 11:52) [1]
> Многа букафф, ниасилил...
> :о)
> <Цитата>
Ты мне тоже очень нравиШся.
← →
Verg © (2006-06-25 00:59) [21]
> в [10] сказано, что MAX может быть охрененном большим числом
> как же хватает памяти для хранения nD, как он хранится,.
> ..
Это Вас , уважаемый, не должно беспокоить. Техника тут не при чем. Оно все решено, Главное - принцип: можно ли, а если можно, то предложи как (если не в лом).
← →
default © (2006-06-25 10:59) [22]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?(учитывая, что ранее говорили - памяти брать много нельзя)
тогда надо знать как хранятся множества диапазонов(
← →
Verg © (2006-06-25 14:35) [23]
> 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 пр.), кроме алгоритма последовательного применения правил (т.е. "в лоб").
← →
Verg © (2006-06-25 14:51) [24]Пример:
В диапазонном классификаторе сетевых 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 битов.
← →
default © (2006-06-25 16:26) [25]Verg © (25.06.06 14:51) [24]
а как операция in реализуется?
"in 01:00:00:00:00:00"
часто множество диапазонов "так убористо"?
почему операцию & хочется сменить диапазонами?(или просто надо и мне отстать с подобным вопросом?:))
ведь её убирание приводит к возрастанию числа диапазонов и, как следствие, к тормозам при обработке
← →
Verg © (2006-06-25 17:01) [26]
> 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 (размерность) переменной. т.е. Если существует хотя бы одно правило, требующее предварительного маскирования, к гиперкубу надо просто добавить размерность, соответствующую значением элемента вектора с наложенной маской.
← →
default © (2006-06-25 20:02) [27]Verg © (25.06.06 17:01) [26]
"Я тут подумал, что есть такой выход:"
проблема разрешилась?
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2006.07.23;
Скачать: [xml.tar.bz2];
Память: 0.53 MB
Время: 0.011 c