Форумы » Наука и техника » Компьютерный » Программирование » Поспорим о быстродействии, господа суровые программисты?
[image]

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

Задача на хороший алгоритм. Из жизни.
Теги:программирование, компьютеры, техника
 
Новый опрос Новый фотосет Новая тема Написать сообщение в тему
1 2
EE Татарин #13.04.2009 07:58
+
-
edit
 

Татарин

координатор
★★★★★
техника компьютеры программирование
Формулировка. Имеется текст в формате вида
Мама \bмыла\i раму\color(#ff0000)\b, но\color=(#00ff00)\i я б её \iлучше\color покрасил.
который представляет текст
Мама мыла раму, но я б её лучше покрасил.

Нужно сделать из него валидный HTML минимального размера (тэгов должно быть минимум).
Файлы могут быть большими. И, случается, даже БОЛЬШИМИ.

Пока мой наилучший результат o(n)=3n+n*n!
Кто может лучше? :)
   1.0.154.531.0.154.53
Это сообщение редактировалось 13.04.2009 в 08:38
US Сергей-4030 #13.04.2009 08:33  @Татарин#13.04.2009 07:58
+
-
edit
 

Сергей-4030

исключающий третье
★★
Татарин> Нужно сделать из него валидный ХМТМ минимального размера (тэгов должно быть минимум).

Что такое XMTM?
   1.0.154.531.0.154.53
EE Татарин #13.04.2009 08:38  @Сергей-4030#13.04.2009 08:33
+
-
edit
 

Татарин

координатор
★★★★★
Сергей-4030> Что такое XMTM?
Виноват. HTML. Поправил.
   1.0.154.531.0.154.53
RU Balancer #13.04.2009 08:48  @Татарин#13.04.2009 07:58
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> Нужно сделать из него валидный HTML

А как быть с некорректными входными данными, типа
\bтест \iтэгов\b\i ?

(вообще же, формат крайне неудобный ;))
   
EE Татарин #13.04.2009 09:11  @Balancer#13.04.2009 08:48
+
-
edit
 

Татарин

координатор
★★★★★
Татарин>> Нужно сделать из него валидный HTML
Balancer> А как быть с некорректными входными данными, типа
Balancer> \bтест \iтэгов\b\i ?
Суть вопроса в том, что это корректные входные данные. :)
Иначе в чём бы состояла радость алгоритмописания? :)

П.С. Обрати внимание, что преобразование - неоднозначно. Существует множество вариантов генерации конечного XML/HTML, из них должен быть выбран минимальный по размеру.
   1.0.154.531.0.154.53
RU Balancer #13.04.2009 09:26  @Татарин#13.04.2009 09:11
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> Суть вопроса в том, что это корректные входные данные. :)

Тогда задача недостаточно строго описана :)

\bслово1 \iслово2 \bслово3 \iслово4 можно трактовать как:
1. слово1 слово2 слово3 слово4
2. слово1 слово2 слово3 слово4
3. слово1 слово2 слово3 слово4

как нужно? :)
   
EE Татарин #13.04.2009 09:32
+
-
edit
 

Татарин

координатор
★★★★★
Извиняюсь повторно. Мне показалось, что пример говорит сам за себя.
Первое упоминание \i - включает курсив, следующее - выключает. Первое упоминание \b - включает жирный, второе - выключает. Цвет задаётся ескейп-последовательностью \color=(#RGB), \color - возвращает цвет к предыдущему.
Это не теги, а последовательности, если угодно - управляющие слова. Они даже завершаться ("ходить парами") никоим образом не обязаны (хотя это уже совсем несущественные мелочи).

Строго говоря, этих последовательностей больше (и вообще всё немного сложнее и насыщеннее подробностями), просто в алгоритм дальнейшее перечисление деталей ничего существенного уже не вносит, ИМХО.

Я ж не прошу сделать за меня конкретную работу (которая, к тому же, уже сделана и сдана), :) а просто предлагаю повыпендриваться/посоревноваться своей изобретательностью. Задача показалась достаточно забавным поводом.

Здесь, ИМХО, есть над чем подумать (особенно, учитывая одновременные требования по скорости работы и качеству результата). :) Если это не так, разубедите меня. :)
   1.0.154.531.0.154.53
Это сообщение редактировалось 13.04.2009 в 09:40
US Mishka #13.04.2009 09:43  @Татарин#13.04.2009 07:58
+
-
edit
 

Mishka

