помогите придумать структуру данных

pitrik2

из файла считываются строки-шаблоны, на вход подается строка, нужно быстро уметь получать все шаблоны которым поданная строка удовлетворяет
строки-шаблоны все одинаковой длины N (щас это 9, может будет больше потом строка-шаблон это N ячеек, в каждой ячейке либо число либо звездочка, звездочка означает что тут любое число
примеры строк-шаблонов:


*,*,*,*,*,*,*,*,*

1,*,*,*,*,*,*,*,*

*,2,*,*,53,*,*,322,*

числа ну скажем ограничены 100, т.е. всего различных строк-шаблонов 100^9
поданная строка содержит только числа
т.е. если строка 1,2,3,4
то она удовлетворяет 1,2,3,4 и 1,2,3,* и *,*,*,* но не удовлетворяет 5,2,3,* и *,*,3,25
вот пример алгоритма (кажись он медленный):
изначально шаблоны кидаем в структуру с быстрой выбиркой (дерево или даже хешсет)
с поданной строкой составляются всевозможные шаблоны
т.е. 1,2,3,* и 1,2,*,4 и 1,2,*,* и т.д.
т.е. всего их 2^N
дальше все их проверяем есть ли такие, ну тойсть отфильтровываем, т.е. типа 2^N * log(n где n - число шаблонов

Serab

Имхо надо отсортировать множество шаблонов и построить бор :confused:

Marinavo_0507

тупое сравнение имеет сложность N*n, так что твой вариант действительно медленный
а как соотносятся числа 2^N и n?
если первое сильно меньше, то можно очевидно ускорить

pitrik2

тупое сравнение имеет сложность N*n, так что твой вариант действительно медленный
ну как, медленный в зависимости от n
n=100
2^N * log n = 512*7 = 3584
N*n = 9*100 = 900
n=1000
2^N * log n = 512*10 = 5120
N*n = 9*1000 = 9000

Dasar

сколько шаблонов?
сколько строк для обработки?

pitrik2

а как соотносятся числа 2^N и n?
если первое сильно меньше, то можно очевидно ускорить
я не знаю даже примерно какое будет n :(
но наверна нада рассчитывать что оно будет большое
просто если оно маленькое, то любой алгортитм довольно быстро отработает и это неинтересно
давай положим n>5000

Dasar

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

pitrik2

сколько строк для обработки?
очень много
не даже больше: ОЧЕНЬ много

pitrik2

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

Marinavo_0507

Раз ты исправил оценку, то непонятно, как ты собрался за log(n) найти шаблон, если одно сравнение стоит n
Я бы понял ещё N*log(n) и обойтись без сравнений, что, собственно, и хотел предложить.

Helga87

ОЧЕНЬ много
у тебя streaming процесс (т.е. новые "запросы" поступают постоянно) или stand-alone (по нажатию на большую красную кнопку обработать сто тыщ миллионов строк)?

pitrik2

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

pitrik2

Я бы понял ещё N*log(n) и обойтись без сравнений, что, собственно, и хотел предложить.
блин, ну N*log(n) наверна и правда правильнее
и то нет, зависит от структуры, ну типа это всё равно быстро должно быть
вон в том же боре попробуй оценить скорость узнавания есть этот элемент там или нет, зависит же от того как реализованы узлы бора, биты до 100 не пойдут, число 100 нифига не фиксировано

pitrik2

у тебя streaming процесс (т.е. новые "запросы" поступают постоянно) или stand-alone (по нажатию на большую красную кнопку обработать сто тыщ миллионов строк)?
первое
там мне потом надо будет отобранные шаблоны отсортировать
и выяснить есть ли такой набор шаблонов уже, если нет то создать
ну это уже какая нить хешмапа, там нада каждому набору потом значение некое посчитать
можно было бы на старте сразу все варианты посчитать, но их же дофигища, памяти стоко не будет и долго
вот что еще наверна важно
в реальном потоке довольно часто будут подаваться те же самые строки
но вот их захешить не оплучится, дело в том что изначальные шаблоны в процессе работы проги тоже могут меняться, редко но могут
ну или токо если хеш поданных строк вычищать при смене изначальных шаблонов, вощем это потом видно на практике будет...

Dasar

поподробнее плз...
на чем можно выиграть сравнения?
на отсечке заведомо не работающих шаблонов
допустим у нас есть шаблоны


1, *...

5, *...

10, *...

134, *...

тогда сравнив первое число строки с третьим вариантов, и узнав что строка больше, то варианты 1 и 2 можно не рассматривать.
после того как полностью сравнили первую цифру переходим ко второй и т.д.
соответственно, задача сводится к стандартному поиску по дереву, за одним исключением, что есть еще "звездочные" ветки, которые чуть более хитрые (если одна из подветок дерева "звездочная", то она обходится в любом случае)

Marinavo_0507

ну добавить ещё умножение на log(M где М-максимальное число
если вдруг максимального нет, то длинну строк и шаблонов надо измерять в битах, а не в позициях

AlexV769

Мне эта задача, если честно, напоминает сферических коней в вакууме.
Думаю, что для n=5k какой-нить grep -f будет работат достаточно быстро, если в шаблонах вместо * написать [0-9]* и окружить всё ^$, чтобы не выдумывать собственный велосипед.
Или я где-то промахнулся?
ps. Хотя обход дерева с отбрасыванием вариантов, конечно, более оптимален :)

Dasar

Или я где-то промахнулся?
grep разве не другую задачу решает?
оставить из входного потока только попадающие под фильтр?
а здесь для каждой строки из входного потока надо сказать каким фильтрам она удовлетворяет.

Marinavo_0507

Скорее всего тот же N*n.
В моих экспериментах grep (и perl) не проявлял излишнего интеллекта (шаблоны были только префиксными, так что задача была даже проще).

AlexV769

grep - фигуральное выражение о проверке применимости шаблонов приведением их к виду регулярного выражения и использования после этого стандартных библиотек.

Dasar

grep - фигуральное выражение о проверке применимости шаблонов приведением их к виду регулярного выражения и использования после этого стандартных библиотек.
так понятно )

AlexV769

вряд ли N*n
отброс будет идти по первому несовпадению ~= отброс шаблонов в рамках дерева завычетом преобразования integer => string

Maurog

сколько шаблонов?
сколько строк для обработки?
ты не ответил на один из этих вопросов
оцени размер префиксного дерева, если шаблонов 100^9 =)

tokuchu

Вообще, по набору шаблонов можно построить один конечный автомат, который будет разбирать поступающие строки и выдавать каким шаблонам они удовлетворяют за время O(n где n — длина входящей строки. Сам автомат строится не помню за какое время, но если шаблоны статичны, то думаю, что это лучший вариант.

pitrik2

ты не ответил на один из этих вопросов
оцени размер префиксного дерева, если шаблонов 100^9 =)
да не, стоко их не будет
давайте так положим
n может быть от 20 до 10000

pitrik2

Вообще, по набору шаблонов можно построить один конечный автомат, который будет разбирать поступающие строки и выдавать каким шаблонам они удовлетворяют за время O(n где n — длина входящей строки. Сам автомат строится не помню за какое время, но если шаблоны статичны, то думаю, что это лучший вариант.
о блин
ты примкнул к версии ?
я так понимаю он под грепом ентот автомат и имел ввиду

Maurog

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

Dasar

Вообще, по набору шаблонов можно построить один конечный автомат, который будет разбирать поступающие строки и выдавать каким шаблонам они удовлетворяют за время O(n где n — длина входящей строки. Сам автомат строится не помню за какое время, но если шаблоны статичны, то думаю, что это лучший вариант.
балансированное дерево - это и есть тот самый автомат.

tokuchu

я так понимаю он под грепом ентот автомат и имел ввиду
Не уверен, что он именно имел в виду. Но grep, наверняка, тоже автомат делает, наверняка, только он один шаблон ищет, хотя несколько легко объединяются.
В общем, твои шаблоны регулярные, а это прямая дорога к КА. Если только шаблоны не меняются настолько часто, что оверхед на построение автомата будет большой.

Marinavo_0507

Вообще, по набору шаблонов можно построить один конечный автомат, который будет разбирать поступающие строки и выдавать каким шаблонам они удовлетворяют за время O(n где n — длина входящей строки.
Только может случиться так, что памяти на его хранение может потребоваться exp(n ну и соотвественно времени на построение, а так ничего :D

tokuchu

балансированное дерево - это и есть тот самый автомат.
Смотря как этим деревом пользоваться. :)
У автомата есть "циклы", а у дерева нет. :)
Но автомат стоится из дерева регулярного выражения, на сколько я помню.

Marinavo_0507

вряд ли N*n
отброс будет идти по первому несовпадению
это не влияет на асимптотическую сложность в худшем случае

tokuchu

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

AlexV769

Я тут в душ сходил.
И вот что мне придумалось.
Пока входных строк 1 штука, совершенно всё равно как и что сортировать - автомат можно строить как по входной строке
(12|*...
и тогда получать линейное однократное сканирование списка шаблонов,
либо наоборот.
Почему-то мне кажется, что преобразование входной строки к регулярному выражению в данном случае даже более оправдано.
Приколы с существенным выигрышем по операциям начнутся как только нужно будет найти все шаблоны удовлетворяющие одновременно N входным строкам.
Тогда да, обход по дереву, построенному на шаблонах будет давать колоссальный выигрыш по сравнению с линейным сканированием.
ps. И вообще я не понял, откуда у топикстартера взялся log(n) без n впереди. В любом случае файл с шаблонами надо хотя бы прочитать - это уже как минимум n операций.

Dasar

за время O(n
такое возможно только при малом разбросе величин чисел
т.е. когда набор if-ов можно заменить на косвенную адресацию
более реальная оценка O(n*log(N/n - где n-длина , N-кол-во шаблонов

AlexV769

а, ну тогда действительно получится n*N
Только с данными n и N это совершенно по барабану :grin:

Dasar

И кстати, какого это оно должно быть балансированное? Тут, на сколько я понимаю, какое получится, такое получится.
берешь дерево которое получилось, и натравливаешь на него алгоритм балансировки => получаешь балансированное дерево

tokuchu

Только может случиться так, что памяти на его хранение может потребоваться exp(n ну и соотвественно времени на построение, а так ничего :D
(где n — длина шаблона но такой расход памяти будет если шаблонов у нас тоже такого порядка, т.е. полный набор. :) И не факт, что другие методы дадут лучшее потребление при этом.
А вообще это я уже сказал, что такой вариант для случая когда число шаблонов маленькое, а строк большое.
Кстати, мне даже кажется, что маленькое число шаблонов — это далеко не факт, что оно меньше числа строк. :)

Dasar

ps. И вообще я не понял, откуда у топикстартера взялся log(n) без n впереди. В любом случае файл с шаблонами надо хотя бы прочитать - это уже как минимум n операций.
из того, что за раз обрабатывается одна строка - совсем не следует, что программа перезапускается после каждой обработки одной строки.
соответственно, эффективная структура шаблонов строится один раз на все последующие обработки строк, и этим можно пренебречь.

Marinavo_0507

но такой расход памяти будет если шаблонов у нас тоже такого порядка, т.е. полный набор.
Нътъ.
В смысле, не только в этом случае.
Если ты вспомнишь, как строится детерминированный автомат из недетерминированного, то увидишь, где там экспонента.

tokuchu

такое возможно только при малом разбросе величин чисел
т.е. когда набор if-ов можно заменить на косвенную адресацию
более реальная оценка O(n*log(N/n - где n-длина , N-кол-во шаблонов
Ну да, предполагаем, что можем хранить большие таблицы, если шаблонов очень много. Думаю, что не стоит заморачиваться Болшими Числами, пока проблема явно не стоит.

tokuchu

берешь дерево которое получилось, и натравливаешь на него алгоритм балансировки => получаешь балансированное дерево
Эээ... либо я чего-то туплю, либо это из серии отбалансировать дерево разбора программы на каком-либо ЯП. В результате получим кашу.

Maurog

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

tokuchu

Нътъ.
В смысле, не только в этом случае.
Если ты вспомнишь, как строится детерминированный автомат из недетерминированного, то увидишь, где там экспонента.
Ну я сейчас точно не помню, а освежать знания меня ломает. Но там же большинство состояний просто отсеиваются за ненадобностью. А не будут они отсеиваться как раз в том случае, если шаблоны будут разнообразными.

Dasar

с деревом в узлах которого находятся элементы, которые можно сравнивать
здесь именно такое дерево и стоит строить

Dasar

Эээ... либо я чего-то туплю, либо это из серии отбалансировать дерево разбора программы на каком-либо ЯП. В результате получим кашу.
чего?

tokuchu

чего?
В общем правильно написал.
А как ты предлагаешь дерево сравнения делать для шаблонов?

Marinavo_0507

А не будут они отсеиваться как раз в том случае, если шаблоны будут разнообразными.
Навскидку мне кажется, что худший случай - это что-то типа
1 * * ... *
* 1 * ... *
...
* * * ... 1
2 * * ... *
...
* * * ... 2
...
...
...
* * * ... k
где n=kN, тогда префиксное дерево должно получиться размером что-то типа N^k, что эквивалентно exp(n так как n>>N
(ну то есть тут можно считерить тоже, но предлагаемый алгоритм не осилит)

Dasar

Ну да, предполагаем, что можем хранить большие таблицы, если шаблонов очень много. Думаю, что не стоит заморачиваться Болшими Числами, пока проблема явно не стоит.
если у тебя числа хотя бы от 1 до 100, то таблица размером 100^9 уже в память не влезет

tokuchu

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

Dasar

А как ты предлагаешь дерево сравнения делать для шаблонов?
для разбора следующих шаблонов


*, *, 3

1,*,4

*,2,5

3,1,6

не надо сравнивать первые и вторые числа, а надо сравнивать сразу третье
и общая сложность будет 5 сравнений (3 в худшем на последней цифре + по одному на второй и первой)
и это важное отличие от префиксного дерева, где сравнение всегда идет слева направо.

tokuchu

Навскидку мне кажется, что худший случай - это что-то типа
1 * * ... *
* 2 * ... *
...
* * * ... N
(N+1) * * ... *
...
* * * ... 2N
...
...
...
* * * ... kN
Чего-то сомнительно, что это будет плохой случай. Там же почти линейная структура автомата получается, наверное. Ну даже если он не такой простой, то наверняка не больше, чем (kN)^2.

tokuchu

не надо сравнивать первые и вторые числа, а надо сравнивать сразу третье
и общая сложность будет 5 сравнений (3 в худшем на последней цифре + по одному на второй и третьей)
и это важное отличие от префиксного дерева, где сравнение всегда идет слева направо.
А у него длина шаблона = длина строки?

Dasar

А у него длина шаблона = длина строки?
насколько я понял - да, но, в целом, это не важно - идея алгоритма таже останется

tokuchu

идея алгоритма таже останется
Ну тогда например 3-я позиция в шаблоне может соответствовать 3,4,... позиции в строке. Это перебор получится и сложность будет (длина шаблона)*(длина строки). В таком случае, если есть желание, есть алгоритмы, которые позволяют проверить шаблон, проверяя не все символы строки. Я правда не вспомню, можно ли их для нескольких шаблонов параллельно обобщить.
А если длина шаблона строго равна длине строки, то конечно же КА — это излишество уже. :) Тут можно для построения дерева даже жадные алгоритмы применить, наверное.

AlexV769

Всё равно не понятно.
Для того, чтобы кол-во операций по шаблонам было k < n, (например, k=log(n нужно, чтобы (n-k) строк вообще не обрабатывались. Как этого добивается топикстартер в случае с
1,2,3,4,5,6,7,8,9
в качестве входной строки и n строк вида
1,2,3,4,5,6,7,8,X
X > 9
в качестве шаблонов?
Где тут будет редуцирование операций?
Линейная составляющая по кол-ву шаблонов в любом случае должна присутствовать.

tokuchu

Кстати это дерево сравнений всё равно небалансируемое, т.к. все сравнения ниже зависят от того, что ты сравнивал выше. И если ты будешь менять корень, то перетряхнётся всё дерево, которое ниже лежит. Причём при этом длины ветвей сохраняться не обязаны.
Если бы у нас была такая ситуация, что мы сравниваем позицию и в зависимости от результата имеем _непересекающиеся_ альтернативы по дальнейшим операциям сравнения, тогда, конечно, да. Здесь можно было бы и балансировать и прочее.
Но тут ситуация другая. В каждом из поддеревьев может быть полный набор оставшихся сравнений. Так что такое дерево тоже потенциально может быть размером (число альтернатив)^(длина шаблона). Тут оптимизация только в том, что такое дерево можно строить быстрее (возможно). Но по памяти оно тоже может быть большим.

Marinavo_0507

да, я стормозил я с экспонентой, скорее может получиться k^N что тоже не сахар при N=9 или даже больше

tokuchu

да, я стормозил я с экспонентой, скорее может получиться k^N что тоже не сахар при N=9 или даже больше
У меня такое чувство, что такие числа будут и в других случаях "структурирования" шаблонов. Да и сами эти шаблоны при таких числах немало места занимать будут. :)

Serab

кстати
это первое что мы на доске на работе нарисовали...
чо, реально на этом остановится?
нет, конечно, надо еще продумать как ходить по этому дереву =)
ладно, шучу.
По-моему это идеальный вариант для твоей задачи: перестраивать дерево надо не так уж и часто, тебе надо минимизировать время обработки единичных запросов. Построенное дерево в идеале занимает в памяти примерно столько же (чаще даже меньше) места, чем полный массив Nxn, который все равно надо прочитать. И строится примерно за то же время (с точностью до log (N) множителя

Maurog

поддерживаю
префиксное дерево из шаблонов должно быстро работать
функционирование дерева такое же, как и работа недетерминированного автомата (состояние описывается множеством вершин)
в конечных вершинах (а их ровно столько, сколько шаблонов) имеется ссылка на соответствующий шаблон
сделав 9 шагов по дереву, мы получим состояние, которое содержит только финальные вершины, в которых прописаны искомые шаблоны (сложность проверки, конечно, не 9, но не большая)
очевидно, что это не будет наилучшим решением, однако это будет наилучшим в среднем имхо
есть пути дальнейшей оптимизации:
заметим, что префиксное дерево зависит от порядка символов в шаблонах, а искомая задача - не зависит
то есть применив некую перестановку (речь о математической перестановки из алгебры) к шаблонам и к каждому входному слову, мы получаем эквивалентную задачу, однако префиксное дерево может оказаться кардинально другим
можно из этих деревьев выбирать наиболее оптимальные
например, имея шаблоны (9 заменим на 6)
*, *, *, *, *, 1
*, *, *, *, *, 2
*, *, *, *, *, 3
*, *, *, *, *, 4
для построения оптимального дерева я бы переставил последнее число и первую звездочку. тем самым на первом же шаге (при проходе по префиксному дереву) мы бы отрезали неподходящие варианты
однако не имею представления как сформулировать критерий оптимальности дерева в общем случае и не думаю, что можно существенно что-то ускорить здесь (только если существует специфика шаблонов)
дерево еще хорошо тем, что из него легко удаляется один шаблон и добавляется другой

tokuchu

однако не имею представления как сформулировать критерий оптимальности дерева в общем случае и не думаю, что можно существенно что-то ускорить здесь (только если существует специфика шаблонов)
Например такой вариант — чтобы максимальное поддерево после проверки этой позиции содержало минимальное число вершин. Хотя это минимальную длину не гарантирует, но может даже и гарантирует — это надо обдумывать.

Dasar

Где тут будет редуцирование операций?
для такого набора шаблонов строится следующее дерево (балансировка будет только по последней цифре):
для наглядности пусть будет 10 шаблонов, с последней цифрой от 11 до 20
сбалансированное дерево будет


сравнивать последнюю цифру с 15

   1) сравнить последнюю цифру с 13

     1) сравнить последнюю цифру с 11

       1) сравнить первую цифру с 1

         1) сравнить вторую цифру с 2

           1) сравнить третью цифру с 3

              ...

     2) сравнить последнюю цифру с 14

       1) сравнить первую цифру с 1

         1) сравнить вторую цифру с 2

           1) сравнить третью цифру с 3

              ...

   2) сравнить последнюю цифру с 17

     1) сравнить последнюю цифру с 16

       1) сравнить первую цифру с 1

         1) сравнить вторую цифру с 2

           1) сравнить третью цифру с 3

              ...

     2) сравнить последнюю цифру с 19

       1) сравнить последнюю цифру с 20

        1) сравнить первую цифру с 1

          1) сравнить вторую цифру с 2

            1) сравнить третью цифру с 3

              ...

