ReverseString для кодировки UTF-8

Модератор: Модераторы

ReverseString для кодировки UTF-8

Сообщение Python » 01.10.2018 20:31:11

Во время чтения очередной статьи про собеседования на программиста, столкнулся с такой простой на первый взгляд задачей: претенденту предложили написать функцию, которая "переворачивает" строку. Аналог ReverseString, но свой. Ответ, который дал претендент, не устроил собеседователя. Оказалось, что он ждал уточняющего вопроса: в какой кодировке, дескать, задана строка, а ответ должен был быть принят для кодировки UTF-8. С задачей претендент, похоже, не справился, а я решил написать свой вариант, поскольку на первой странице гугля такового не обнаружилось. Предлагаю на суд общественности:
Код: Выделить всё
// переворачивает строку, записанную в UTF-8 в обратном направлении
function ReverseStringUtf8(const S:string):string;
var
  PrimeChar,LastChar:integer;
  B:byte;
begin
  PrimeChar:=1;
  LastChar:=Length(S);
  SetLength(Result,LastChar);
  while LastChar>0 do begin
    B:=ord(S[PrimeChar]);
    if B and $F7=$F0 then begin
      // четырёхбайтный символ
      Result[LastChar-3]:=S[PrimeChar+0];
      Result[LastChar-2]:=S[PrimeChar+1];
      Result[LastChar-1]:=S[PrimeChar+2];
      Result[LastChar-0]:=S[PrimeChar+3];
      Inc(PrimeChar,4);
      Dec(LastChar,4);
    end else if B and $F0=$E0 then begin
      // трёхбайтовый символ
      Result[LastChar-2]:=S[PrimeChar+0];
      Result[LastChar-1]:=S[PrimeChar+1];
      Result[LastChar-0]:=S[PrimeChar+2];
      Inc(PrimeChar,3);
      Dec(LastChar,3);
    end else if B and $E0=$C0 then begin
      // двухбайтовый символ
      Result[LastChar-1]:=S[PrimeChar+0];
      Result[LastChar-0]:=S[PrimeChar+1];
      Inc(PrimeChar,2);
      Dec(LastChar,2);
    end else begin
      // однобайтный символ
      Result[LastChar]:=S[PrimeChar];
      Inc(PrimeChar);
      Dec(LastChar);
    end;
  end;
end;
Python
новенький
 
Сообщения: 20
Зарегистрирован: 23.01.2018 21:50:17

Re: ReverseString для кодировки UTF-8

Сообщение SSerge » 02.10.2018 06:04:51

Что-то очень сомневаюсь, что работодатель ожидает от претендента знаний таблицы префиксов utf8 на память.
И очень сомневаюсь, что ему понравится решение, как бы намекающее на готовность претендента постоянно писать нечитаемый код, основанный на внутренних структурах организации данных. Если, конечно, это не набор на крайне узкую задачу. :D
SSerge
энтузиаст
 
Сообщения: 971
Зарегистрирован: 12.01.2012 05:34:14
Откуда: Барнаул

Re: ReverseString для кодировки UTF-8

Сообщение Vapaamies » 22.10.2018 18:45:03

SSerge писал(а):Что-то очень сомневаюсь, что работодатель ожидает от претендента знаний таблицы префиксов utf8 на память.

На самом деле там нечего запоминать, если помнить принцип. Но в целом согласен, задание весьма спорное.
Аватара пользователя
Vapaamies
постоялец
 
Сообщения: 291
Зарегистрирован: 24.07.2012 22:37:59
Откуда: Санкт-Петербург

Re: ReverseString для кодировки UTF-8

Сообщение Mirage » 24.10.2018 00:30:56

Python писал(а):B:=ord(S[PrimeChar]);


Это выражение возьмет 2 байта по указанному индексу и обрежет до одного. Это точно то, что планировалось?
Какой набор данных используется для тестирования данной функции? Есть ли там строки с 3-х и 4-х байтными символами, а также суррогатными парами?
Mirage
энтузиаст
 
Сообщения: 881
Зарегистрирован: 06.05.2005 20:29:07
Откуда: Russia

Re: ReverseString для кодировки UTF-8

Сообщение SSerge » 24.10.2018 09:05:42

Mirage писал(а):Это выражение возьмет 2 байта по указанному индексу и обрежет до одного.


"В военное время значение ПИ может достигать четырех и даже пяти" (С)
Если это выражение возьмет два байта (а верно это в случае модели равенства String=UnicodeString, что верно только для дельфи), то весь алгоритм вообще рассыплется. Хотя бы из-за того, что в функцию будет передан не utf8, а utf16.
SSerge
энтузиаст
 
Сообщения: 971
Зарегистрирован: 12.01.2012 05:34:14
Откуда: Барнаул

Re: ReverseString для кодировки UTF-8

Сообщение vada » 24.10.2018 14:48:21

Было время искал работу. Ходил по собеседованиям. Даже разочек занимался подобной гуйней. Задачки у собеседователя были ну просто пепец! Хак на хаке! Я у него спросил, типа, вы все свои программы разрабатываете с подобными хаками? Он гордо ответил что все задачки взяты из реализаций их сотрудников. Я даже не стал пробовать что-то ему написать. Просто ушел. И впредь до собеседования спрашивал будет ли написание тестов. На собеседования с тестами больше не ходил. Чего зря время тратить.
Аватара пользователя
vada
энтузиаст
 
Сообщения: 691
Зарегистрирован: 14.02.2006 13:43:17

Re: ReverseString для кодировки UTF-8

Сообщение bormant » 08.11.2018 02:20:32

Раз уж ожидается корректная utf8-строка, проще опереться не на префиксы, а на признак символа-продолжения Byte(s[i]) and $C0=$80.
Получится что-то вроде:
Код: Выделить всё
function RevStrUtf8(const s: String): String;
var i, j: Integer;
begin
  Result:=''; j:=Length(s)+1;
  for i:=Length(s) downto 1 do
    if Byte(s[i]) and $C0<>$80 then begin
      Result:=Result+Copy(s,i,j-i); j:=i;
    end;
end;

Можно вместо Result+Copy() добавить SetLength() и Move(), если есть желание.
Аватара пользователя
bormant
постоялец
 
Сообщения: 407
Зарегистрирован: 21.03.2012 11:26:01

Re: ReverseString для кодировки UTF-8

Сообщение runewalsh » 08.11.2018 07:53:37

Все забыли про комбинируемые символы.
Например, ударе́ние записывается двумя кодовыми точками: <символ> <U+0301>.
В перевёрнутом виде они должны остаться единым целым. (Так ведёт себя встроенная функция Utf8CodePointLen с параметром IncludeCombiningDiacriticalMarks = true).

В идеале ещё можно вспомнить про RtL- и LtR-метки, а может, и что-то другое.
Короче говоря, не так просто всё это...
Аватара пользователя
runewalsh
энтузиаст
 
Сообщения: 578
Зарегистрирован: 27.04.2010 00:15:25

Re: ReverseString для кодировки UTF-8

Сообщение bormant » 08.11.2018 20:38:52

Кстати, если правильно путаю, диакритика в плоскости BMP (\u3000-\u3fff), а в utf8 они кодируются 2-байтовыми вариантами с первым байтом $C0, это более-менее легко учесть...
Аватара пользователя
bormant
постоялец
 
Сообщения: 407
Зарегистрирован: 21.03.2012 11:26:01


Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2

Рейтинг@Mail.ru