модератор
★★★
Татарин> Формулировка. Имеется текст в формате вида
Татарин> Мама \bмыла\i раму\color(#ff0000)\b, но\color=(#00ff00)\i я б её \iлучше\color покрасил.
Татарин> который представляет текст
Татарин> Мама мыла раму, но я б её лучше покрасил.

А почемы слово "раму" красного цвета? :)
   3.0.53.0.5
RU Balancer #13.04.2009 09:46  @Татарин#13.04.2009 09:32
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> Первое упоминание \i - включает курсив, следующее - выключает.

Понятно.

Кстати, в этом синтаксисе набор тэгов нерасширяемый без влезания в код парсера. Нет признака конца тэга. И поэтому тэг \b не отличить от \bb в фрагменте \bbold :)
   
EE Татарин #13.04.2009 09:54  @Mishka#13.04.2009 09:43
+
-
edit
 

Татарин

координатор
★★★★★
Татарин>> Мама мыла раму, но я б её лучше покрасил.
Mishka> А почемы слово "раму" красного цвета? :)
Думаю, по примерно той же причине, по которой у тебя "почему" через "ы" пишется. :)

Хотя, конечно, подмывает сказать, что в этом и есть главная особенность формата. :D
   1.0.154.531.0.154.53
EE Татарин #13.04.2009 09:55  @Balancer#13.04.2009 09:46
+
-
edit
 

Татарин

координатор
★★★★★
Balancer> Кстати, в этом синтаксисе набор тэгов нерасширяемый без влезания в код парсера. Нет признака конца тэга. И поэтому тэг \b не отличить от \bb в фрагменте \bbold :)
Ну, задача-то не просто так же встала. Дурацкий формат, что уж тут...
   1.0.154.531.0.154.53
RU hcube #13.04.2009 10:58
+
-
edit
 

hcube

старожил
★★
Можно еще CSS попробовать использовать, задать им некий набор цветов по умолчанию. Да и [i class=1] компактнее чем [i]<color=#112233>.

А вообще, если речь пошла о минимальном размере, то есть такая штука как GZIP ;-)
   6.06.0
RU Balancer #13.04.2009 10:59
+
-
edit
 

Balancer

администратор
★★★★★
На PHP у «неколенного» парсера на строке вида
000 \b\i\color(#ff0000)rrrrr \color(#00ff00) gggg\bgggg\color(#0000ff)bbbbb\colorggggg\colorrrrr\i\color, повторённой n раз столько времени выходит:

$ php markup.php
1: 0,00134897232056
10: 0,0121030807495
100: 0,445528030396
500: 11,2481658459

Какая это O-зависимость выходит? :)

...

Походу, это N2.
   
RU Balancer #13.04.2009 11:04
+
-
edit
 

Balancer

администратор
★★★★★
$ php markup.php
1: 0,00127291679382
10: 0,0151479244232
100: 0,465785980225
500: 11,6852560043
1000: 51,3077819347

Да, видимо, N2 с небольшим :)
   
EE Татарин #13.04.2009 11:06  @hcube#13.04.2009 10:58
+
-
edit
 

Татарин

координатор
★★★★★
hcube> Можно еще CSS попробовать использовать, задать им некий набор цветов по умолчанию. Да и [i class=1] компактнее чем [i]<color=#112233>.
Нет, css - вне игры. Задача не практическая.
   1.0.154.531.0.154.53
EE Татарин #13.04.2009 11:08  @Balancer#13.04.2009 10:59
+
-
edit
 

Татарин

координатор
★★★★★
Balancer> На PHP у «неколенного» парсера на строке вида
Balancer> 000 \b\i\color(#ff0000)rrrrr \color(#00ff00) gggg\bgggg\color(#0000ff)bbbbb\colorggggg\colorrrrr\i\color, повторённой n раз столько времени выходит:
Результат ещё покажь. Там точно минимум тэгов? :)
   1.0.154.531.0.154.53
RU Balancer #13.04.2009 11:10  @Татарин#13.04.2009 11:08
+
-
edit
 

Balancer

администратор
★★★★★
Balancer>> 000 \b\i\color(#ff0000)rrrrr \color(#00ff00) gggg\bgggg\color(#0000ff)bbbbb\colorggggg\colorrrrr\i\color, повторённой n раз столько времени выходит:
Татарин> Результат ещё покажь. Там точно минимум тэгов? :)


000 <b><i><span color="#ff0000">rrrrr <span color="#00ff00"> gggg</span></span></i></b><i><span color="#ff0000">rrrr</span></i>


Оптимизация по тегам примитивная, но, вроде, лишних нет :)
   
RU Balancer #13.04.2009 11:11
+
-
edit
 