Где тут будет редуцирование операций?
соответственно по этому дереву будет задано лишь три вопроса для строки
1,2,3,4,5,6,7,8,9

Dasar

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

tokuchu

в дереве у нас есть, как взаимоисключающие варианты, так и нет - ни то, ни другое - балансировку усложняет, но не отменяет.
Блин... ты сравнение одной позиции методом дихотомии считаешь балансировкой дерева? (судя по посту выше)
А я дерево описывал в котором в одном узле одно "глобальное" сравнение позиции. И такое дерево не балансируется.
А сравнение одной позиции можно как угодно оптимизировать, но балансировкой я бы называть это не стал.

Dasar

А я дерево описывал в котором в одном узле одно "глобальное" сравнение позиции. И такое дерево не балансируется.
очень плохо, но тоже балансируется: начинать с позиции где меньше всего звездочек, это и есть упрощенная балансировка

tokuchu

очень плохо, но тоже балансируется: начинать с позиции где меньше всего звездочек, это и есть упрощенная балансировка
Это не балансировка дерева, а алгоритм построения оптимального.
Балансировка — это когда дерево у тебя уже есть, и ты его преобразуешь. При этом узлы сохраняются.

Dasar

Это не балансировка дерева, а алгоритм построения оптимального.
Балансировка — это когда дерево у тебя уже есть, и ты его преобразуешь. При этом узлы сохраняются.
и что не так?
например, шаблоны
1, 2,1
1, 2,2
1, 2,3
1, 2,4
1, 2,5
и т.д.
1, 3,1
1, 3,2
и т.д.
у тебя есть исходное дерево (очень грубо):


