Язык
Контакты
GitHub
Поддержка
Регистрация
Войти
Логин: Пароль: Запомнить:
Пользователи
Последние сообщения
Ответить
1

Конечные автоматы для увеличения производительности

Drunya

  • Man of God
  • Админ
  • 3527
  • Репутация:110 
  • Предупреждения: 0 
  • Регистрация:
    30 Ноя -0001
#1
И так. Ни для кого не секрет, что наши бб коды хромают со вложенностью. Так как на чистых регулярках реализовать вложенность работающую в 100% случаев нереально, а если и добиться этого кучей циклов и прочего, то выйдет как минимум 2 регулярки на один бб код плюс один запуск preg_match для каждого уровня. Не комильфо. По этому я решил освоить конечные автоматы, так как был наслышан о их производительности.

Но вот не задача. Накатал простой автомат для обработки тегов [b] с любой вложенностью и он показал просто кошмарную производительность, хотя я максимально его оптимизировал. В чем дело? Может я конечно что-то не так сделал. Вопрос конечно довольно специфичен, но может кто то что-то знает или сможет нарыть)

Вот мой автомат
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 64 
 65 
 66 
 67 
 68 
 69 
 70 
<?php // Логическое представление
$rules = array(
    
// normal state - search open tag
    // 1 - open tag
    
=> array(1),
    
// open tag is finded, search close tag or open
    // 1 - close tag
    // 2 - open tag
    
=> array(12),
);

$str 'входящая строка';

    
$lenght mb_strlen($str);
    
$currpos 0;
    
$currstate 1;
    
$out '';

    
$memory = array();
    
$levelmemory = array();


    while (
$currpos $lenght) {
        switch (
$currstate) {
            case 
1:
                if (
mb_substr($str$currpos3) === '[b]') {
                    
$currstate 2;
                    
$levelmemory[] = 1;
                    
$currpos += 3;
                    
$memory[] = '';
                } else {
                    if (
false !== ($posopen strpos($str'['$currpos))) {
                        
$out .= mb_substr($str$currpos, ($posopen $currpos));
                        
$currpos += ($posopen $currpos);
                    } else {
                        
$out .= mb_substr($str$currposmb_strlen($str));
                        
$currpos += mb_strlen($str) - 1;
                    }
                }
                break;
            case 
2:
                if (
mb_substr($str$currpos4) === '[/b]') {
                    
$currstate array_pop($levelmemory);
                    
$currpos += 4;
                    
$preout '<b>' array_pop($memory) . '</b>';
                    if (
$currstate === 2) {
                        
$memory[count($memory) - 1] .= $preout;
                    } else {
                        
$out .= $preout;
                    }
                } else if (
mb_substr($str$currpos3) === '[b]') {
                    
$currpos += 3;
                    
$memory[] = '';
                    
$levelmemory[] = 2;
                } else {
                    if (
false !== ($posopen strpos($str'['$currpos))) {
                        
$tmp array_pop($memory) . mb_substr($str$currpos, ($posopen $currpos));
                        
$memory[] = $tmp;
                        
$currpos += ($posopen $currpos);
                    } else {
                        
$tmp array_pop($memory) . mb_substr($str$currposmb_strlen($str));
                        
$memory[] = $tmp;
                        
$currpos += mb_strlen($str) - 1;
                    }

                }
                break;
        }
    }
    
//pr(h($out));?>

На сто итераций тестовой строки с 3 уровнями вложенности ушло 0.0556979179382

На регулярках как бы я не крутил выходит быстрее. :pardon:

Отредактировано автором 2 Июл 2011
Я горжусь тем, что создал бесплатную CMS - AtomX. И люблю нашу команду)

skad0

  • Атом-мозг
  • Юзер
  • 841
  • Репутация:10 
  • Предупреждения: 0 
  • Регистрация:
    2 Окт 2010
#2
http://ua2.php.net/manual/en/ref.bbcode.php

Drunya

  • Man of God
  • Админ
  • 3527
  • Репутация:110 
  • Предупреждения: 0 
  • Регистрация:
    30 Ноя -0001
#3
Это по каким то причинам мы уже давно отсеяли)

Я горжусь тем, что создал бесплатную CMS - AtomX. И люблю нашу команду)

skad0

  • Атом-мозг
  • Юзер
  • 841
  • Репутация:10 
  • Предупреждения: 0 
  • Регистрация:
    2 Окт 2010
