Это сайт — моя персональная записная книжка. Интересна мне, по большей части, история, своя жизнь и немного программирование.

strrev для UTF-8

В ходе обсуждения одной книге на «Хабре» придумал как развернуть строку UTF-8. Просто так её не перевернёшь — строка многобайтная, порядок байт важен.

Вот что я придумал: перевожу в двухбайтную кодировку UTF-16 с одним порядком байт, потом «strrev» переворачивает байты, а потом я конвертирую из кодировки с обратным порядков байт:

$test = 'А роза упала на лапу Азора ウィキ';

$test = iconv('utf-8', 'utf-16le', $test);
$test = strrev($test);
// キィウ арозА упал ан алапу азор А
echo iconv('utf-16be', 'utf-8', $test);
56 комментариев
SunChaser (sunchaser.info) 2012

дкмаю, лучше взять utf-32, у utf-16 тоже переменная длина символа, правда, в большинстве случаев это будет незаметно

Евгений Степанищев (bolknote.ru) 2012

Комментарий для sunchaser.info:

Ну, суррогатные пары крайняя редкость.

SunChaser (sunchaser.info) 2012

Комментарий для Евгения Степанищева:

тоже верно. в целом способ — гениален
спасибо производителям железа, не сумевшим договориться о порядке символов :D

Михаил Калашник (splurov.livejournal.com) 2012

А я делал preg_split а потом array_reverse().

Евгений Степанищев (bolknote.ru) 2012

Комментарий для splurov.livejournal.com:

Можно так, да. Но думаю, дольше будет.

Для читателей, такой вариант имеется ввиду:

echo implode(array_reverse(preg_split(’//u’, $test)));

greli (greli.livejournal.com) 2012

А зачем вообще нужно переворачивать строку? Это действительно где-то нужно кроме как на собеседованиях?

SiMM 2012

Интересно, а можно одной регуляркой с рекурсивным шаблоном обойтись?

Михаил Калашник (splurov.livejournal.com) 2012

Комментарий для greli.livejournal.com:

А зачем вообще нужно переворачивать строку? Это действительно где-то нужно кроме как на собеседованиях?

Я так «шутил» над забаненными пользователями на форуме.

Евгений Степанищев (bolknote.ru) 2012

Комментарий для greli.livejournal.com:

А зачем вообще нужно переворачивать строку? Это действительно где-то нужно кроме как на собеседованиях?

Откуда мне знать? Возможно нужно. Я, например, не знаю, что делает браузер, когда встречает dir=rtl, может переворачивает строку и печатает.

Евгений Степанищев (bolknote.ru) 2012

Комментарий для SiMM:

Интересно, а можно одной регуляркой с рекурсивным шаблоном обойтись?

Гм. Но рекурсивный шаблон не умеет рекурсивно заменять же :)

Евгений Степанищев (bolknote.ru) 2012

Комментарий для greli.livejournal.com:

Это действительно где-то нужно кроме как на собеседованиях?

В жизни столько задач встречалось, я бы никогда не подумал, что это надо.

sergey-cheban (sergey-cheban.livejournal.com) 2012

Комментарий для Евгения Степанищева:

Я, например, не знаю, что делает браузер, когда встречает dir=rtl, может переворачивает строку и печатает.

Там достаточно сложный алгоритм. Насколько я помню, он опубликован где-то на unicode.org. Умеет корректно обрабатывать русскоязычные вставки в арабских цитатах в английских текстах, да ещё на нескольких строках.

А strrev для переворачивания строк не годится. Он даже диакритику нормально не обработает.

Евгений Степанищев (bolknote.ru) 2012

Комментарий для sergey-cheban.livejournal.com:

А strrev для переворачивания строк не годится.

Годится. Для строк в однобайтовой кодировке. Его придумали в те времена, когда других и не было.

youROCK 2012

Я кстати в обсуждении на хабре привел обзор реализаций с сравнением производительности — способ с LE/BE самый быстрый:
http://habrahabr.ru/post/141290/#comment_4727585

Евгений Степанищев (bolknote.ru) 2012

Комментарий для youROCK:

Спасибо за сравнение моего способа с конкурентами :) Но есть способ быстрее!

Я взял ваш код и попробовал ещё несколько вариантов (на своём «Маке», PHP 5.4.0):

Joomla: 0.58767 sec
Mb: 0.82677 sec
Split: 0.79137 sec
My: 0.07228 sec
Iter: 0.02963 sec ←
My/Mb: 0.06835 sec
Plain: 0.00269 sec

Iter — это я взял свой итератор по UTF-8-строке ( http://bolknote.ru/all/2734 ) и, итерируя им, добавлял строку с другого конца:

foreach (new UtfString($str) as $position => $char) {
$str = $char . $str;
}

Соответственно, если выкинуть сам итератор и сунуть его код в цикл, должно стать ещё быстрее.

cyanide-burnout (cyanide-burnout.livejournal.com) 2012

  $text = «Тест перевернутой строки»;
  $result = «„;
  for ($index = 0; $index < strlen($text); $index ++)
  {
    $item = $text[$index];
    $byte = ord($item);
    if ($byte < 0x80)
    {
      $result = $item . $result;
      continue;
    }
    if (($byte & 0xc0) == 0x80)
    {
      $sequence .= $item;
      $count -​-​;
      if ($count == 0)
        $result = $sequence . $result;
      continue;
    }
    for ($count = 1; $count <= 6; $count ++)
    {
      $mask = (0xfc0 >> $count) & 0xff;
      $mark = (0xf80 >> $count) & 0xff;
      if (($byte & $mask) == $mark)
        break;
    }
    $sequence = $item;
  }
  print(„$result\n“);

Не?

Евгений Степанищев (bolknote.ru) 2012

Комментарий для cyanide-burnout.livejournal.com:

Лень смотреть код. То есть вы выкинули итератор и засунули его код в цикл, как я предлагал в предыдущем комментарии, об этом речь? Код получился, кстати, полная жесть, применять в других местах его трудно. Так что я бы использовал для небольших строк вариант с перекодированием, а в остальных случаях — итератор.

Евгений Степанищев (bolknote.ru) 2012

Кстати, есть библиотека для быстрой конвертации UTF-8 в UTF-16 с использованием SIMD: http://u8u16.costar.sfu.ca/

cyanide-burnout (cyanide-burnout.livejournal.com) 2012

Я ничего никуда не выкидывал. Просто сел и за пару минут написал.

Евгений Степанищев (bolknote.ru) 2012

Комментарий для cyanide-burnout.livejournal.com:

Ну вы фактически то же самое сделали, что я предлагал: засунули код итератора внутрь цикла (пусть вы взяли не мой код, а аналогичный). Что я не так сказал-то?

Только этим кодом пользоваться неудобно, о чём я уже так же сказал. Конечно, если нужна максимальная производительность, такой вариант лучше. Но в этом случае ещё лучше написать модуль на Си (я когда работал в «Яндексе» делал модуль для быстрого измерения длины строки в ЮТФ-8).

cyanide-burnout (cyanide-burnout.livejournal.com) 2012

Еще раз повторю. Ничей код я не брал. Просто взял и из головы написал. Вашего итератора в глаза не видел. Так что никакого плагиата и «выкидывания итератора». Вы тут приводите сравнение по скорости работы, вот я нарисовал наиболее оптимальный код для этой задачи. Естественно, такая реализация на C будет наиболее производительной и экономной к ресурсам. В случае с iconv, если рассматривать C-шный код происходит двухкратное выделение буфера на куче, причем размер буфера изначально берется максимальный, если предварительно не посчитать фактическую длинну исходного текста. В моем примере выделение буфера в случае кода на C происходит однократно, его размер соответствует размеру исходной строки. При этои нет никаких ограничений (в отличие от варианта с перекодированием) на использование страниц Юникода, то есть можно строку с символами UCS-4 без проблем переворачивать. Единственное, что еще стоит туда добавить — валидацию первого байта последовательности UTF-8.

Евгений Степанищев (bolknote.ru) 2012

Комментарий для cyanide-burnout.livejournal.com:

Я вас в плагиате и не обвиняю. Я говорю, что вы закодировали ту мысль, которую я написал: взять итератор и сунуть его в цикл. Что вы и проделали. Да, очевидно, что это быстрее. Я об этом и писал:

Соответственно, если выкинуть сам итератор и сунуть его код в цикл, должно стать ещё быстрее.

Вы в конце своего кода вопрошаете «не?». Почему не-то, если комментарием выше я ровно то же и предлагаю сделать?

Евгений Степанищев (bolknote.ru) 2012

Комментарий для cyanide-burnout.livejournal.com:

Я попробовал свою реализацию strrev, где попытался потратить свои «пять минут» на реализацию быстрого итератора:

Iter: 16.4157 sec ← итератор из приведённой мной ссылки
Cycle: 10.26968 sec ← ваш вариант за пять минут
My Cycle: 4.17994 sec ← мой вариант за пять минут
Plain: 0.01655 sec ← голый strrev

Евгений Степанищев (bolknote.ru) 2012
cyanide-burnout (cyanide-burnout.livejournal.com) 2012

Продолжим :)

#include <stddef.h>
#include <stdint.h>
#include <srting.h>
#include <stdio.h>
int strrev(uint8_t* source, uint8_t* destination)
{

  uint8_t* sequence;
  uint16_t mark;
  uint16_t mask;
  size_t count;
  destination += strlen(source) — 1;
  *destination = 0;
  while (*source != 0)
  {
    if (*source < 0x80)
    {
      destination -​-​;
      *destination = *source;
      source ++;
      continue;
    }
    if ((*source & 0xc0) == 0x80)
    {
      sequence ++;
      *sequence = *source;
      source ++;
      continue;
    }
    for (count = 2; count <= 8; count ++)
    {
      mask = (0xff80 >> count) & 0xff;
      mark = (0xff00 >> count) & 0xff;
      if ((*source & mask) == mark)
        break;
    }
    if (count == 8)
      return -1;
    sequence = destination -= count;
    *destination = *source;
    source ++;
  }
  return 0;

}
void main()
{

  char text[] = «Тест перевернутой строки»;
  char result[sizeof(text)];
  if (strrev(text, result) == 0)
    printf(«Result: %s\n», result);
  else
    printf(«Incorrect UTF-8 format\n»);

}

Евгений Степанищев (bolknote.ru) 2012

Комментарий для cyanide-burnout.livejournal.com:

Вы лучше мой код скомпилируйте в Си :)