1) сравнить первую позицию

   1) сравнить вторую позицию

     1) сравнить третью позицию

        и т.д.

     2) сравнить третью позицию

        и т.д.

     3) сравнить третью позицию

        и т.д.

     4) сравнить третью позицию

        и т.д.

   2) сравнить вторую позицию

     1) сравнить третью позицию

        и т.д.

     2) сравнить третью позицию

        и т.д.

     3) сравнить третью позицию

        и т.д.

     4) сравнить третью позицию

        и т.д.

  3) сравнить вторую позицию

     1) сравнить третью позицию

        и т.д.

     2) сравнить третью позицию

        и т.д.

     3) сравнить третью позицию

        и т.д.

     4) сравнить третью позицию

        и т.д.

   4) сравнить вторую позицию

     1) сравнить третью позицию

        и т.д.

     2) сравнить третью позицию

        и т.д.

     3) сравнить третью позицию

        и т.д.

     4) сравнить третью позицию

        и т.д.

ты на него смотришь и видешь, что если сравнения поменять местами, то дерево уменьшится:


1) сравнить третью позицию

   1) сравнить вторую позицию

     1) сравнить первую позицию

   2) сравнить вторую позицию

     1) сравнить первую позицию

  3) сравнить вторую позицию

     1) сравнить первую позицию

   4) сравнить вторую позицию

     1) сравнить первую позицию

  и т.д.