#4
Цитата
Это по каким то причинам мы уже давно отсеяли)

Это работает и работает отлично. По скорости не уступает регуляркам, по юзабельности твоему методу.

Drunya

  • Man of God
  • Админ
  • 3527
  • Репутация:110 
  • Предупреждения: 0 
  • Регистрация:
    30 Ноя -0001
#5
skad0 пишет:
Это работает и работает отлично. По скорости не уступает регуляркам, по юзабельности твоему методу.
Я же говорю, что му думали заюзать этот стандартный метод, но по каким то причинам отказались. Хотя на досуге надо будет потестить, посмотреть.

Я горжусь тем, что создал бесплатную CMS - AtomX. И люблю нашу команду)

skad0

  • Атом-мозг
  • Юзер
  • 841
  • Репутация:10 
  • Предупреждения: 0 
  • Регистрация:
    2 Окт 2010
#6
Надо записывать)

Добавлено2011.07.22 16-26

 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
<?php function bb_parse($string) {
        
$tags 'b|u|s|i|size|color|center|quote|url|img';
        while (
preg_match_all('`\[('.$tags.')=?(.*?)\](.+?)\[/\1\]`'$string$matches)) foreach ($matches[0] as $key => $match) {
            list(
$tag$param$innertext) = array($matches[1][$key], $matches[2][$key], $matches[3][$key]);
            switch (
$tag) {
                case 
'b'$replacement "<strong>$innertext</strong>"; break;
                case 
'i'$replacement "<em>$innertext</em>"; break;
                case 
'u'$replacement "<u>$innertext</u>"; break;
                case 
's'$replacement "<strike>$innertext</strike>"; break;
                case 
'size'$replacement "<span style=\"font-size: $param;\">$innertext</span>"; break;
                case 
'color'$replacement "<span style=\"color: $param;\">$innertext</span>"; break;
                case 
'center'$replacement "<center>$innertext</center>"; break;
                case 
'quote':  $replacement "<blockquote>$innertext</blockquote>";  break;
                case 
'url'$replacement '<a href="' . ($param$param $innertext) . "\">$innertext</a>"; break;
                case 
'img':
                    list(
$width$height) = preg_split('`[Xx]`'$param);
                    
$replacement "<img src=\"$innertext\" " . (is_numeric($width)? "width=\"$width\" " '') . (is_numeric($height)? "height=\"$height\" " '') . '/>';
                break;
                case 
'video':
                    
$videourl parse_url($innertext);
                    
parse_str($videourl['query'], $videoquery);
                    if (
strpos($videourl['host'], 'youtube.com') !== FALSE$replacement '<embed src="http://www.youtube.com/v/' $videoquery['v'] . '" type="application/x-shockwave-flash" width="425" height="344"></embed>';
                    if (
strpos($videourl['host'], 'google.com') !== FALSE$replacement '<embed src="http://video.google.com/googleplayer.swf?docid=' $videoquery['docid'] . '" width="400" height="326" type="application/x-shockwave-flash"></embed>';
                break;
            }
            
$string str_replace($match$replacement$string);
        }
        return 
$string;
    }
?>
[/php]

Drunya

  • Man of God
  • Админ
  • 3527
  • Репутация:110 
  • Предупреждения: 0 
  • Регистрация:
    30 Ноя -0001
#7
То есть ты хочешь сказать что этот алгоритм корректно отрабатывает вложенность и не парные теги(зфбыл закрыть и т.д.)?

Хотя не парный теги еще фигня. Не закрыл, твои проблемы. А вот вложенность нужна. А так как этот алгоритм использует регулярку, то и о вложенности речи быть не может. По крайней мере правильной. Или может?

Я горжусь тем, что создал бесплатную CMS - AtomX. И люблю нашу команду)

skad0

  • Атом-мозг
  • Юзер
  • 841
  • Репутация:10 
  • Предупреждения: 0 
  • Регистрация:
    2 Окт 2010
#8
Цитата

Хотя не парный теги еще фигня. Не закрыл, твои проблемы. А вот вложенность нужна. А так как этот алгоритм использует регулярку, то и о вложенности речи быть не может. По крайней мере правильной. Или может?

Из того, что я уже потестил, все пашет. Не закрытые - тупо не пашут.

Отредактировано автором 22 Июл 2011
1
Сейчас online: 42. Зарегистрированных: 2. Гостей: 40.