PHP и UTF-8: пятый этап

Итак, пятый этап. Точнее на этап, он, пожалуй, не тянет, но после этапов 4,5 и 4,6 мне хочется целых чисел.

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

В самом деле, если простое взятие символа по индексу в строке с фиксированным размером символа имеет сложность O(1), то в UTF-8 строке эта сложность возрастает до O(n). Соответственно, когда я прохожу циклом по строке с фиксированным размером символа эта сложность — O(n), а текущие циклы в моих функциях проходят строку UTF-8 за O(n²). Особенно это будет заметно в функции rtrim.

Я написал небольшие тесты. Замерял три прохода по тексту объёмом 187,5КБ. Проход по строке с однобайтной кодировкой — 0,2 секунды, по строке UTF-8 — 160 секунд. Забегая вперёд, скажу, что проход той же строки (UTF-8) итератором занимает 4,3 секунды, результат хуже, чем у встроенных функций, но в 37 раз лучше (на этих данных), чем проход прежним алгоритмом.

Вообще-то в PHP5 появилось очень много вещей, которые никто не использует. Свежие книжки ещё не появились, а документацию никто ни читает. Поэтому один из моих любимых вопросов на собеседовании по PHP — «что бы вы сделали, если бы вам в PHP понадобился двусвязанный список» (что-что, использовал бы SplDoublyLinkedList), впрочем если претендент не отвечает, в минус ему это не идёт, зато правильный ответ идёт в плюс.

Так вот, одна из вещей, которой мало кто пользуется — возможность создать в PHP свой итератор. У меня тут не руководство по итераторам, поэтому я ограничусь лишь кодом и примером использования. Вообще-то мне в коде понадобятся два итератора (второй будет итерировать строку с конца), но они очень похожи, поэтому я приведу только один.

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

UTF-8 достаточно хорошо устроен — первый байт символа всегда можно отличить по виду от его хвоста. У «хвоста» старшие биты всегда выглядят как «10», вот и весь критерий. Так что мы всегда можем сказать где начался новый символ — там где старшие биты байта не совпали с «10».
    class UtfString implements Iterator
    {
        protected $str;   // строка
        protected $idx;   // бинарный индекс строки
        protected $pos;   // UTF-8-индекс
        protected $len;   // бинарная длина
        protected $next;  // бинарный указатель на следующий

        protected $idx_start; // бинарный индекс откуда стартуем
        protected $pos_start; // UTF-8-индекс откуда стартуем

        // проверка — байт не является началом символа
        protected function isNotBegin($ch)
        {
            return (ord($ch) & 192) == 128;
        }

        public function __construct($str, $pos_start = 0)
        {
            $this->str = $str;
            $this->pos = $this->pos_start = $pos_start;
            $this->len = strlen($str);
            $this->next = null;

            if ($pos_start) {
                for ($i = 0; $i<$pos_start; $i++) {
                    $this->idx_start++; 

                    while ($this->isNotBegin($this->str[$this->idx_start])) {
                        $this->idx_start++;
                    }
                }
                $this->idx = $this->idx_start;

            } else {
                $this->idx = $this->idx_start = 0;
            }
        }

        public function current()
        {
            $idx = $this->idx;
            $out = $this->str[$idx++];

            while ($this->isNotBegin($ch = $this->str[$idx])) {
                $out .= $ch; // быстрее, чем массив!
                $idx++;
            }

            $this->next = $idx;

            return $out;
        }

        public function key()
        {
            return $this->pos;
        }

        public function next()
        {
            $this->pos++;

            if ($this->next) {
                $this->idx  = $this->next;
                $this->next = null;
            } else {
                for ($this->idx++; $this->isNotBegin($this->str[$this->idx]); $this->idx++);
            }
        }

        public function rewind()
        {
            $this->idx = $this->idx_start;
            $this->pos = $this->pos_start;
        }

        public function valid()
        {
            return $this->idx < $this->len;
        }

        public function __toString()
        {
            return $this->str;
        }
    }