соответственно - это и есть алгоритм балансировки - перестроение исходного дерева

tokuchu

соответственно - это и есть алгоритм балансировки - перестроение исходного дерева
При балансировке число узлов и они сами не меняются. Меняется глубина. :)

Dasar

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

tokuchu

Ну фактически ты строишь новое дерево. А термин "балансировка" всё же прижился в другом контексте, хотя может это только в моём сознании так. В общем мы только в терминологии не сходимся. :)

Dasar

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

asvsergey

Что то мне кажется, что тут без дерева можно обойтись.
Составить 9 разбиений всех шаблонов на категории, каждая категория отвечает за одну позицию в шаблоне, если числа от 1 до 100, то по 99 категорий в разбиении. Каждой строке будет соответсвовать по одной категории из этих 9 разбиений, взяв пересечение этого множества получим все шаблоны. Пересечение упорядоченых масивов делать легко, принадлежность к категории тоже легко определить.

Dasar

взяв пересечение этого множества получим все шаблоны
как это сделать быстро?

asvsergey

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

Serab

девятью итераторами имхо трудновато будет. Все равно придется попарно сливать, нет?

Marinavo_0507

N*n*log(M) получается, худший случай - когда почти везде звёздочки - списки будут длинными

Serab

где M=N, или я невнимательно тред прочитал?

