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);
2 апреля 2012 20:10

SunChaser (sunchaser.info)
3 апреля 2012, 16:05

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

bolk (bolknote.ru)
3 апреля 2012, 16:06, ответ предназначен SunChaser (sunchaser.info):

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

SunChaser (sunchaser.info)
3 апреля 2012, 16:10, ответ предназначен bolk (bolknote.ru):

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

Михаил Калашник (splurov.livejournal.com)
3 апреля 2012, 16:14

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

bolk (bolknote.ru)
3 апреля 2012, 16:19, ответ предназначен Михаил Калашник (splurov.livejournal.com):

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

Для читателей, такой вариант имеется ввиду:
echo implode(array_reverse(preg_split('//u', $test)));

greli (greli.livejournal.com)
3 апреля 2012, 17:13

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

SiMM (инкогнито)
3 апреля 2012, 17:19

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

Михаил Калашник (splurov.livejournal.com)
3 апреля 2012, 17:35, ответ предназначен greli (greli.livejournal.com):

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

bolk (bolknote.ru)
3 апреля 2012, 17:41, ответ предназначен greli (greli.livejournal.com):

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

bolk (bolknote.ru)
3 апреля 2012, 17:42, ответ предназначен SiMM

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

bolk (bolknote.ru)
3 апреля 2012, 17:42, ответ предназначен greli (greli.livejournal.com):

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

sergey-cheban (sergey-cheban.livejournal.com)
3 апреля 2012, 21:25, ответ предназначен bolk (bolknote.ru):

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

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

bolk (bolknote.ru)
3 апреля 2012, 21:50, ответ предназначен sergey-cheban.livejournal.com:

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

youROCK (инкогнито)
4 апреля 2012, 02:44

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

bolk (bolknote.ru)
4 апреля 2012, 07:57, ответ предназначен 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/2010/09/21/~2734) и, итерируя им, добавлял строку с другого конца:
foreach (new UtfString($str) as $position => $char) {
$str = $char . $str;
}
Соответственно, если выкинуть сам итератор и сунуть его код в цикл, должно стать ещё быстрее.

cyanide-burnout (cyanide-burnout.livejournal.com)
4 апреля 2012, 10:18


  $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");


Не?

bolk (bolknote.ru)
4 апреля 2012, 10:33, ответ предназначен cyanide-burnout.livejournal.com:

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

bolk (bolknote.ru)
4 апреля 2012, 10:41

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

cyanide-burnout (cyanide-burnout.livejournal.com)
4 апреля 2012, 10:48

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

bolk (bolknote.ru)
4 апреля 2012, 11:13, ответ предназначен cyanide-burnout.livejournal.com:

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

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

cyanide-burnout (cyanide-burnout.livejournal.com)
4 апреля 2012, 11:43

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

bolk (bolknote.ru)
4 апреля 2012, 11:51, ответ предназначен cyanide-burnout.livejournal.com:

Я вас в плагиате и не обвиняю. Я говорю, что вы закодировали ту мысль, которую я написал: взять итератор и сунуть его в цикл. Что вы и проделали. Да, очевидно, что это быстрее. Я об этом и писал:
Соответственно, если выкинуть сам итератор и сунуть его код в цикл, должно стать ещё быстрее.
Вы в конце своего кода вопрошаете «не?». Почему не-то, если комментарием выше я ровно то же и предлагаю сделать?

bolk (bolknote.ru)
4 апреля 2012, 12:13, ответ предназначен cyanide-burnout.livejournal.com:

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

bolk (bolknote.ru)
4 апреля 2012, 12:14

Вот код:

cyanide-burnout (cyanide-burnout.livejournal.com)
4 апреля 2012, 12:26

Продолжим :)
#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");
}

bolk (bolknote.ru)
4 апреля 2012, 12:34, ответ предназначен cyanide-burnout.livejournal.com:

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

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

cyanide-burnout (cyanide-burnout.livejournal.com)
4 апреля 2012, 12:36

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

cyanide-burnout (cyanide-burnout.livejournal.com)
4 апреля 2012, 12:38

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