Использовать итератор достаточно просто:
    $str = str_repeat('Привет', 64000);

    foreach (new UtfString($str) as $position => $char) {
        // …
    }
Так как в итерации сначала вызывается «current», а потом «next» мне показалось странным терять информацию о положении следующего символа, которую мы в «current» уже знаем, так что я передаю её в «next» через защищённое свойство.

Список функций (из моего списка используемых функций), которые я перепишу с итератором (или скорость которых увеличится): trim, ltrim, rtrim, wordwrap, strcspn и strspn, а так же некоторые места в коде проекта.
21 сентября 2010 13:00

ExH (exh.myopenid.com)
21 сентября 2010, 19:05

В буржуйнете уже как пол года есть два замечательных примера с итераторами от автора симфони.
http://fabien.potencier.org/article/43/find-your-files
http://fabien.potencier.org/article/44/php-iterators-and-streams-are-awesome

bolk (bolknote.ru)
21 сентября 2010, 22:10, ответ предназначен ExH (exh.myopenid.com):

Всякие там SplHeap и SqlQueue тоже в буржунете хорошо описаны. Но разрозненные блоги читать куда сложнее, чем документацию, но и последним, более лёгким (как я выше сказал) путём мало кто пользуется.

Дмитрий Фантазеров (Смирнов) (fantaseour.ya.ru)
5 октября 2010, 01:21, ответ предназначен bolk (bolknote.ru):

Свежие книжки ещё не появились, а документацию никто ни читает.
Так
1. Итераторы в документации слабовато отражены по сравнению со всем остальным (напр. http://php.net/manual/en/class.directoryiterator.php). Т.е. чуть ли не рефлексией надо было пользоваться, чтобы посмотреть, что итератор умеет, например вот так:
http://www.phpro.org/tutorials/Introduction-to-SPL-DirectoryIterator.html

2. Я вот нашел новую работу и надеюсь скоро смогу писать на php 5.3. А так, когда пишешь, для шаредов, где ничего нет и все сурово, то надежды на скорый приход 5.3 нету.

Дмитрий Фантазеров (Смирнов) (fantaseour.ya.ru)
5 октября 2010, 01:21, ответ предназначен bolk (bolknote.ru):

пользуясь случаем, хотел бы сказать спасибо за эту серию заметок.

bolk (bolknote.ru)
5 октября 2010, 15:06, ответ предназначен fantaseour.ya.ru:

Да не за что :)

Мы сейчас тоже заняты перетаскиванием нескольких проектов на PHP 5.3, кстати :)

Дмитрий Фантазеров (Смирнов) (fantaseour.ya.ru)
28 июня 2012, 18:30, ответ предназначен bolk (bolknote.ru):

Попробовал использовать Ваш итератор. Нашел небольшую ошибку:

В строке
while ($this->isNotBegin($ch = $this->str[$idx])) {
надо бы проверку на конец строки:
while ($idx<$this->len && $this->isNotBegin($ch = $this->str[$idx])) {

bolk (bolknote.ru)
28 июня 2012, 20:21, ответ предназначен fantaseour.ya.ru:

Это не ошибка. Мне подумалось, что notice+такая проверка быстрее, чем две проверки. Но может это и не так, надо проверить, когда время будет.

Дмитрий Фантазеров (Смирнов) (fantaseour.ya.ru)
28 июня 2012, 21:02

А почему бы тогда не подавить нотис?
@$this->str[$idx]
или это тоже медленно, но что-то я этого не читал нигде...

bolk (bolknote.ru)
28 июня 2012, 21:54, ответ предназначен fantaseour.ya.ru:

Это медленно, увы. Информация о медленности подавления через «собачку» есть где-то у Ильи Альшанетского.

Дмитрий Фантазеров (Смирнов) (fantaseour.ya.ru)
28 июня 2012, 22:07

ага, да есть такое. спасибо.

Ваше имя или адрес блога (можно OpenID):

Текст вашего комментария, не HTML:

Кому бы вы хотели ответить (или кликните на его аватару)