Serab

А, нашел. M — максимальное число? Причем тут оно в этом решении?

Marinavo_0507

М - это максимальное целое число, или количество разных чисел в шаблонах
оно тут при том, что "100 категорий в каждом разбиении"

Serab

А, ну я тоже не понял причем тут категории.
Я понял его идею так: 9 раз сортируем массив шаблонов по каждому столбцу в отдельности. Потом по числу в очередной позиции входной строчки несложно получаем упорядоченную последовательность номеров подходящих образцов, сливаем. Но это то же самое, что и дерево, чуть медленнее.

tokuchu

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

Marinavo_0507

Но это то же самое, что и дерево, чуть медленнее.
Я бы сказал, это то же тупое сравнение, но вид сбоку.

Serab

ну да: это как сортировка вставками: место для вставки можно найти за логарифм отсортированного участка, но он съедается тем, что сама вставка за линейное время выполняется. Здесь тоже: можно и без всякой сортировки находить эти множества (набор индексов при этом тоже получается естественным, т.е. упорядоченным но это просто уменьшает константу где-то в два раза.
Но с деревом тоже не стоит сильно искушаться: ответ — это подмножество шаблонов, размер которого дает довольно жесткое ограничение на сложность.

asvsergey

девятью итераторами имхо трудновато будет. Все равно придется попарно сливать, нет?

9 итераторами просто :)
Берешь первые 9 значений, находишь максимум и минимум, если не равны, все что меньше максимума начинаешь продвигать дальше по масиву, пока не станут больше равны, получаешь новый максимум, старый максимум становится минимумом, когда минимум с максимумы равны - это искомое значение, все масивы проходишь один раз, дла каждого продвижения по масиву используется одно сравнение с текущим максимумом.

