惊!Rust 中这样操作字符串竟然是错的

polarisxu

共 1416字,需浏览 3分钟

 ·

2022-03-05 18:47

文本在编程语言中是必不可少的。String 是 Rust 和 JavaScript 中定义用于处理世界各地书面语言中的文本。通过字符串索引的简单概念,我们将讨论 Rust 和 JavaScript 如何处理字符串,以及它们在如何处理字符串(如 grapheme,甚至表情符号)中的细微差别。

我们使用经典算法 is_palindrome 来介绍字符串索引的概念。

01 Rust 中的 is_palindrome

回文[1],以一种非常一般的方式解释它,是一个向前和向后阅读都相同的字符串。"Ana" 是回文,"A dog! A panic in a pagoda!" 是回文。

本文的目的,我们将使用更窄的定义来保持算法的简单性。此处的回文被定义为"不带空格的小写 ASCII 字符的连续序列"。

一种直观的方法是使用两个指针。一个从给定字符串的开头开始,向末尾移动,另一个从末尾开始。移动指针时,比较指向的字符。如果所有比较都相等,则给定的字符串是回文。类似这样:

// ❌ It won't compile
fn is_palindrome(strString) -> 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]阅读更多关于它的信息。它非常容易阅读且有见地👏。

03 正确的 is_palindrome

我们可以迭代 bytes[9],并将字符串的前半部分与反向的后半部分进行比较。如果它们相等,这是一个回文:

// ✅
fn is_palindrome(strString) -> 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



往期推荐


我是 polarisxu,北大硕士毕业,曾在 360 等知名互联网公司工作,10多年技术研发与架构经验!2012 年接触 Go 语言并创建了 Go 语言中文网!著有《Go语言编程之旅》、开源图书《Go语言标准库》等。


坚持输出技术(包括 Go、Rust 等技术)、职场心得和创业感悟!欢迎关注「polarisxu」一起成长!也欢迎加我微信好友交流:gopherstudio

浏览 105
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报