Только чтобы такой жести не было как выше, разместите свой код на pastebin.com, а сюда ссылку скопируйте :)

cyanide-burnout (cyanide-burnout.livejournal.com) 2012

К сожалению вы мыслите в PHP, на C ваш код не оптимален :)

cyanide-burnout (cyanide-burnout.livejournal.com) 2012

Да, и у вас отсутствует поддержка U+3FFFFFF и U+7FFFFFFF

cyanide-burnout (cyanide-burnout.livejournal.com) 2012

http://pastebin.com/sypb51ky вот немного подправленная версия

Евгений Степанищев (bolknote.ru) 2012

Комментарий для cyanide-burnout.livejournal.com:

Да, и у вас отсутствует поддержка U+3FFFFFF и U+7FFFFFFF

Нет таких символов в стандарте.

К сожалению вы мыслите в PHP, на C ваш код не оптимален :)

К счастью, я мыслю на языке, на котором программирую :) Можно и на Си попробовать. Правда, я бы в этом случае лучше начал бы использовать ассемблерные SIMD-вставки.

cyanide-burnout (cyanide-burnout.livejournal.com) 2012

Ну так вы же мне предложили ваш код на С портировать, вот я вам и говорю — для С он ен опримален. Что касается ассемблера — вы заранее лешаете код кроссплатформенности :)

