unicode - 在 Rust 中模拟 Python 的 `index(separator, start_index)`

Question

我目前正在从 Rust 从 Python 移植一个库，发现有一行我无法找到正确的“翻译”:

right = s.index(sep, left)

其中 right 是在 left 之后的字符串 s 中找到的第一个 sep 实例的索引>.

这里可以看到一个简单的例子:

Python 3

>>> s = "Hello, my name is erip and my favorite color is green."
>>> right = s.index("my", 10) # Find index of first instance of 'my' after index 10
>>> print right
27
>>> print s[27:]
my favorite color is green.

我在 Rust 中的尝试是:

// s: &str, sep: &str, left: usize
let right = s[left..].find(sep).unwrap() + left;

这将在 left 之后的字节中搜索 sep。这seems to work使用 ASCII 字符时。不过，使用 Unicode 时似乎存在问题:

Python 3

>>> s = "Hello, mÿ name is erip and mÿ favorite color is green."
>>> right = s.index("mÿ", 10)
>>> print(right)
27

Rust

fn main() {
    let sep: &str = "mÿ";
    let left: usize = 10;
    let s: &str = "Hello, mÿ name is erip and mÿ favorite color is green.";
    let right = s[left..].find(sep).unwrap() + left;
    println!("{}", right); //prints 28
}

我意识到 Python 2 也会给出 28，因为它本身不支持 Unicode，但我想模仿 Python 3 的结果。

问题是因为 Rust 中的 usize 指的是字符串中 bytes 的数量，因为“mÿ”实际上需要 3 个字节来编码。我怎样才能在 Rust 中获得这种期望的行为？

我正在使用 rustc 1.4.0。

Answer 1

让我们稍微重述一下问题，因为不清楚 index 的单位应该是什么。人们相信弦很容易，因为我们一生中的大部分时间都在使用它们。然而，事情远没有我们想的那么简单。

Rust 认为字符串(&str 或 String)是 UTF-8 编码的字节序列。使用字节偏移量跳转到字符串的复杂度为 O(1)，您确实希望这种级别的性能保证能够在其上构建更复杂的东西。

我不知道 Python 认为该索引是什么。一旦您超越了像 ASCII 这样一个字符是一个字节的简单编码方案，它就会变得困难。根据您的需要，有多种方法可以对 Unicode 字符串进行分块。两个明显的是通过 Unicode 代码点和字素。

由于代码点可以在 Rust 中使用 char 表示，这就是我假设您想要的。但是，您是唯一能弄清楚这一点的人。

此外，由于您要求结果为 28，因此它必须是字符串中的字节数。跳过 N 个代码点但返回字节有点奇怪，但事实就是如此。

---

现在我们知道我们在做什么...让我们尝试去做吧。 (请参阅下一个解决方案，我在其中更好地阅读了期望的结果)。

你需要使用的关键是char_indices .这是一个复杂度为 O(n) 的操作，遍历字符串并为您提供每个代码点及其对应的字节偏移量。

然后，只需将它们放在一起并正确处理离开字符串末尾的情况即可。 Rust 的强类型使这一点变得显而易见，万岁!

// `index` is the number of Unicode codepoints to skip
// The result is the number of **bytes** inside the haystack
// that the needle can be found.
fn python_index(haystack: &str, needle: &str, index: usize) -> Option<usize> {
    haystack.char_indices().nth(index).and_then(|(byte_idx, _)| {
        let leftover = &haystack[byte_idx..];
        leftover.find(needle).map(|inner_idx| inner_idx + byte_idx)
    })
}

fn main() {
    let right = python_index("Hello, mÿ name is erip and mÿ favorite color is green.", "mÿ", 10);
    println!("{:?}", right); // prints Some(28)
}

---

我们采用与上面相同的高级概念，但是一旦找到针，我们就会重新设置并再次遍历代码点。当我们找到子字符串的相同字节偏移量时，我们终止。

然后只需计算我们看到的字符数并添加我们已经跳过的数字即可。

// `index` is the number of Unicode codepoints to skip
// The result is the number of codepoints inside the haystack
// that the needle can be found.
fn python_index(haystack: &str, needle: &str, index: usize) -> Option<usize> {
    haystack.char_indices().nth(index).and_then(|(byte_idx, _)| {
        let leftover = &haystack[byte_idx..];

        leftover.find(needle).map(|inner_offset| {
            leftover.char_indices().take_while(|&(inner_inner_offset, _)| {
                inner_inner_offset != inner_offset
            }).count() + index
        })
    })
}

fn main() {
    let right = python_index("Hello, mÿ name is erip and mÿ favorite color is green.", "mÿ", 10);
    println!("{:?}", right); // prints Some(27)
}

这当然感觉效率不高；您想要进行基准测试以了解其表现如何。但是，find 实现非常优化，所以我宁愿使用它，然后直接通过字符并相信缓存和预取会帮助我解决问题 ^_^。