惊!Rust 中这样操作字符串竟然是错的
文本在编程语言中是必不可少的。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(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]阅读更多关于它的信息。它非常容易阅读且有见地👏。
03 正确的 is_palindrome
我们可以迭代 bytes[9],并将字符串的前半部分与反向的后半部分进行比较。如果它们相等,这是一个回文:
// ✅
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 标准和编码,以支持国际上的书面语言。
原文链接:https://dawchihliou.github.io/articles/indexing-strings-in-rust-and-typescript
参考资料
回文: https://en.wikipedia.org/wiki/Palindrome
[2]chars()
: https://doc.rust-lang.org/stable/std/string/struct.String.html#method.chars
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
escape()
: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/escape
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