cyanide-burnout (cyanide-burnout.livejournal.com) 2012

Нет таких символов в стандарте.

Смотря в каком. Может и в Unicode 6.0 нет, зто ISO/IEC 10646 предусматривает такие схемы кодирования.
Или у нас как с проблемой 2000 или с 2038 — пока петух не клюнет, все будут кодить по старому :)

&lt;wj4 (hayk.livejournal.com) 2012

Комментарий для Евгения Степанищева:

А почему вы предпочитаете iconv mbstring’у?

&lt;wj4 (hayk.livejournal.com) 2012

Комментарий для Евгения Степанищева:

Кстати, нельзя ли подправить ваш движок, что бы в нике вместо «&lt;» отображался «<»?

&lt;wj4 (hayk.livejournal.com) 2012

Комментарий для Евгения Степанищева:

Вернее вместо «<» «<»?

Евгений Степанищев (bolknote.ru) 2012

Комментарий для hayk.livejournal.com:

А почему вы предпочитаете iconv mbstring’у?

Он быстрее.

Кстати, нельзя ли подправить ваш движок, что бы в нике вместо «&lt;» отображался «<»?

Да, я уже заметил. Займусь на днях.

&lt;wj4 (hayk.livejournal.com) 2012

Комментарий для Евгения Степанищева:

Он быстрее.

А есть данные каких-то тестов? Лет 8 назад на моих тестах mbstring был быстрее. Ну и функционал у него больше.

Займусь на днях.

Спасибо.

Sergey Solyanik (profiles.google.com/111742252137753914675) 2012

Кстати, про ендейцев — http://commandcenter.blogspot.com/2012/04/byte-order-fallacy.html

Евгений Степанищев (bolknote.ru) 2012

Комментарий для hayk.livejournal.com:

А есть данные каких-то тестов?

Да я сегодня попробовал заменить там iconv на mb_convert_string (PHP 5.4.0), iconv чуть-чуть быстрее был.

Евгений Степанищев (bolknote.ru) 2012

Комментарий для cyanide-burnout.livejournal.com:

Вот моя попытка подумать на Си:

http://pastebin.com/9wxgzqDg

Евгений Степанищев (bolknote.ru) 2012

Комментарий для cyanide-burnout.livejournal.com:

Сравнение с вашим вариантом по скорости:

bolk@Bolk ~/Sites/test  $ gcc -Os -std=c99 yours.c && time ./a.out
Result: ?кортс йотунревереп тсеТ
real 0m0.425s
user 0m0.421s
sys 0m0.002s
bolk@Bolk ~/Sites/test  $ gcc -Os -std=c99 my.c && time ./a.out
!икортс йотунревереп тсеТ
real 0m0.299s
user 0m0.282s
sys 0m0.003s

Евгений Степанищев (bolknote.ru) 2012

Ступил, что ключ -Os «по размеру» означает. Но с -O3 картина сильно не меняется.

Евгений Степанищев (bolknote.ru) 2012

Комментарий для hayk.livejournal.com:

Кстати, нельзя ли подправить ваш движок, что бы в нике вместо «<» отображался „<“?

Кажется, я забирал неправильно. Должно сработать верно в следующий раз.

Евгений Степанищев (bolknote.ru) 2012

А оказывает по производительности мой первый вариант тоже всё рвёт:

iconv: 0.18627 s ← iconv
mb: 0.58601 s ← то же, но с MB
cycle: 4.27128 s ← мой вариант с циклом
an cyc: 10.04912 sec ← предложенный читателем вариант с циклом

Евгений Степанищев (bolknote.ru) 2012
Artem 2012