apl13

Тред нечетал, минимальные ацикличные автоматы упоминались? :crazy:

asvsergey

А, ну я тоже не понял причем тут категории.
Я понял его идею так: 9 раз сортируем массив шаблонов по каждому столбцу в отдельности. Потом по числу в очередной позиции входной строчки несложно получаем упорядоченную последовательность номеров подходящих образцов, сливаем. Но это то же самое, что и дерево, чуть медленнее.

Не совсем так, я имел ввиду хранить 9х100 упорядоченых масивов, каждый массив соответсвует позиции и числу или звездочке, при добавлении шабшлона мы добавляем его номер в те масивы, к которым он подходит, т.е в случае * во все масивы для данной позиции, либо в один конкретный (можно завести отдельный масив для * и класть туда, тогда надо будет искать пересечение 18 масивов).
Для строчки берем 9 конкретных подходящих для нее масива и пересекаем.

Serab

А что за 100?

asvsergey

Я бы сказал, это то же тупое сравнение, но вид сбоку.

Да сравнение, но не тупое :)

Maurog

изначально шаблоны кидаем в структуру с быстрой выбиркой (дерево или даже хешсет)
с поданной строкой составляются всевозможные шаблоны
т.е. 1,2,3,* и 1,2,*,4 и 1,2,*,* и т.д.
т.е. всего их 2^N
дальше все их проверяем есть ли такие, ну тойсть отфильтровываем, т.е. типа 2^N * log(n где n - число шаблонов
решение, имеющее право на жизнь
1) шаблоны упорядочены (лексикографически, * меньше любого числа)
2) для входного слова (a1, a2, ...aN) определяем множество всех шаблонов (их будет 2^N)
упорядочиваем их
3) считаем intersection двух множеств - это и есть искомый результат
сложность операции 1) - n*log(n)
сложность операции 2) - const(N)
сложность операции 3 как уже выше писали n + 2^N (в худшем случае)
для n = 10000, N = 9 это может быть вполне неплохо
поясню операцию 2 - при фиксированном N _порядок_ этих самых шаблонов на самом деле не зависит от входного слова. поэтому 2^N шаблонов можно сгенерить и упорядочить в самом начале (либо завести умный итератор, который в правильном порядке будет обходить эти шаблоны)

