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

語言: CN / TW / HK

關注「 Rust程式設計指北 」,一起學習 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 書中提到的 ["नमस्ते"](https://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' // á

s1s2 兩者都是 á 。如果我們檢查兩個字串的長度:

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 由兩個獨立的元素組成, á

我們看到相同的字元可以以不同的方式表示,很明顯 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 標準和編碼,以支援國際上的書面語言。

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

參考資料

[1]

迴文: https://en.wikipedia.org/wiki/Palindrome

[2]

chars() : https://doc.rust-lang.org/stable/std/string/struct.String.html#method.chars

[3]

Rust 書籍: https://doc.rust-lang.org/book/

[4]

String 的內部表示: https://doc.rust-lang.org/book/ch08-02-strings.html#internal-representation

[5]

ASCII: https://en.wikipedia.org/wiki/ASCII

[6]

UTF-8: https://en.wikipedia.org/wiki/UTF-8

[7]

Unicode: https://en.wikipedia.org/wiki/Unicode

[8]

Rust 書中: https://doc.rust-lang.org/book/ch08-02-strings.html

[9]

bytes: https://doc.rust-lang.org/stable/std/string/struct.String.html#method.bytes

[10]

ECMAScript 標準: https://tc39.es/ecma262/#sec-terms-and-definitions-string-value

[11]

normalize() : https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/normalize

[12]

escape() : https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/escape

[13]

Encoding API: https://developer.mozilla.org/en-US/docs/Web/API/Encoding_API

[14]

TextEncoder: https://developer.mozilla.org/en-US/docs/Web/API/TextEncoder

[15]

TextDecoder: https://developer.mozilla.org/en-US/docs/Web/API/TextDecoder

推薦閱讀

覺得不錯,點個贊吧

掃碼關注「 Rust程式設計指北