Balancer

администратор
★★★★★
Упс. Вижу ошибку. На старых тестах всё ок было :) Пошёл чинить...

Это оптимизатор тэгов слишком жёсткий получился ;)
   
RU Balancer #13.04.2009 11:15
+
-
edit
 

Balancer

администратор
★★★★★
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><span color="#ff0000"></span>

Тайминг стал похуже:

$ php markup.php
1: 0,00125098228455
10: 0,0170760154724
100: 0,482527017593
500: 14,3426609039
1000: 66,6711261272
   
RU Balancer #13.04.2009 11:18
+
-
edit
 

Balancer

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

$ php markup.php
1: 0,0151560306549
10: 0,00933384895325
100: 0,0901589393616
500: 0,45777797699
1000: 0,906383037567

:)
   
EE Татарин #13.04.2009 11:20  @Balancer#13.04.2009 11:15
+
-
edit
 

Татарин

координатор
★★★★★
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><span color="#ff0000"></span>
Ошибка: второй [i] не нужен. Ты закрываешь курсив и тут же открываешь, не имея ни буквы "прямого" текста. :)
Кстати, последний color - тоже совершенно непонятно к чему: он пустой вообще.

Balancer> Тайминг стал похуже:
:)
Есть предложение тогда сразу давать тест-файл и количество тегов.
Количество тегов я смогу втупую сравнить с тем, что получается у меня. Если у тебя больше - значит, у тебя ошибка. Ну, если меньше, то ошибка, конечно у меня. :)
   1.0.154.531.0.154.53
Это сообщение редактировалось 13.04.2009 в 11:26
EE Татарин #13.04.2009 11:23  @Balancer#13.04.2009 11:18
+
-
edit
 

Татарин

координатор
★★★★★
Balancer> Кстати, если тэги не мультистрочные, то можно по строкам бить.
Почему не "мультистрочные"? Или я тебя неверно понял? Что это такое - "мультистрочный тег"?
   1.0.154.531.0.154.53
RU Balancer #13.04.2009 11:25  @Татарин#13.04.2009 11:20
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> Ошибка: второй [i] не нужен.

i нужен :)

Татарин> Ты закрываешь курсив и тут же открываешь, не имея ни буквы "прямого" текста. :)

Там текст дальше идёт. Так что, рано или поздно, i открыть надо будет. Так какая разница, где?

А вот ошибка - в конце опять span/span вылезли. Сейчас разберусь :)

Татарин> Есть предложение тогда сразу давать тест-файл и количество тегов.

Ну, я дал строку. Тестирую так:

<?php

$s = "000 \b\i\color(#ff0000)rrrrr \color(#00ff00) gggg\bgggg\color(#0000ff)bbbbb\colorggggg\colorrrrr\i\color\n";
foreach(array(1,10,100,500,1000) as $size)
{
    $start = microtime(true);
    $text = str_repeat($s, $size);
    $x = markup($text);

    echo "$size: ".(microtime(true) - $start)."\n";
//  echo $x;
}
   
RU Balancer #13.04.2009 11:26  @Татарин#13.04.2009 11:23
+
-
edit
 

Balancer

администратор
★★★★★
Татарин> Почему не "мультистрочные"? Или я тебя неверно понял? Что это такое - "мультистрочный тег"?

Который на несколько строк разбит. Т.е.:


\bbold
bold
\bnormal


Если так нельзя - то сильно быстрее ;)
   
EE Татарин #13.04.2009 11:31  @Balancer#13.04.2009 11:25
+
-
edit
 

Татарин

координатор
★★★★★
Balancer> Там текст дальше идёт. Так что, рано или поздно, i открыть надо будет. Так какая разница, где?
Блин, ты всё ещё не врубился, в чём тут главная радость. :)

Смотри, ты же можешь в первом его включении вынести его за болд, поставить первым. Тогда отпадёт необходимость выключать его и включать во второй раз. Как-то так:
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>
Форматирование осталось прежним, а одним тегом стало меньше. Согласен? :)
   1.0.154.531.0.154.53
1 2

в начало страницы | новое
Форумы » Наука и техника » Компьютерный » Программирование » Поспорим о быстродействии, господа суровые программисты?
Copyright © Balancer 1997..2025
Создано 13.04.2009
Связь с владельцами и администрацией сайта: anonisimov@gmail.com, rwasp1957@yandex.ru и admin@balancer.ru.
 
Поиск
Настройки






Статистика
Рейтинг@Mail.ru
АвиаТОП
 
Яндекс.Метрика
website counter
 
free counters