asvsergey

100 значений, которое может принимать число:
числа ну скажем ограничены 100, т.е. всего различных строк-шаблонов 100^9

Serab

Ну вот это очень плохо, имхо. Т.е. это с тем же успехом можно сказать, что массивы надо всегда сортировать подсчетом: пусть только количество различных чисел будет 50.

Dasar

to и : так вы помните, что слияние списков очень затратная операция в плане константы (которая идет перед оценкой сложности): для каждого списка же надо память выделить, потом прибить и т.д.?

asvsergey

to и : так вы помните, что слияние списков очень затратная операция в плане константы (которая идет перед оценкой сложности): для каждого списка же надо память выделить, потом прибить и т.д.?

Где ты увидел слияние списка?

Dasar

Где ты увидел слияние списка?
считаем intersection двух множеств

asvsergey

Это было в условии задачи, если числа не ограничены небольшим числом, то нужно реализовывать по другому.

Serab

А, прощу прощения :crazy:

asvsergey

Слияние и пересечение это разные вещи.

Dasar

Слияние и пересечение это разные вещи.
т.е. выделение памяти не будет?

Dasar

Слияние и пересечение это разные вещи.
если по занудствовать, то пересечение - это частный случая слияния.

Serab

А если занудствовать, то есть правила Де-Моргана. Так-то.

