Поспорим о быстродействии, господа суровые программисты?

Задача на хороший алгоритм. Из жизни.
 
EE Татарин #13.04.2009 11:32  @Balancer#13.04.2009 11:26
+
-
edit
 

Татарин

координатор
★★★★☆
Balancer> Который на несколько строк разбит. Т.е.:
Balancer> Если так нельзя - то сильно быстрее ;)
Вообще, считай, что переводов строки нет, для простоты и чистоты задачи.
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  1.0.154.531.0.154.53
RU Balancer #13.04.2009 11:58  @Татарин#13.04.2009 11:31
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> Смотри, ты же можешь в первом его включении вынести его за болд, поставить первым.

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

$ php markup.0.php
1: 0,00144195556641
10: 0,0147280693054
100: 0,397891044617
500: 7,74917697906
1000: 29,6116909981

code text
  1. 000 <b><i><span color="#ff0000">rrrrr <span color="#00ff00"> gggg</span></span></i></b><i><span color="#ff0000"><span color="#00ff00">gggg<span color="#0000ff">bbbbb</span>ggggg</span>rrrr</span></i>


А вот с пермутациями тэгов - да, в голову ничего быстрого не приходит.
 
+
-
edit
 

Balancer

администратор
★★★★★
$ php markup.php
1: 0,0018789768219
10: 0,0115969181061
100: 0,383130788803
500: 7,61049103737
1000: 29,8531341553

[code html]
000 rrrrr ggggggggbbbbbgggggrrrr
[/code html]

Но я поступил нечестно и мой способ редукции работает только для сочетаний i и b :)

Сейчас подумаю на счёт color.
 
+
-
edit
 

Balancer

администратор
★★★★★
$ php markup.php
1: 0,00167107582092
10: 0,0124468803406
100: 0,384516000748
500: 7,91936206818
1000: 30,9722850323

code html4strict
  1. 000 <i><b> <span color="#ff0000">rrrrr <span color="#00ff00"> gggg </span></span></b><span color="#ff0000"><span color="#00ff00"> gggg<span color="#0000ff">bbbbb</span>ggggg</span>rrrr </span></i><span color="#ff0000"> </span>


Вроде, окончательный вариант в первом приближении :)
 
