有效地提取前缀子串

Question

目前我正在使用以下函数来提取前缀子串:

fn prefix(s: &String, k: usize) -> String {
    s.chars().take(k).collect::<String>()
}

然后可以将其用于比较,如下所示:

let my_string = "ACGT".to_string();
let same = prefix(&my_string, 3) == prefix(&my_string, 2);

但是,除了迭代处理之外,这还String为每次调用分配一个新prefix的.我熟悉的大多数其他语言都有一种有效的方法来进行这样的比较,只使用字符串的视图.Rust有办法吗？

Answer 1

是的,您可以使用以下Index操作获取字符串的子句:

fn prefix(s: &str, k: usize) -> &str {
    &s[..k]
}

fn main() {
    let my_string = "ACGT".to_string();
    let same = prefix(&my_string, 3) == prefix(&my_string, 2);
    println!("{}", same);
}

请注意,切片字符串使用字节作为单位,而不是字符.程序员应确保切片长度位于有效的UTF-8边界上.此外,您必须确保不要尝试切片超出字符串的末尾.打破其中任何一个将导致a panic!.

会有更多的防守版本

fn prefix(s: &str, k: usize) -> &str {
    let idx = s.char_indices().nth(k).map(|(idx, _)| idx).unwrap_or(s.len());
    &s[0..idx]
}

关键的区别在于我们使用char_indices迭代器,它告诉我们与字符对应的字节偏移量.索引到UTF-8字符串是一项O(n)操作,Rust不希望隐藏您的算法复杂性.这仍然不完整,因为例如可以组合字符.由于人类语言的复杂性,处理字符串很难.

我熟悉的大多数其他语言都有一种有效的方法

令人怀疑:-)为了及时有效,他们必须知道每个字符要跳过多少字节.要么他们必须为每个字符串保留一个查找表,要么使用固定大小的字符编码.这两种解决方案都可以使用比所需更多的内存,例如,当您组合字符时,固定大小的编码甚至不起作用.

当然,其他语言可以说"LOL,字符串只是字节数组,运气正确",并且有效地忽略了你的字符编码......

另外两个笔记

1. 你的谓词并没有多大意义.一串2个字母永远不会匹配3个字母中的一个.要匹配的字符串,它们必须具有相同的字节数.

2. 你永远不需要把它&String作为一个函数参数.&str在所有情况下采用a 是一个更容易接受的论点,除了一个无人需要的小小案例 - 知道a的容量String,但不能修改字符串.