cyanide-burnout (cyanide-burnout.livejournal.com)
4 апреля 2012, 12:41

вот немного подправленная версия

bolk (bolknote.ru)
4 апреля 2012, 13:00, ответ предназначен cyanide-burnout.livejournal.com:

Да, и у вас отсутствует поддержка U+3FFFFFF и U+7FFFFFFF
Нет таких символов в стандарте.
К сожалению вы мыслите в PHP, на C ваш код не оптимален :)
К счастью, я мыслю на языке, на котором программирую :) Можно и на Си попробовать. Правда, я бы в этом случае лучше начал бы использовать ассемблерные SIMD-вставки.

cyanide-burnout (cyanide-burnout.livejournal.com)
4 апреля 2012, 13:06

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

cyanide-burnout (cyanide-burnout.livejournal.com)
4 апреля 2012, 13:17

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

&lt;wj4 (hayk.livejournal.com)
4 апреля 2012, 13:32, ответ предназначен bolk (bolknote.ru):

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

&lt;wj4 (hayk.livejournal.com)
4 апреля 2012, 13:35, ответ предназначен bolk (bolknote.ru):

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

&lt;wj4 (hayk.livejournal.com)
4 апреля 2012, 13:36, ответ предназначен bolk (bolknote.ru):

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

bolk (bolknote.ru)
4 апреля 2012, 14:03, ответ предназначен &lt;wj4 (hayk.livejournal.com):

А почему вы предпочитаете iconv mbstring'у?
Он быстрее.
Кстати, нельзя ли подправить ваш движок, что бы в нике вместо «&amp;lt;» отображался «&lt;»?
Да, я уже заметил. Займусь на днях.

&lt;wj4 (hayk.livejournal.com)
4 апреля 2012, 14:10, ответ предназначен bolk (bolknote.ru):

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

Sergey Solyanik (profiles.google.com/111742252137753914675)
4 апреля 2012, 14:47

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

bolk (bolknote.ru)
4 апреля 2012, 14:57, ответ предназначен &lt;wj4 (hayk.livejournal.com):

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

bolk (bolknote.ru)
4 апреля 2012, 16:14, ответ предназначен cyanide-burnout.livejournal.com:

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

bolk (bolknote.ru)
4 апреля 2012, 16:15, ответ предназначен 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

bolk (bolknote.ru)
4 апреля 2012, 16:38

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

bolk (bolknote.ru)
4 апреля 2012, 22:13, ответ предназначен &lt;wj4 (hayk.livejournal.com):

Кстати, нельзя ли подправить ваш движок, что бы в нике вместо «&lt;» отображался „<“?
Кажется, я забирал неправильно. Должно сработать верно в следующий раз.

bolk (bolknote.ru)
4 апреля 2012, 22:56

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

bolk (bolknote.ru)
4 апреля 2012, 22:56

Вот код:

Artem (инкогнито)
5 апреля 2012, 22:19

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

Artem (инкогнито)
5 апреля 2012, 22:27

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

Artem (инкогнито)
5 апреля 2012, 22:34

Блин. Исправьте мой пост.

bolk (bolknote.ru)
6 апреля 2012, 07:46, ответ предназначен 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 (инкогнито)
6 апреля 2012, 09:50

Могу вас только упрекнуть в мухляже.
Вот чистый тест на С -

Результаты у меня такие:
Me: Result: икортс йотунревереп тсеТ - 1880000
Bolk: Result: икортс йотунревереп тсеТ - 2520000

Artem (инкогнито)
6 апреля 2012, 09:57

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

Artem (инкогнито)
6 апреля 2012, 09:59

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

Artem (инкогнито)
6 апреля 2012, 11:09

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

Artem (инкогнито)
6 апреля 2012, 11:12

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

bolk (bolknote.ru)
6 апреля 2012, 14:11, ответ предназначен 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 (инкогнито)
6 апреля 2012, 14:27

А... Все понятно. 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 - все увидите. И про код тоже.

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

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

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