PHP и 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, а так же некоторые места в коде проекта.