RU Balancer #13.04.2009 12:49  @Татарин#13.04.2009 07:58
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> Мама \bмыла\i раму\color(#ff0000)\b, но\color=(#00ff00)

color(..), или color=(..), или оба?
 
+
-
edit
 

Balancer

администратор
★★★★★
$ php markup.php
1: 0,00154280662537
10: 0,0104448795319
100: 0,296799898148
500: 6,37055897713
1000: 24,2174150944

code text
  1. Мама \bмыла\i раму\color(#ff0000)\b, но\color(#00ff00)\i я б её \iлучше\color покрасил.

превращается в

code html4strict
  1. Мама <b>мыла<i> раму</i></b><span style="color:#ff0000"><i>, но</i><span style="color:#00ff00"> я б её <i>лучше</i></span><i> покрасил.</i></span>


Мама мыла раму, но я б её лучше покрасил.
 
 
EE Татарин #13.04.2009 14:28  @Balancer#13.04.2009 13:09
+
-
edit
 

Татарин

координатор
★★★★☆
А что будет результатом в этих двух случаях?
\color(#000000)Текст1 \b\i Текст2 \color\b\i Текст3
\b\i Текст3\color(#000000)Текст1 \b\i Текст2 \color

И ты отдаёшь color'y какое-то предпочтение перед "мелкими" тегами?
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  1.0.154.531.0.154.53
RU Balancer #13.04.2009 14:32  @Татарин#13.04.2009 14:28
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> А что будет результатом в этих двух случаях?
Татарин> \color(#000000)Текст1 \b\i Текст2 \color\b\i Текст3

<span style="color:#000000">Текст1 <b><i> Текст2 </i></b></span> Текст3

Текст1 Текст2 Текст3
 


Татарин> \b\i Текст3\color(#000000)Текст1 \b\i Текст2 \color

code html4strict
  1. <b><i> Текст3<span style="color:#000000">Текст1 </span></i></b><span style="color:#000000"> Текст2 </span>


Текст3Текст1 Текст2
 


Татарин> И ты отдаёшь color'y какое-то предпочтение перед "мелкими" тегами?

При парсинге - нет, при чистке лишних тэгов (у меня это делается в два регекспа по готовому результату парсинга) - да.
 
+
-
edit
 

Balancer

администратор
★★★★★
Лови временный тэг [test090413]...[/test090413]

;)

[test090413]
\btest\b \color(#008800)green
[/test090413]
 
US Сергей-4030 #13.04.2009 18:06
+
-
edit
 

Сергей-4030

исключающий третье
★★
админ. бан
Я бы присоединился, но я плохо знаю HTML. Получается, смысл вот в чем: сначала у нас набор тегов, который может "взаимопроникать",

code text
  1. [i]aa[b]bb[/i]cc[/b]


а надо сделать "иерархический" набор:

code text
  1. [i]aa[/i][b][i]bb[/i]cc[/b]


Так? Я правильно понял задачку?
 1.0.154.531.0.154.53
RU Balancer #13.04.2009 19:52  @Сергей-4030#13.04.2009 18:06
+
-
edit
 

Balancer

администратор
★★★★★
Сергей-4030> Так? Я правильно понял задачку?

В валидном HTML не должно быть «пересечений» тэгов. Т.е. конструкции вида
code html4strict
  1. <b>...<i>...</b>...</i>

запрещены (хотя браузерами всеми популярными всё равно как надо отобразятся).

Так что, ты всё правильно понял, нужно перед закрытием внешнего тэга закрыть незаконченный внутренний, а потом вернуть его:

code html4strict
  1. <b>...<i>...</i></b><i>...</i>


Но в случае варианта, типа:

code html4strict
  1. <b><i>...</i></b><i>...</i>


можно поменять начальные тэги местами:

code html4strict
  1. <i><b>...</b>...</i>


Вот в этом и стоит главная трудность сабжевой задачи.

Я решил её не совсем честно :) Но, вроде, на всём, что тестировал, работает. Хотя гарантировать работу в любых случаях я не могу.

Татарин, вон, судя по всему, решил честно, но получил совершенно ужасный N+N*N! :) (если я правильно понимаю факториал квадрата).
 
+
-
edit
 
US Mishka #13.04.2009 19:56  @Сергей-4030#13.04.2009 18:06
+
-
edit
 

Mishka

модератор
★★★
Сергей-4030> Я бы присоединился, но я плохо знаю HTML. Получается, смысл вот в чем: сначала у нас набор тегов, который может "взаимопроникать",
Сергей-4030> Так? Я правильно понял задачку?
Скобочный анализ для разного типа скобок. Есть разные законы типа дистрибутиных. Я бы сделал первый проход по выявлению переключающих тегов, затем преобразовал это дело в скобки, а потом по типу полиномов Жигалкина бы привёл к минимальной форме.
 6.06.0
+
-
edit
 

Mishka

модератор
★★★
Хм, при ближайшем рассмотрении, задача напоминает на покрытие прямой специфическими отрезками с правилами объединения этих отрезков. Вроде, понятно, что самые крупные отрезки надо выносить наружу. Т.е. длина отрезка служит неплохим мерилом оптимизации. Если один отрезок лежит целиком внутри другого, то это тривиальный случай — внешний первым идёт и это минимальное представление. Значит вопрос пересечения. При пересечении двух — пофиг. Для большего количесва — надо построить модельку для 3-х и попытаться обобщить.
 6.06.0
+
-
edit
 

Balancer

администратор
★★★★★
Вот и математики подошли... :)

...

Я решал тупо, конечными автоматами.
 
EE Татарин #14.04.2009 16:15  @Сергей-4030#13.04.2009 18:06
+
-
edit
 

Татарин

координатор
★★★★☆
Сергей-4030> Я бы присоединился, но я плохо знаю HTML. Получается, смысл вот в чем: сначала у нас набор тегов, который может "взаимопроникать",
Сергей-4030> Так? Я правильно понял задачку?
Да, именно так. Собссно, в смысле алгоритма HTML тут не важен; тут важно, чтобы тэги не пересекались, как в любом честном XML.
Три вида тега - болд, италик и цвет (причём цвет должен уметь неограниченую вложенность).

Тэгов в результате итоге должен быть минимум (что достаточно сложно в вычислительном плане и само по себе, а уж при полной/честной обработке цвета... ;)). И, конечно, скорость!
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  1.0.154.531.0.154.53
EE Татарин #14.04.2009 16:29  @Balancer#13.04.2009 19:52
+
-
edit
 

Татарин

координатор
★★★★☆
Balancer> Вот в этом и стоит главная трудность сабжевой задачи.
Да, но не единственная. :)
Если упираться до конца, то <color(A)> 1 </color> <color(B)>2</color> <color(A)> 3 </color> может быть редуцирован до <color(A)> 1 <color(B)>2</color> 3  </color>

Balancer> Татарин, вон, судя по всему, решил честно, но получил совершенно ужасный N+N*N! :) (если я правильно понимаю факториал квадрата).
О, нет, это всё же N*(N!). Что ОЧЕНЬ не сахар, но всё же не до такой степени. :)