Dasar

А если занудствовать, то есть правила Де-Моргана. Так-то.
как они здесь применимы?

Serab

Ну типа пересечение не сложнее объединения. Объединение не сложнее пересечения.

Maurog

to и : так вы помните, что слияние списков очень затратная операция в плане константы (которая идет перед оценкой сложности): для каждого списка же надо память выделить, потом прибить и т.д.?
я не вижу много затрат при подсчете пересечения двух множеств
результат пересечения - это список ссылок (указателей, на прогр. языке) на элементы уже существующих множеств (или одного из множеств, это ведь пересечение)
оффтоп: списки отстой, вектор + указатели рулят =)

Dasar

это список ссылок
с динамическим выделением памяти?

Dasar

типа пересечение не сложнее объединения. Объединение не сложнее пересечения.
это не морган

Maurog

со статическим, N =9 ведь фиксировано
512 указателей хватит
да и вообще тебя понесло не туда=) спички считаешь)
гораздо больше потерь будет при конвертации строки "a1, a2, , a9" в набор чисел =)

Serab

http://ru.wikipedia.org/wiki/Законы де Моргана

Dasar

гораздо больше потерь будет при конвертации строки "a1, a2, , a9" в набор чисел =)
допустим шаблонов тысяч 9,
хочешь сказать что слить 9 раз списки размером тысяча каждый, это дольше чем распарсить строку длиной 40 символов?
сливаться-то списки будут на каждую входную строчку, а не один раз предварительно.

Dasar

http://ru.wikipedia.org/wiki/Законы де Моргана
для танкистов, покажи, пожалуйста, полностью логическую цепочку (т.е. как связаны мой пост, твой пост с двумя отрицаниями и законы моргана)

Serab

вместо исходных массивов сразу получаем дополненные, это не увеличивает сложность. Дальше вместо пересечений реализуем дополнение, либо наоборот. Дополнение полученного массива делается в один проход — явно не сложнее, чем все остальное.

Maurog

Ну типа пересечение не сложнее объединения. Объединение не сложнее пересечения.
честно говоря, я тоже не понял как ты из законов де Моргана сделал вывод о сложности соответствующих операций =)
по-моему, надо изучить сложность операции "дополнение" для начала=)

Serab

это я обдумал, но не стал писать.
Но это странно: рассуждать о сложности объединения и пересечения в сравнении с дополнением.

Dasar

вместо исходных массивов сразу получаем дополненные
что такое дополненные массивы?

Serab

Наверное стоит удалить все, что я писал выше =)

asvsergey

Я тут подумал, что если использовать вместо упорядоченых масивов битовые поля, то сэконмится память и увеличится быстродействие, взять пересечение битовых полей - элеметарная операция.

Serab

Не поверишь, но я тоже об этом думал.
В общем так: предлагаю написать оба варианта и потестить скорость на настоящих данных.

asvsergey

Хотя про память может и наврал, чет не соображаю после работы :(

asvsergey

Можно, но пока не знаю как со временем будет.

Serab

Ну вообще этим бы топикстартеру в самую пору заняться.
Оставить комментарий
Имя или ник:
Комментарий: