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);
дкмаю, лучше взять utf-32, у utf-16 тоже переменная длина символа, правда, в большинстве случаев это будет незаметно
Комментарий для sunchaser.info:
Ну, суррогатные пары крайняя редкость.
Комментарий для Евгения Степанищева:
тоже верно. в целом способ — гениален
спасибо производителям железа, не сумевшим договориться о порядке символов :D
А я делал preg_split а потом array_reverse().
Комментарий для splurov.livejournal.com:
Можно так, да. Но думаю, дольше будет.
Для читателей, такой вариант имеется ввиду:
А зачем вообще нужно переворачивать строку? Это действительно где-то нужно кроме как на собеседованиях?
Интересно, а можно одной регуляркой с рекурсивным шаблоном обойтись?
Комментарий для greli.livejournal.com:
Я так «шутил» над забаненными пользователями на форуме.
Комментарий для greli.livejournal.com:
Откуда мне знать? Возможно нужно. Я, например, не знаю, что делает браузер, когда встречает dir=rtl, может переворачивает строку и печатает.
Комментарий для SiMM:
Гм. Но рекурсивный шаблон не умеет рекурсивно заменять же :)
Комментарий для greli.livejournal.com:
В жизни столько задач встречалось, я бы никогда не подумал, что это надо.
Комментарий для Евгения Степанищева:
Там достаточно сложный алгоритм. Насколько я помню, он опубликован где-то на unicode.org. Умеет корректно обрабатывать русскоязычные вставки в арабских цитатах в английских текстах, да ещё на нескольких строках.
А strrev для переворачивания строк не годится. Он даже диакритику нормально не обработает.
Комментарий для sergey-cheban.livejournal.com:
Годится. Для строк в однобайтовой кодировке. Его придумали в те времена, когда других и не было.
Я кстати в обсуждении на хабре привел обзор реализаций с сравнением производительности — способ с LE/BE самый быстрый:
http://habrahabr.ru/post/141290/#comment_4727585
Комментарий для youROCK:
Спасибо за сравнение моего способа с конкурентами :) Но есть способ быстрее!
Я взял ваш код и попробовал ещё несколько вариантов (на своём «Маке», PHP 5.4.0):
Iter — это я взял свой итератор по UTF-8-строке ( http://bolknote.ru/all/2734 ) и, итерируя им, добавлял строку с другого конца:
Соответственно, если выкинуть сам итератор и сунуть его код в цикл, должно стать ещё быстрее.
$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“);
Не?
Комментарий для cyanide-burnout.livejournal.com:
Лень смотреть код. То есть вы выкинули итератор и засунули его код в цикл, как я предлагал в предыдущем комментарии, об этом речь? Код получился, кстати, полная жесть, применять в других местах его трудно. Так что я бы использовал для небольших строк вариант с перекодированием, а в остальных случаях — итератор.
Кстати, есть библиотека для быстрой конвертации UTF-8 в UTF-16 с использованием SIMD: http://u8u16.costar.sfu.ca/
Я ничего никуда не выкидывал. Просто сел и за пару минут написал.
Комментарий для cyanide-burnout.livejournal.com:
Ну вы фактически то же самое сделали, что я предлагал: засунули код итератора внутрь цикла (пусть вы взяли не мой код, а аналогичный). Что я не так сказал-то?
Только этим кодом пользоваться неудобно, о чём я уже так же сказал. Конечно, если нужна максимальная производительность, такой вариант лучше. Но в этом случае ещё лучше написать модуль на Си (я когда работал в «Яндексе» делал модуль для быстрого измерения длины строки в ЮТФ-8).
Еще раз повторю. Ничей код я не брал. Просто взял и из головы написал. Вашего итератора в глаза не видел. Так что никакого плагиата и «выкидывания итератора». Вы тут приводите сравнение по скорости работы, вот я нарисовал наиболее оптимальный код для этой задачи. Естественно, такая реализация на C будет наиболее производительной и экономной к ресурсам. В случае с iconv, если рассматривать C-шный код происходит двухкратное выделение буфера на куче, причем размер буфера изначально берется максимальный, если предварительно не посчитать фактическую длинну исходного текста. В моем примере выделение буфера в случае кода на C происходит однократно, его размер соответствует размеру исходной строки. При этои нет никаких ограничений (в отличие от варианта с перекодированием) на использование страниц Юникода, то есть можно строку с символами UCS-4 без проблем переворачивать. Единственное, что еще стоит туда добавить — валидацию первого байта последовательности UTF-8.
Комментарий для cyanide-burnout.livejournal.com:
Я вас в плагиате и не обвиняю. Я говорю, что вы закодировали ту мысль, которую я написал: взять итератор и сунуть его в цикл. Что вы и проделали. Да, очевидно, что это быстрее. Я об этом и писал:
Вы в конце своего кода вопрошаете «не?». Почему не-то, если комментарием выше я ровно то же и предлагаю сделать?
Комментарий для cyanide-burnout.livejournal.com:
Я попробовал свою реализацию strrev, где попытался потратить свои «пять минут» на реализацию быстрого итератора:
Вот код: http://pastebin.com/AFNccVzj
Продолжим :)
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;
char text[] = «Тест перевернутой строки»;
char result[sizeof(text)];
if (strrev(text, result) == 0)
printf(«Result: %s\n», result);
else
printf(«Incorrect UTF-8 format\n»);
Комментарий для cyanide-burnout.livejournal.com:
Вы лучше мой код скомпилируйте в Си :)
Только чтобы такой жести не было как выше, разместите свой код на pastebin.com, а сюда ссылку скопируйте :)
К сожалению вы мыслите в PHP, на C ваш код не оптимален :)
Да, и у вас отсутствует поддержка U+3FFFFFF и U+7FFFFFFF
http://pastebin.com/sypb51ky вот немного подправленная версия
Комментарий для cyanide-burnout.livejournal.com:
Нет таких символов в стандарте.
К счастью, я мыслю на языке, на котором программирую :) Можно и на Си попробовать. Правда, я бы в этом случае лучше начал бы использовать ассемблерные SIMD-вставки.
Ну так вы же мне предложили ваш код на С портировать, вот я вам и говорю — для С он ен опримален. Что касается ассемблера — вы заранее лешаете код кроссплатформенности :)
Смотря в каком. Может и в Unicode 6.0 нет, зто ISO/IEC 10646 предусматривает такие схемы кодирования.
Или у нас как с проблемой 2000 или с 2038 — пока петух не клюнет, все будут кодить по старому :)
Комментарий для Евгения Степанищева:
А почему вы предпочитаете iconv mbstring’у?
Комментарий для Евгения Степанищева:
Кстати, нельзя ли подправить ваш движок, что бы в нике вместо «<» отображался «<»?
Комментарий для Евгения Степанищева:
Вернее вместо «<» «<»?
Комментарий для hayk.livejournal.com:
Он быстрее.
Да, я уже заметил. Займусь на днях.
Комментарий для Евгения Степанищева:
А есть данные каких-то тестов? Лет 8 назад на моих тестах mbstring был быстрее. Ну и функционал у него больше.
Спасибо.
Кстати, про ендейцев — http://commandcenter.blogspot.com/2012/04/byte-order-fallacy.html
Комментарий для hayk.livejournal.com:
Да я сегодня попробовал заменить там iconv на mb_convert_string (PHP 5.4.0), iconv чуть-чуть быстрее был.
Комментарий для cyanide-burnout.livejournal.com:
Вот моя попытка подумать на Си:
http://pastebin.com/9wxgzqDg
Комментарий для cyanide-burnout.livejournal.com:
Сравнение с вашим вариантом по скорости:
Ступил, что ключ -Os «по размеру» означает. Но с -O3 картина сильно не меняется.
Комментарий для hayk.livejournal.com:
Кажется, я забирал неправильно. Должно сработать верно в следующий раз.
А оказывает по производительности мой первый вариант тоже всё рвёт:
Вот код:
http://pastebin.com/WVCFCydP
Хорошая попытка на С :) Была аналогичная мысль, но ломало уже ее пробовать.
Но! Есть один кусочек там, который можно еще заоптимизировать %)
Как увидел, подумалось, можно ли еще подвылизать мой вариант...
Вот итог — http://pastebin.com/qwmNEE3D
Да, первый вариант с iconv в любом случае должен рвать, так как 99% задачи выполняется в нативном скомпилированном коде. Мой вариант тоже очевидно, почему самый медленный :) Это сколько же кода надо интерпритатору разпарсить :)
Блин. Исправьте мой пост. http://pastebin.com/gj8WL1Xn
Комментарий для Artem:
Не удалась оптимизация:
Могу вас только упрекнуть в мухляже.
Вот чистый тест на С — http://pastebin.com/7dYdQyPK
Результаты у меня такие:
С оптимизацией по O3 —
Да, и что вы тут сделали с OpenID? Со вчерашнего вечера я не могу постить сюда с OpenID
Ну и теперь самое больное: ваш вариант с iconv просто не работает в случае, если в строке есть символы начиная с U+0800
Как обычно, опечатался :) C D800, конечно. Блин, похоже про суррогатные пары уже писали.
Комментарий для Artem:
Ничего не сделал. Проверьте ваш OpenID. Я именно через OpenID вам и отвечаю.
Зря. Я не мухлюю, зачем мне это? Вот запуск кода из вашего комментария:
А... Все понятно. LLVM. Используйте честеый GCC и будет вам счастье:
У меня — на GCC на Маке:
На LLVM на Маке:
На Линухах (gcc (Debian 4.4.5-8) 4.4.5):
Вот теперь сравните тайминги на Маке с LLVM и GCC — все увидите. И про код тоже.