Хорошая попытка на С :) Была аналогичная мысль, но ломало уже ее пробовать.
Но! Есть один кусочек там, который можно еще заоптимизировать %)
Как увидел, подумалось, можно ли еще подвылизать мой вариант...
Вот итог — http://pastebin.com/qwmNEE3D

Artem 2012

Да, первый вариант с iconv в любом случае должен рвать, так как 99% задачи выполняется в нативном скомпилированном коде. Мой вариант тоже очевидно, почему самый медленный :) Это сколько же кода надо интерпритатору разпарсить :)

Artem 2012

Блин. Исправьте мой пост. http://pastebin.com/gj8WL1Xn

Евгений Степанищев (bolknote.ru) 2012

Комментарий для Artem:

Не удалась оптимизация:

bolk@Bolk ~/Sites/test  $ gcc -O3 my.c -std=c99 && time ./a.out
!икортс йотунревереп тсеТ
real 0m0.263s
user 0m0.260s
sys 0m0.002s
bolk@Bolk ~/Sites/test  $ gcc -O3 artem.c && time ./a.out
!икортс йотунревереп тсеТ
real 0m0.352s
user 0m0.348s
sys 0m0.003s

Artem 2012

Могу вас только упрекнуть в мухляже.
Вот чистый тест на С — http://pastebin.com/7dYdQyPK

Результаты у меня такие:

Me: Result: икортс йотунревереп тсеТ — 1880000
Bolk: Result: икортс йотунревереп тсеТ — 2520000

Artem 2012

С оптимизацией по O3 —

gcc test.c -O3 -o test
~$ ./test
Me: Result: икортс йотунревереп тсеТ — 650000
Bolk: Result: икортс йотунревереп тсеТ — 1080000

Artem 2012

Да, и что вы тут сделали с OpenID? Со вчерашнего вечера я не могу постить сюда с OpenID

Artem 2012

Ну и теперь самое больное: ваш вариант с iconv просто не работает в случае, если в строке есть символы начиная с U+0800

Artem 2012

Как обычно, опечатался :) C D800, конечно. Блин, похоже про суррогатные пары уже писали.

Евгений Степанищев (bolknote.ru) 2012

Комментарий для Artem:

Да, и что вы тут сделали с OpenID? Со вчерашнего вечера я не могу постить сюда с OpenID

Ничего не сделал. Проверьте ваш OpenID. Я именно через OpenID вам и отвечаю.

Могу вас только упрекнуть в мухляже.

Зря. Я не мухлюю, зачем мне это? Вот запуск кода из вашего комментария:

bolk@Bolk ~/Sites/test  $ gcc -O3 test.c && ./a.out
test.c: In function ‘test’:
test.c:78: warning: format ‘%d’ expects type ‘int’, but argument 3 has type ‘clock_t’
test.c:78: warning: format ‘%d’ expects type ‘int’, but argument 3 has type ‘clock_t’
test.c: In function ‘main’:
test.c:84: warning: return type of ‘main’ is not ‘int’
Me: икортс йотунревереп тсеТ — 1438814
Bolk: икортс йотунревереп тсеТ — 1047433
Me: икортс йотунревереп тсеТ — 1541164
Bolk: икортс йотунревереп тсеТ — 1071701
Me: икортс йотунревереп тсеТ — 1353705
Bolk: икортс йотунревереп тсеТ — 1079784
Me: икортс йотунревереп тсеТ — 1454354
Bolk: икортс йотунревереп тсеТ — 1087533
Me: икортс йотунревереп тсеТ — 1447162
Bolk: икортс йотунревереп тсеТ — 1085313
Me: икортс йотунревереп тсеТ — 1368059

bolk@Bolk ~/Sites/test  $ gcc -​-​version
i686-apple-darwin11-llvm-gcc-4.2 (GCC) 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2335.15.00)
Copyright (C) 2007 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Artem 2012

