-
/1358631-programming_oop_wallpaper_red_by_hexeno.png)
Поспорим о быстродействии, господа суровые программисты?
Задача на хороший алгоритм. Из жизни.Теги:
Татарин
Balancer> Который на несколько строк разбит. Т.е.:
Balancer> Если так нельзя - то сильно быстрее
Вообще, считай, что переводов строки нет, для простоты и чистоты задачи.
Balancer> Если так нельзя - то сильно быстрее
Вообще, считай, что переводов строки нет, для простоты и чистоты задачи.
...А неубитые медведи делили чьи-то шкуры с шумом.
Боюсь, мы поздно осознали, к чему всё это приведёт.
инфо
инструменты
Balancer
Татарин> Смотри, ты же можешь в первом его включении вынести его за болд, поставить первым.
А, понял. Тогда - да, задача сильно усложняется. А так, после исправления ошибки убирания пустых тэгов:
$ php markup.0.php
1: 0,00144195556641
10: 0,0147280693054
100: 0,397891044617
500: 7,74917697906
1000: 29,6116909981
А вот с пермутациями тэгов - да, в голову ничего быстрого не приходит.
А, понял. Тогда - да, задача сильно усложняется. А так, после исправления ошибки убирания пустых тэгов:
$ php markup.0.php
1: 0,00144195556641
10: 0,0147280693054
100: 0,397891044617
500: 7,74917697906
1000: 29,6116909981
code text
- 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>
А вот с пермутациями тэгов - да, в голову ничего быстрого не приходит.
$ 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.
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.
$ php markup.php
1: 0,00167107582092
10: 0,0124468803406
100: 0,384516000748
500: 7,91936206818
1000: 30,9722850323
Вроде, окончательный вариант в первом приближении
1: 0,00167107582092
10: 0,0124468803406
100: 0,384516000748
500: 7,91936206818
1000: 30,9722850323
code html4strict
Вроде, окончательный вариант в первом приближении
Татарин> Мама \bмыла\i раму\color(#ff0000)\b, но\color=(#00ff00)
color(..), или color=(..), или оба?
color(..), или color=(..), или оба?
$ php markup.php
1: 0,00154280662537
10: 0,0104448795319
100: 0,296799898148
500: 6,37055897713
1000: 24,2174150944
превращается в
1: 0,00154280662537
10: 0,0104448795319
100: 0,296799898148
500: 6,37055897713
1000: 24,2174150944
code text
- Мама \bмыла\i раму\color(#ff0000)\b, но\color(#00ff00)\i я б её \iлучше\color покрасил.
превращается в
code html4strict
Мама мыла раму, но я б её лучше покрасил.
А что будет результатом в этих двух случаях?
\color(#000000)Текст1 \b\i Текст2 \color\b\i Текст3
\b\i Текст3\color(#000000)Текст1 \b\i Текст2 \color
И ты отдаёшь color'y какое-то предпочтение перед "мелкими" тегами?
\color(#000000)Текст1 \b\i Текст2 \color\b\i Текст3
\b\i Текст3\color(#000000)Текст1 \b\i Текст2 \color
И ты отдаёшь color'y какое-то предпочтение перед "мелкими" тегами?
...А неубитые медведи делили чьи-то шкуры с шумом.
Боюсь, мы поздно осознали, к чему всё это приведёт.
Татарин> А что будет результатом в этих двух случаях?
Татарин> \color(#000000)Текст1 \b\i Текст2 \color\b\i Текст3
<span style="color:#000000">Текст1 <b><i> Текст2 </i></b></span> Текст3
Татарин> \b\i Текст3\color(#000000)Текст1 \b\i Текст2 \color
Татарин> И ты отдаёшь color'y какое-то предпочтение перед "мелкими" тегами?
При парсинге - нет, при чистке лишних тэгов (у меня это делается в два регекспа по готовому результату парсинга) - да.
Татарин> \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
Текст3Текст1 Текст2
Татарин> И ты отдаёшь color'y какое-то предпочтение перед "мелкими" тегами?
При парсинге - нет, при чистке лишних тэгов (у меня это делается в два регекспа по готовому результату парсинга) - да.
Лови временный тэг [test090413]...[/test090413]
[test090413]
\btest\b \color(#008800)green
[/test090413]
[test090413]
\btest\b \color(#008800)green
[/test090413]
Сергей-4030
Я бы присоединился, но я плохо знаю HTML. Получается, смысл вот в чем: сначала у нас набор тегов, который может "взаимопроникать",
а надо сделать "иерархический" набор:
Так? Я правильно понял задачку?
code text
- [i]aa[b]bb[/i]cc[/b]
а надо сделать "иерархический" набор:
code text
- [i]aa[/i][b][i]bb[/i]cc[/b]
Так? Я правильно понял задачку?
Сергей-4030> Так? Я правильно понял задачку?
В валидном HTML не должно быть «пересечений» тэгов. Т.е. конструкции вида
запрещены (хотя браузерами всеми популярными всё равно как надо отобразятся).
Так что, ты всё правильно понял, нужно перед закрытием внешнего тэга закрыть незаконченный внутренний, а потом вернуть его:
Но в случае варианта, типа:
можно поменять начальные тэги местами:
Вот в этом и стоит главная трудность сабжевой задачи.
Я решил её не совсем честно Но, вроде, на всём, что тестировал, работает. Хотя гарантировать работу в любых случаях я не могу.
Татарин, вон, судя по всему, решил честно, но получил совершенно ужасный N+N*N! (если я правильно понимаю факториал квадрата).
В валидном HTML не должно быть «пересечений» тэгов. Т.е. конструкции вида
code html4strict
запрещены (хотя браузерами всеми популярными всё равно как надо отобразятся).
Так что, ты всё правильно понял, нужно перед закрытием внешнего тэга закрыть незаконченный внутренний, а потом вернуть его:
code html4strict
Но в случае варианта, типа:
code html4strict
можно поменять начальные тэги местами:
code html4strict
Вот в этом и стоит главная трудность сабжевой задачи.
Я решил её не совсем честно
Но, вроде, на всём, что тестировал, работает. Хотя гарантировать работу в любых случаях я не могу.Татарин, вон, судя по всему, решил честно, но получил совершенно ужасный N+N*N!
(если я правильно понимаю факториал квадрата).
Продублировал задачу в Форум - Talks - Конкурс! Программисты, кто тут задачу хотел? :)
Сергей-4030> Я бы присоединился, но я плохо знаю HTML. Получается, смысл вот в чем: сначала у нас набор тегов, который может "взаимопроникать",
Сергей-4030> Так? Я правильно понял задачку?
Скобочный анализ для разного типа скобок. Есть разные законы типа дистрибутиных. Я бы сделал первый проход по выявлению переключающих тегов, затем преобразовал это дело в скобки, а потом по типу полиномов Жигалкина бы привёл к минимальной форме.
Сергей-4030> Так? Я правильно понял задачку?
Скобочный анализ для разного типа скобок. Есть разные законы типа дистрибутиных. Я бы сделал первый проход по выявлению переключающих тегов, затем преобразовал это дело в скобки, а потом по типу полиномов Жигалкина бы привёл к минимальной форме.
Хм, при ближайшем рассмотрении, задача напоминает на покрытие прямой специфическими отрезками с правилами объединения этих отрезков. Вроде, понятно, что самые крупные отрезки надо выносить наружу. Т.е. длина отрезка служит неплохим мерилом оптимизации. Если один отрезок лежит целиком внутри другого, то это тривиальный случай — внешний первым идёт и это минимальное представление. Значит вопрос пересечения. При пересечении двух — пофиг. Для большего количесва — надо построить модельку для 3-х и попытаться обобщить.
Вот и математики подошли...
...
Я решал тупо, конечными автоматами.
...
Я решал тупо, конечными автоматами.
Сергей-4030> Я бы присоединился, но я плохо знаю HTML. Получается, смысл вот в чем: сначала у нас набор тегов, который может "взаимопроникать",
Сергей-4030> Так? Я правильно понял задачку?
Да, именно так. Собссно, в смысле алгоритма HTML тут не важен; тут важно, чтобы тэги не пересекались, как в любом честном XML.
Три вида тега - болд, италик и цвет (причём цвет должен уметь неограниченую вложенность).
Тэгов в результате итоге должен быть минимум (что достаточно сложно в вычислительном плане и само по себе, а уж при полной/честной обработке цвета...). И, конечно, скорость!
Сергей-4030> Так? Я правильно понял задачку?
Да, именно так. Собссно, в смысле алгоритма HTML тут не важен; тут важно, чтобы тэги не пересекались, как в любом честном XML.
Три вида тега - болд, италик и цвет (причём цвет должен уметь неограниченую вложенность).
Тэгов в результате итоге должен быть минимум (что достаточно сложно в вычислительном плане и само по себе, а уж при полной/честной обработке цвета...
). И, конечно, скорость!
...А неубитые медведи делили чьи-то шкуры с шумом.
Боюсь, мы поздно осознали, к чему всё это приведёт.
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 раз прогнанная прога - НЕ эквивалентны по времени выполнения одному "сложному" файлу.
Самый честный способ, что я придумал - генератор случайного потока, в который поочерёдно выкидываются текст и случайные ескейп-последовательности. Конечно, после проверки на простых примерах того факта, что прога вообще работает.
Да, но не единственная.
Если упираться до конца, то <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 раз прогнанная прога - НЕ эквивалентны по времени выполнения одному "сложному" файлу.
Самый честный способ, что я придумал - генератор случайного потока, в который поочерёдно выкидываются текст и случайные ескейп-последовательности. Конечно, после проверки на простых примерах того факта, что прога вообще работает.
...А неубитые медведи делили чьи-то шкуры с шумом.
Боюсь, мы поздно осознали, к чему всё это приведёт.
Это сообщение редактировалось 15.04.2009 в 11:49
tarasv
Balancer>> Татарин, вон, судя по всему, решил честно, но получил совершенно ужасный N+N*N! (если я правильно понимаю факториал квадрата).
Татарин> О, нет, это всё же N*(N!). Что ОЧЕНЬ не сахар, но всё же не до такой степени.
Если факториал то задача NP полная и действительно нужно перебирать все возможные перестановки тэгов? Тоесть понятно что таким способом идеальное решение будет найдено но както это уж больно сурово такой подход выглядит. Может просто ограничиться несколькими проходами оптимизатора и остановиться на не идеальном а просто хорошем решении?
(если я правильно понимаю факториал квадрата).Татарин> О, нет, это всё же N*(N!). Что ОЧЕНЬ не сахар, но всё же не до такой степени.
Если факториал то задача NP полная и действительно нужно перебирать все возможные перестановки тэгов? Тоесть понятно что таким способом идеальное решение будет найдено но както это уж больно сурово такой подход выглядит. Может просто ограничиться несколькими проходами оптимизатора и остановиться на не идеальном а просто хорошем решении?
tarasv> Если факториал то задача NP полная и действительно нужно перебирать все возможные перестановки тэгов? Тоесть понятно что таким способом идеальное решение будет найдено но както это уж больно сурово такой подход выглядит. Может просто ограничиться несколькими проходами оптимизатора и остановиться на не идеальном а просто хорошем решении?
Нет, на практике всё далеко не так плохо, ибо разумная организация данных позволяет резко сократить потребное время на практических задачах (перебирать только те теги, которые реально пересекаются или могут пересекаться), при том, что решение получается наилучшее. Я могу выложить С++ текст - будет понятно, о чём речь.
Вопрос о хорошем решении с точки зрения теории. Мне вот, например, неочевидно, что это NP-полная задача. NP-полный мой алгоритм, но не уверен, что он является наилучшим.
Нет, на практике всё далеко не так плохо, ибо разумная организация данных позволяет резко сократить потребное время на практических задачах (перебирать только те теги, которые реально пересекаются или могут пересекаться), при том, что решение получается наилучшее. Я могу выложить С++ текст - будет понятно, о чём речь.
Вопрос о хорошем решении с точки зрения теории. Мне вот, например, неочевидно, что это NP-полная задача. NP-полный мой алгоритм, но не уверен, что он является наилучшим.
...А неубитые медведи делили чьи-то шкуры с шумом.
Боюсь, мы поздно осознали, к чему всё это приведёт.
Татарин> Нет, на практике всё далеко не так плохо, ибо разумная организация данных позволяет резко сократить потребное время на практических задачах (перебирать только те теги, которые реально пересекаются или могут пересекаться), при том, что решение получается наилучшее. Я могу выложить С++ текст - будет понятно, о чём речь.
Татарин> Вопрос о хорошем решении с точки зрения теории. Мне вот, например, неочевидно, что это NP-полная задача. NP-полный мой алгоритм, но не уверен, что он является наилучшим.
Даже если она NP полная то N! гарантированно выдает оптимальное решение, N*(N!) это уже явно завышенная оценка. Хотя с начала надо договориться что есть N в этой задаче
Если будет свободный вечер в два-три ближайших дня то хочу сам попробовать что получится. Так что исходники пожалуй не надо, во избежании соблазна
Татарин> Вопрос о хорошем решении с точки зрения теории. Мне вот, например, неочевидно, что это NP-полная задача. NP-полный мой алгоритм, но не уверен, что он является наилучшим.
Даже если она NP полная то N! гарантированно выдает оптимальное решение, N*(N!) это уже явно завышенная оценка. Хотя с начала надо договориться что есть N в этой задаче
Если будет свободный вечер в два-три ближайших дня то хочу сам попробовать что получится. Так что исходники пожалуй не надо, во избежании соблазна
Вопрос возник по постановке задачи - тэги цвета во многих примерах неуравновешенные, соответсвенно может быть как минимум две интерпретации
\color(#ff0000)rrrrr\color(#00ff00)rrrrr\colorrrrrr
это
rrrrrrrrrrrrrrr
или
rrrrrrrrrrrrrrr
как правильно?
\color(#ff0000)rrrrr\color(#00ff00)rrrrr\colorrrrrr
это
rrrrrrrrrrrrrrr
или
rrrrrrrrrrrrrrr
как правильно?
tarasv> как правильно?
Выше говорилось, что цвета образуют типа стека. И \color без параметров возвращает предыдущее состояние, а не сбрасывает в исходное. Т.е. у тебя верный второй вариант.
Выше говорилось, что цвета образуют типа стека. И \color без параметров возвращает предыдущее состояние, а не сбрасывает в исходное. Т.е. у тебя верный второй вариант.
Пока не забанили, выскажусь. ИМХО, задача явно NP-полная, лично мне в голову ничего другого не приходит. Поэтому решение, которое я реализовал чисто переборное.
2 Мишка: По-моему, сортировка "отрезков" ничего не дает. Самый длинный отрезок не обязательно самый оптимальный.
2 Мишка: По-моему, сортировка "отрезков" ничего не дает. Самый длинный отрезок не обязательно самый оптимальный.
Copyright © Balancer 1997..2018
Создано 13.04.2009
Связь с владельцами и администрацией сайта: anonisimov@gmail.com, rwasp1957@yandex.ru и admin@balancer.ru.
Создано 13.04.2009
Связь с владельцами и администрацией сайта: anonisimov@gmail.com, rwasp1957@yandex.ru и admin@balancer.ru.
- Поиск
- Настройки
-
- Персональное
-
Здравствуйте, гость!
Гостевой функционал сайта ограничен. Для полноценной работы зарегистрируйтесь, пожалуйста.
- Тема
- RPG (самоуправление)
- Твиттер сайта Твиты пользователя @AirbaseRu
- Статистика
-
