Web-разработка

Индексация строк в Rust и TypeScript в сравнениях

24.02.2022

Краткое содержание

В Rust обращение к символам в строках по индексу не компилируется.
Рассмотрим, как Rust работает со строками.
Обсудим, как JavaScript обрабатывает строки.
Сравним классический алгоритм is_palindrome в Rust и TypeScript.

Текст играет важную роль в языках программирования. В Rust и JavaScript его обработка на всевозможных письменных языках реализуется посредством такого типа данных, как строка (String). На примере простой концепции индексации строки мы посмотрим, как Rust и JavaScript обрабатывают сами строки и такие нюансы в них, как графемы или даже эмоджи.

Для введения в данную концепцию воспользуемся классическим алгоритмом is_palindrome.

`is_palindrome` в Rust

В самом общем смысле палиндром означает строку, которая одинаково читается в обоих направлениях. Например, “Анна”, “А роза упала на лапу Азора” или даже “02/02/2020”.

В целях данной статьи и для простоты алгоритма введем более узкое определение. Под палиндромом будем понимать “непрерывную последовательность строчных буквенных символов ASCII без пробела”.

Согласно первому подходу проще всего было бы использовать два указателя. Один берет направление от начала заданной строки и двигается к ее концу, а другой — от конца к началу. Во время перемещения указателей сравниваем отмечаемые ими символы. Строка является палиндромом при равенстве всех сравнений. Как в следующем примере:

// ❌ Не компилируется 
fn is_palindrome(str: String) -> bool {
  //        lp       rp
  //        |        |
  //        v →    ← v
  // str = "aabbccbbaa"
  let mut lp = 0;
  let mut rp = str.len() - 1;
  while lp < rp {
    if str[lp] != str[rp] {
    // ^^^^^^^ `Строка не индексируется по `usize` 
      return false;
    }
    lp += 1;
    rp -= 1;
  }
  true
}

При попытке скомпилировать программу вы заметите, что компилятор Rust не обеспечивает доступ к символам по индексу. Довольно интересное ограничение, учитывая, что языки JavaScript, Go и Python предоставляют такую возможность.

Копнув поглубже, мы обнаружим ряд строковых методов из стандартной библиотеки, например chars(), для доступа к символам строки. chars() возвращает итератор по символам char среза строки. Таким образом, для обращения к символам по индексу придется провести итерацию среза строки, как в следующем примере:

let left = str.as_str().chars().nth(lp).unwrap();

Временная сложность этой простой задачи составляет O(n) вместо O(1).

В чем причина?

Строки Rust представлены в кодировке Unicode и UTF-8

В официальной документации Rust можно найти внутреннее представление String:

Тип String является оболочкой над типом Vec<u8>.

Для строк в ASCII каждый символ представлен 1 байтом, закодированном в UTF-8. Однако для строк в других письменных языках, например хинди в транскрипции Devanagari из документации Rust, каждый символ кодируется в UTF-8 с несколькими значениями Unicode (кодовая единица).

В документации Rust говорится:

Индексирование строк часто является плохой идеей, потому что не ясно, каким должен быть возвращаемый тип такой операции: байтовым значением, символом, кластером графем или срезом строки.

Это одна из причин, по которой компилятор Rust не разрешает прямой доступ к символам в строке. Настоятельно рекомендуем ознакомиться с материалом по этой теме в документации. Легкое и познавательное чтение гарантируется.

Корректировка `is_palindrome`

Мы можем провести итерацию по байтам и сравнить первую половину строки со второй половиной в обратном направлении. При их равенстве делаем вывод, что это палиндром:

// ✅
fn is_palindrome(str: String) -> bool {
    let half = str.len() / 2;
    let forward = str.bytes().take(half);
    let backward = str.bytes().rev().take(half);
    forward.eq(backward)
}
fn main() {
    assert_eq!(is_palindrome(String::from("")), true);
    assert_eq!(is_palindrome(String::from("aabbccbbaa")), true);
    assert_eq!(is_palindrome(String::from("aabbccbbab")), false);
}

Временная сложность — O(n), где n равняется длине строки.
Пространственная сложность — O(1).

Пространственная сложность составляет O(1), поскольку каждый итератор создает указатель и счетчик.

Второй подход заключается в применении типажа (trait) DoubleEndedIterator и объединении прямого и обратного итераторов с помощью zip():

fn is_palindrome(str: String) -> bool {
    let mut chars = string.bytes();
    while let Some((front, back)) = chars.next().zip(chars.next_back()) {
        if front != back {
            return false;
        }
    }
    true
}

Временная сложность — O(n), где n равняется длине строки.
Пространственная сложность — O(1).

Благодарю Reddit за предложенный подход!

`isPalindrome` в TypeScript

JavaScript допускает индексацию строк. Поэтому мы сможем выполнить алгоритм с двумя указателями, который не компилировался в Rust.

/*
 *  lp       rp
 *  |        |
 *  v →    ← v
 * "aabbccbbaa"
 */
function isPalindrome(str: string): boolean {
  let lp = 0
  let rp = str.length - 1
  while (lp < rp) {
    if (str[lp] !== str[rp]) {
      return false
    }
    lp += 1
    rp -= 1
  }
  return true
}
isPalindrome('') // true
isPalindrome('aabbccbbaa') // true
isPalindrome('aabbccbbab') // false

Временная сложность — O(n), где n равняется длине строки.
Пространственная сложность — O(1). Постоянное пространство для двух указателей.

Или просто сравните строки в прямом и обратном порядке:

function isPalindrome(str: string): boolean {
  return str === str.split('').reverse().join('')
}

Временная сложность — O(n), где n равняется длине входной строки.
Пространственная сложность — O(n), где n равняется длине входной строки.

В JavaScript мы довольно легко справились с задачей. Значит ли это, что он обрабатывает строки иначе, чем Rust?

Строки JavaScript представлены в кодировке UTF-16

Определение примитивного строкового значения дано в стандарте ECMAScript:

Примитивное значение — это конечная упорядоченная последовательность из нуля или более 16-битных беззнаковых целых значений.

Строковое значение — это элемент типа String. Каждое целое число последовательности обычно представляет один 16-битный элемент текста в UTF-16.

Иначе говоря, каждый символ JavaScript представлен в Unicode двумя байтами и закодирован в UTF-16.

Рассмотрим ряд примеров. Можно использовать одну или две кодовые единицы для создания символа:

const s1: string = '\u00E1' // á
const s2: string = '\u0061\u0301' // á

И s1, и s2 образуют á. Проверим длину обеих строк:

console.log(s1.length) // 1
console.log(s2.length) // 2

Длины разные, хотя строки представляют один и тот же символ. Заглянем внутрь строки с помощью индексации и посмотрим на составляющие ее элементы:

console.log(s1[0]) // á
console.log(s1[1]) // undefined

console.log(s2[0]) // a
console.log(s2[1]) //  ́
console.log(s2[2]) //  undefined (неопределен)

Как видно, s2 состоит из двух независимых элементов: a and ́.

Поскольку один и тот же символ может быть представлен по-разному, то очевидно, что индексация строк в JavaScript не является надежным критерием.

Проверим на равенство:

console.log(s1 === s2) // false 🧐

Сделаем задачу еще более интересной, воспользовавшись другим способом создания символа á:

const s3: string = 'a\u0301' // á

В s3 мы заменяем кодовую единицу \u0061 на представляющий ее символ a. Выполним несколько проверок:

console.log(s3.length === 2) // true
console.log(s2 === s3) // true 🧐
console.log(s1 === s3) // false

Как видим, один и тот же символ можно представить несколькими наборами кодовых единиц, которыми и определяется равенство.

Поскольку это может быть крайне не удобно, то в JavaScript представлен строковый метод normalize(), который возвращает форму нормализации Unicode данной строки. Применим его для s1, s2 и s3:

console.log(s1.normalize() === s2.normalize()) // true
console.log(s1.normalize() === s3.normalize()) // true

Заглянем внутрь нормализованных форм á:

// `escape` устарел. 
escape(s1.normalize()) // '%E1'
escape(s2.normalize()) // '%E1'
escape(s3.normalize()) // '%E1'

Обратите внимание, что метод escape() был удален из стандарта ECMAScript.

Благодаря нормализации обработка строк становится более прогнозируемой.

JavaScript предоставляет официальный Encoding API. Мы можем использовать TextEncoder и TextDecoder для кодирования и декодирования строк.

const encoder = new TextEncoder()
const decoder = new TextDecoder()
const bytes = encoder.encode('\u0061\u0301')
decoder.decode(bytes) // 'á'

Заключение

Строки сложны. Rust предлагает надежную систему для работы с ними и строгий компилятор, который побуждает программистов заранее продумывать их обработку. С другой стороны, JavaScript предоставляет удобныe API для решения простых случаев, таких как ASCII. Оба языка реализуют стандарт Unicode и кодировку для всемирной поддержки письменных языков.

Индексация строк в Rust и TypeScript в сравнениях

Краткое содержание

`is_palindrome` в Rust

Строки Rust представлены в кодировке Unicode и UTF-8

Корректировка `is_palindrome`

`isPalindrome` в TypeScript

Строки JavaScript представлены в кодировке UTF-16

Заключение

Читайте также

Сопряженное априорное распределение

ТОП-5 признаков качественного продуктового дизайна

Как организовать свою систему обработки данных: кейс mondayDB

Тесты

Насколько хорошо вы разбираетесь в Kotlin?

Что вы знаете о C#

Хорошо ли вы знаете JavaScript?

Краткое содержание

is_palindrome в Rust

Строки Rust представлены в кодировке Unicode и UTF-8

Корректировка is_palindrome

isPalindrome в TypeScript

Строки JavaScript представлены в кодировке UTF-16

Заключение

Читайте также

Сопряженное априорное распределение

ТОП-5 признаков качественного продуктового дизайна

Как организовать свою систему обработки данных: кейс mondayDB

Тесты

Насколько хорошо вы разбираетесь в Kotlin?

Что вы знаете о C#

Хорошо ли вы знаете JavaScript?

`is_palindrome` в Rust

Корректировка `is_palindrome`

`isPalindrome` в TypeScript