А... Все понятно. LLVM. Используйте честеый GCC и будет вам счастье:

У меня — на GCC на Маке:

/usr/bin/gcc-4.2 -O3 test.c -o test
Me: икортс йотунревереп тсеТ — 444051
Bolk: икортс йотунревереп тсеТ — 568784
Me: икортс йотунревереп тсеТ — 451393
Bolk: икортс йотунревереп тсеТ — 569233
Me: икортс йотунревереп тсеТ — 459639
Bolk: икортс йотунревереп тсеТ — 568269
Me: икортс йотунревереп тсеТ — 460119
Bolk: икортс йотунревереп тсеТ — 574653
Me: икортс йотунревереп тсеТ — 452624
Bolk: икортс йотунревереп тсеТ — 576380
Me: икортс йотунревереп тсеТ — 457421
Bolk: икортс йотунревереп тсеТ — 572093
Me: икортс йотунревереп тсеТ — 455012
Bolk: икортс йотунревереп тсеТ — 570585
Me: икортс йотунревереп тсеТ — 451122
Bolk: икортс йотунревереп тсеТ — 569084
Me: икортс йотунревереп тсеТ — 457265
Bolk: икортс йотунревереп тсеТ — 571624
Me: икортс йотунревереп тсеТ — 450616
Bolk: икортс йотунревереп тсеТ — 569169

На LLVM на Маке:

Me: икортс йотунревереп тсеТ — 918185
Bolk: икортс йотунревереп тсеТ — 689982
Me: икортс йотунревереп тсеТ — 934351
Bolk: икортс йотунревереп тсеТ — 689400
Me: икортс йотунревереп тсеТ — 1026613
Bolk: икортс йотунревереп тсеТ — 689698
Me: икортс йотунревереп тсеТ — 909506
Bolk: икортс йотунревереп тсеТ — 689857
Me: икортс йотунревереп тсеТ — 1040461
Bolk: икортс йотунревереп тсеТ — 689440
Me: икортс йотунревереп тсеТ — 921184
Bolk: икортс йотунревереп тсеТ — 689783
Me: икортс йотунревереп тсеТ — 922327
Bolk: икортс йотунревереп тсеТ — 689928
Me: икортс йотунревереп тсеТ — 871381
Bolk: икортс йотунревереп тсеТ — 690166
Me: икортс йотунревереп тсеТ — 938563
Bolk: икортс йотунревереп тсеТ — 690099
Me: икортс йотунревереп тсеТ — 926310
Bolk: икортс йотунревереп тсеТ — 689970

На Линухах (gcc (Debian 4.4.5-8) 4.4.5):

Me: икортс йотунревереп тсеТ — 600000
Bolk: икортс йотунревереп тсеТ — 1090000
Me: икортс йотунревереп тсеТ — 790000
Bolk: икортс йотунревереп тсеТ — 1080000
Me: икортс йотунревереп тсеТ — 800000
Bolk: икортс йотунревереп тсеТ — 1070000
Me: икортс йотунревереп тсеТ — 790000
Bolk: икортс йотунревереп тсеТ — 1080000
Me: икортс йотунревереп тсеТ — 790000
Bolk: икортс йотунревереп тсеТ — 1070000
Me: икортс йотунревереп тсеТ — 790000
Bolk: икортс йотунревереп тсеТ — 1080000
Me: икортс йотунревереп тсеТ — 790000
Bolk: икортс йотунревереп тсеТ — 1080000
Me: икортс йотунревереп тсеТ — 790000
Bolk: икортс йотунревереп тсеТ — 1080000
Me: икортс йотунревереп тсеТ — 790000
Bolk: икортс йотунревереп тсеТ — 1090000
Me: икортс йотунревереп тсеТ — 780000
Bolk: икортс йотунревереп тсеТ — 1080000

Вот теперь сравните тайминги на Маке с LLVM и GCC — все увидите. И про код тоже.