И, конечно, это "вычисленная" сложность алгоритма: то есть, сложность, которая получается при подстановке максимально "плохого" для данного алгоритма файла. "Типичная" много меньше - что-то типа полинома 2-3-4-5-6 степени на доступных мне примерах. Кстати, что очень важно при вычислении тестов: N раз повторённый отрывок и уж тем более, N раз прогнанная прога - НЕ эквивалентны по времени выполнения одному "сложному" файлу.
Самый честный способ, что я придумал - генератор случайного потока, в который поочерёдно выкидываются текст и случайные ескейп-последовательности. Конечно, после проверки на простых примерах того факта, что прога вообще работает. :)
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  1.0.154.531.0.154.53
Это сообщение редактировалось 15.04.2009 в 11:49
CA tarasv #15.04.2009 00:42  @Татарин#14.04.2009 16:29
+
-
edit
 

tarasv

опытный

Balancer>> Татарин, вон, судя по всему, решил честно, но получил совершенно ужасный N+N*N! :) (если я правильно понимаю факториал квадрата).
Татарин> О, нет, это всё же N*(N!). Что ОЧЕНЬ не сахар, но всё же не до такой степени. :)

Если факториал то задача NP полная и действительно нужно перебирать все возможные перестановки тэгов? Тоесть понятно что таким способом идеальное решение будет найдено но както это уж больно сурово такой подход выглядит. Может просто ограничиться несколькими проходами оптимизатора и остановиться на не идеальном а просто хорошем решении?
 7.07.0
EE Татарин #15.04.2009 01:20  @tarasv#15.04.2009 00:42
+
-
edit
 

Татарин

координатор
★★★★☆
tarasv> Если факториал то задача NP полная и действительно нужно перебирать все возможные перестановки тэгов? Тоесть понятно что таким способом идеальное решение будет найдено но както это уж больно сурово такой подход выглядит. Может просто ограничиться несколькими проходами оптимизатора и остановиться на не идеальном а просто хорошем решении?
Нет, на практике всё далеко не так плохо, ибо разумная организация данных позволяет резко сократить потребное время на практических задачах (перебирать только те теги, которые реально пересекаются или могут пересекаться), при том, что решение получается наилучшее. Я могу выложить С++ текст - будет понятно, о чём речь.

Вопрос о хорошем решении с точки зрения теории. Мне вот, например, неочевидно, что это NP-полная задача. NP-полный мой алгоритм, но не уверен, что он является наилучшим.
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  1.0.154.531.0.154.53
CA tarasv #15.04.2009 02:10  @Татарин#15.04.2009 01:20
+
-
edit
 

tarasv

опытный

Татарин> Нет, на практике всё далеко не так плохо, ибо разумная организация данных позволяет резко сократить потребное время на практических задачах (перебирать только те теги, которые реально пересекаются или могут пересекаться), при том, что решение получается наилучшее. Я могу выложить С++ текст - будет понятно, о чём речь.
Татарин> Вопрос о хорошем решении с точки зрения теории. Мне вот, например, неочевидно, что это NP-полная задача. NP-полный мой алгоритм, но не уверен, что он является наилучшим.

Даже если она NP полная то N! гарантированно выдает оптимальное решение, N*(N!) это уже явно завышенная оценка. Хотя с начала надо договориться что есть N в этой задаче ;)
Если будет свободный вечер в два-три ближайших дня то хочу сам попробовать что получится. Так что исходники пожалуй не надо, во избежании соблазна ;)
 7.07.0
+
-
edit
 

tarasv

опытный

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

\color(#ff0000)rrrrr\color(#00ff00)rrrrr\colorrrrrr
это
rrrrrrrrrrrrrrr
или
rrrrrrrrrrrrrrr

как правильно?
 7.07.0
+
-
edit
 

Balancer

администратор
★★★★★
tarasv> как правильно?

Выше говорилось, что цвета образуют типа стека. И \color без параметров возвращает предыдущее состояние, а не сбрасывает в исходное. Т.е. у тебя верный второй вариант.
 
US Сергей-4030 #18.04.2009 00:02
+
-
edit
 

Сергей-4030

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

2 Мишка: По-моему, сортировка "отрезков" ничего не дает. Самый длинный отрезок не обязательно самый оптимальный. :(
 1.0.154.531.0.154.53

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru