Rust 中這樣操作字串竟然是錯的

大家好，我是螃蟹哥！

文字在程式語言中是必不可少的。String 是 Rust 和 JavaScript 中定義用於處理世界各地書面語言中的文字。通過字串索引的簡單概念，我們將討論 Rust 和 JavaScript 如何處理字串，以及它們在如何處理字串（如 grapheme，甚至表情符號）中的細微差別。

我們使用經典演算法 is_palindrome 來介紹字串索引的概念。

01 Rust 中的 is_palindrome

迴文 ^[1] ，以一種非常一般的方式解釋它，是一個向前和向後閱讀都相同的字串。" Ana " 是迴文，" A dog! A panic in a pagoda! " 是迴文。

本文的目的，我們將使用更窄的定義來保持演算法的簡單性。此處的迴文被定義為"不帶空格的小寫 ASCII 字元的連續序列"。

一種直觀的方法是使用兩個指標。一個從給定字串的開頭開始，向末尾移動，另一個從末尾開始。移動指標時，比較指向的字元。如果所有比較都相等，則給定的字串是迴文。類似這樣：

// :x: It won't compile
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] {
    // ^^^^^^^ `String` cannot be indexed by `usize`
      return false;
    }
    lp += 1;
    rp -= 1;
  }

  true
}

如果你嘗試編譯程式，會注意到 Rust 編譯器不允許我們按索引訪問字元。這是一個非常有趣的約束，因為許多語言，如 JavaScript，Go 和 Python 都提供了該功能。

隨著我們深入挖掘，標準庫中有一些字串方法（如 `chars()` ^[2] ）來訪問字串中的字元。 chars() 返回字串切片 s 上的迭代器。因此，我們必須迴圈訪問字串切片以按索引訪問字元。例如像這樣：

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

訪問字串中字元這樣簡單的任務時間複雜度 是 O(n) 而不是   O(1) 。

為什麼？

02 Rust 的字串採用 Unicode/UTF-8 編碼

我們可以從官方的 Rust 書籍 ^[3] 中找到 String 的內部表示 ^[4] 。

字串是 Vec 的包裝器。

對於 ASCII ^[5] 中的字串，每個字元由 1 個以 UTF-8 ^[6] 編碼的位元組表示。但是，對於其他書面語言中的字串，例如 Rust 書中提到的 ["नमस्ते"](http://doc.rust-lang.org/book/ch08-02-strings.html#bytes-and-scalar-values-and-grapheme-clusters-oh-my ""नमस्ते"") 每個字元都以 UTF-8 編碼，具有多個 Unicode ^[7] 值（程式碼單元，即碼點）。

所以在 Rust 的書中，這樣說：

索引字串通常不是好的方式，因為不清楚字串索引操作的返回型別應該是什麼：位元組、字元、字形群（a grapheme cluster）或字串切片。

這是 Rust 編譯器不允許直接訪問字串中的字元的原因之一。我真的建議你在 Rust 書中 ^[8] 閱讀更多關於它的資訊。它非常容易閱讀且有見地:clap:。

03 正確的  is_palindrome

我們可以迭代 bytes ^[9] ，並將字串的前半部分與反向的後半部分進行比較。如果它們相等，這是一個迴文：

// :white_check_mark:
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(n)，其中 n 是字串的長度

空間複雜性 O(n) 是因為我們根據輸入字串的長度建立了兩個位元組迭代器。

04 TypeScript 中的 isPalindrome

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 中相當容易。這是否意味著 JavaScript 對字串的處理方式與 Rust 不同？

05 JavaScript 字串採用 UTF-16 編碼

我們可以在 ECMAScript 標準 ^[10] 中找到字串原始（primitive）值的定義：

原始值是零個或多個 16 位無符號整數值的有限有序序列

字串值是字串型別的成員。序列中的每個整數值通常表示 UTF-16 文字的單個 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 和 ́ 。

我們看到相同的字元可以以不同的方式表示，很明顯 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()` ^[11] 來返回給定字串的 Unicode 規範化形式。讓我們嘗試使用：

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

讓我們來看看 á 規範化形式的內部

// `escape` is deprecated.
escape(s1.normalize()) // '%E1'
escape(s2.normalize()) // '%E1'
escape(s3.normalize()) // '%E1'

請注意， `escape()` ^[12] 已從 ECMAScript 標準中刪除。

由於規範化，現在處理字串更加可預測。

JavaScript 實際上提供了一個官方的 Encoding API ^[13] 。我們可以使用 TextEncoder ^[14] 和 TextDecoder ^[15] 來處理字串編碼和解碼。

const encoder = new TextEncoder()
const decoder = new TextDecoder()

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

06 總結

字串很複雜。Rust 提供了一個強大的系統來處理字串，並提供了一個嚴格的編譯器，以鼓勵我們提前考慮字串處理。另一方面，JavaScript 提供了方便的 API 來處理像 ASCII 這樣的簡單用例。在引擎層面，它們都實現了Unicode 標準和編碼，以支援國際上的書面語言。

原文連結：http://dawchihliou.github.io/articles/indexing-strings-in-rust-and-typescript

參考資料