Rust 生命周期:这两种类型声明具有不同的生命周期。

huangapple go评论71阅读模式
英文:

Rust lifetimes: these two types are declared with different lifetimes

问题

Here is the translated code:

我正在学习Rust中的字符串。我想要实现一个函数来计算字符串列表中的最长公共前缀。

我的代码

impl Solution {
    pub fn get_common_prefix(s1: &String, s2: &String) -> String {
        let mut idx: usize = 0;
        if s1.len() > s2.len() {
            std::mem::swap(&mut s1, &mut s2);
        }
        
        while idx < s1.len() && s1.chars().nth(idx) == s2.chars().nth(idx) {
            idx += 1;    
        }
        return s1[0..idx].to_string();
    }
    pub fn longest_common_prefix(mut strs: Vec<String>) -> String {
        strs.sort();
        let mut longest_pref = strs[0].clone();
        for i in 0..strs.len() {
            longest_pref = Self::get_common_prefix(&longest_pref, &strs[i]);
        }
        return longest_pref;
    }
}

Regarding the error you mentioned, it seems to be a lifetime mismatch issue. You can fix it by cloning the strings in your longest_common_prefix function. I've made that change in the translated code above by using .clone(). This should resolve the error.

英文:

I am learning strings in Rust. I want to implement function to calculate the longes common prefix among list of strings.

My code

impl Solution {
    pub fn get_common_prefix(s1: &amp;String, s2: &amp;String) -&gt; String {
        let mut idx: usize = 0;
        if s1.len() &gt; s2.len() {
            std::mem::swap(&amp;mut s1, &amp;mut s2);
        }
        
        while idx &lt; s1.len() &amp;&amp; s1.chars().nth(idx) == s2.chars().nth(idx) {
            idx += 1;    
        }
        return s1[0..idx].to_string();
        
        
    }
    pub fn longest_common_prefix(mut strs: Vec&lt;String&gt;) -&gt; String {
        strs.sort();
        let mut longest_pref = strs[0];
        for i in 0..strs.len() {
            longest_pref = Self::get_common_prefix(&amp;longest_pref, &amp;strs[i]);
        }
        return longest_pref;
    }
}

I have an error. Could you please help to fix it?

Line 5, Char 37: lifetime mismatch (solution.rs)
  |
2 |     pub fn get_common_prefix(s1: &amp;String, s2: &amp;String) -&gt; String {
  |                                  -------      ------- these two types are declared with different lifetimes...
...
5 |             std::mem::swap(&amp;mut s1, &amp;mut s2);
  |                                     ^^^^^^^ ...but data from `s2` flows into `s1` here

I was reading about lifetimes here https://doc.rust-lang.org/rust-by-example/scope/lifetime.html but didn't succeeded

答案1

得分: 12

以下是您要翻译的内容:

如果您尝试显式表达隐式生命周期,您将得到get_common_prefix的以下签名:

fn get_common_prefix<'a, 'b>(s1: &'a String, s2: &'b String) -> String {
    ...
}

特别是,您不能交换这两个值,因为两个借用的寿命不会持续相同的时间。相反,您可以这样做

fn get_common_prefix<'a>(s1: &'a String, s2: &'a String) -> String {
    ...
}

这样做会解决问题,但也会引发许多其他错误,因为您的代码还有其他问题。让我们一一解决这些问题。

首先,它现在会抱怨std::mem::swap(&mut s1, &mut s2);是非法的,因为

error[E0596]: cannot borrow `s1` as mutable, as it is not declared as mutable
 --&gt; src/main.rs:4:24
  |
4 |         std::mem::swap(&mut s1, &mut s2);
  |                        ^^^^^^^ cannot borrow as mutable
  |
help: consider changing this to be mutable
  |
1 | pub fn get_common_prefix<'a>(mut s1: &'a String, s2: &'a String) -> String {
  |                              +++

error[E0596]: cannot borrow `s2` as mutable, as it is not declared as mutable
 --&gt; src/main.rs:4:33
  |
4 |         std::mem::swap(&mut s1, &mut s2);
  |                                 ^^^^^^^ cannot borrow as mutable
  |
help: consider changing this to be mutable
  |
1 | pub fn get_common_prefix<'a>(s1: &'a String, mut s2: &'a String) -> String {
  |                                              +++

但是,Rust非常友好,并告诉您在这种情况下该怎么做,将s1s2都声明为可变:

fn get_common_prefix<'a>(mut s1: &'a String, mut s2: &'a String) -> String {
    ...
}

现在get_common_prefix函数是正确的,但longest_common_prefix中仍然存在错误:

error[E0507]: cannot move out of index of `Vec<String>`
  --&gt; src/main.rs:16:28
   |
16 |     let mut longest_pref = strs[0];
   |                            ^^^^^^^ move occurs because value has type `String`, which does not implement the `Copy` trait
   |
help: consider borrowing here
   |
16 |     let mut longest_pref = &strs[0];
   |                            +

问题是您正在从strs中获取strs[0],但没有删除它,这是非法的,因为第一个字符串现在被拥有两次(一次由longest_pref拥有,一次由strs拥有)。

一种解决方法是使用swap_remove来实际获取strs[0](假设我们不关心元素的顺序,它非常高效地从向量中删除元素):

pub fn longest_common_prefix(mut strs: Vec<String>) -> String {
    strs.sort();
    let mut longest_pref = strs.swap_remove(0);
    for i in 1..strs.len() {
        longest_pref = get_common_prefix(&longest_pref, &strs[i]);
    }
    return longest_pref;
}

这样做虽然有效,但效率不高,有几个原因。首先,尽管性能损失不大,但在函数签名中使用&String几乎总是不正确的,因为您可以对其执行的操作(实际上,Rust将为您执行操作,因此您可能不会意识到它)只能将其Deref&str,这基本上是相同的,但减少了一层间接性(因为您可以将String视为指向str的指针)。因此,我们应该直接编写如下内容:

fn get_common_prefix<'a>(s1: &'a str, s2: &'a str) -> String {
    ...
}

此外,在我们可以返回字符串切片(因为我们正在获取子字符串)时,返回String没有意义,因此我们可以直接返回字符串的切片:

pub fn get_common_prefix<'a>(mut s1: &'a str, mut s2: &'a str) -> &'a str {
    let mut idx: usize = 0;
    if s1.len() > s2.len() {
        std::mem::swap(&mut s1, &mut s2);
    }
    
    while idx < s1.len() && s1.chars().nth(idx) == s2.chars().nth(idx) {
        idx += 1;    
    }
    return &s1[0..idx]
}

请注意,我更改了返回类型和最后一行。

现在,为了使其工作,我们还需要使longest_common_prefix能够使用字符串切片:

pub fn longest_common_prefix(mut strs: Vec<String>) -> String {
    strs.sort();
    let mut longest_pref: &str = &strs[0];
    for i in 1..strs.len() {
        longest_pref = get_common_prefix(&longest_pref, &strs[i]);
    }
    return longest_pref.to_string();
}

我们又回到了只是引用strs的第一个元素,而不是获取它。此外,当我们实际需要返回String时,我们只需在一次分配中执行它。

还有其他一些优化要做。首先,对strs进行排序是没有意义的,它不会改变longest_common_prefix的结果,因此我们可以将其删除:

pub fn longest_common_prefix(strs: Vec<String>) -> String {
    let mut longest_pref: &str = &strs[0];
    for i in 1..strs.len() {
        longest_pref = get_common_prefix(&longest_pref, &strs[i]);
    }
    return longest_pref.to_string();
}

接下来,s1.chars().nth(i)非常慢

英文:

If you tried to explicit the implicit lifetimes, you would get the following signature for get_common_prefix:

fn get_common_prefix&lt;&#39;a, &#39;b&gt;(s1: &amp;&#39;a String, s2: &amp;&#39;b String) -&gt; String { 
    ...
}

In particular, you can't swap these two values, because both borrows don't last as long as each other. Instead, you could do

fn get_common_prefix&lt;&#39;a&gt;(s1: &amp;&#39;a String, s2: &amp;&#39;a String) -&gt; String { 
    ...
}

Doing so will solve the issue, but will also throw a lot of other errors, because there are other issues with your code. Let's go through them one by one.

First of all, it will now complain that std::mem::swap(&amp;mut s1, &amp;mut s2); is illegal because

error[E0596]: cannot borrow `s1` as mutable, as it is not declared as mutable
 --&gt; src/main.rs:4:24
  |
4 |         std::mem::swap(&amp;mut s1, &amp;mut s2);
  |                        ^^^^^^^ cannot borrow as mutable
  |
help: consider changing this to be mutable
  |
1 | pub fn get_common_prefix&lt;&#39;a&gt;(mut s1: &amp;&#39;a String, s2: &amp;&#39;a String) -&gt; String {
  |                              +++

error[E0596]: cannot borrow `s2` as mutable, as it is not declared as mutable
 --&gt; src/main.rs:4:33
  |
4 |         std::mem::swap(&amp;mut s1, &amp;mut s2);
  |                                 ^^^^^^^ cannot borrow as mutable
  |
help: consider changing this to be mutable
  |
1 | pub fn get_common_prefix&lt;&#39;a&gt;(s1: &amp;&#39;a String, mut s2: &amp;&#39;a String) -&gt; String {
  |                                              +++

However, Rust is quite nice and tells you what to do in this case, declare both s1 and s2 as mutable:

fn get_common_prefix&lt;&#39;a&gt;(mut s1: &amp;&#39;a String, mut s2: &amp;&#39;a String) -&gt; String { 
    ...
}

The function get_common_prefix is now correct, but there is still an error in longest_common_prefix:

error[E0507]: cannot move out of index of `Vec&lt;String&gt;`
  --&gt; src/main.rs:16:28
   |
16 |     let mut longest_pref = strs[0];
   |                            ^^^^^^^ move occurs because value has type `String`, which does not implement the `Copy` trait
   |
help: consider borrowing here
   |
16 |     let mut longest_pref = &amp;strs[0];
   |                            +

The problem is that you are taking strs[0] from strs, but not removing it, which is illegal, because the first string would now be owned twice (once by longest_pref, and once by strs).

One solution is to actually take strs[0], with swap_remove (which is very efficient at removing elements from a vector, assuming we don't care about the order of the elements):

pub fn longest_common_prefix(mut strs: Vec&lt;String&gt;) -&gt; String {
    strs.sort();
    let mut longest_pref = strs.swap_remove(0);
    for i in 1..strs.len() {
        longest_pref = get_common_prefix(&amp;longest_pref, &amp;strs[i]);
    }
    return longest_pref;
}

This works, but... it's quite inefficient, for several reasons. First of all, even though it's not a terrible performance hit, it's almost always wrong to have a &amp;String in a function signature, because all you can do with it (actually, Rust will do it for you so maybe you don't realize it) is to Deref it to a &amp;str, which is basically the same with one less indirection (because you can see String as a pointer to str). So we should directly write that instead

fn get_common_prefix&lt;&#39;a&gt;(s1: &amp;&#39;a str, s2: &amp;&#39;a str) -&gt; String { 
    ...
}

Furthermore, there is no point in returning a String, which requires an allocation, when we can just return a slice over that string (because we are taking substrings):

pub fn get_common_prefix&lt;&#39;a&gt;(mut s1: &amp;&#39;a str, mut s2: &amp;&#39;a str) -&gt; &amp;&#39;a str {
    let mut idx: usize = 0;
    if s1.len() &gt; s2.len() {
        std::mem::swap(&amp;mut s1, &amp;mut s2);
    }
    
    while idx &lt; s1.len() &amp;&amp; s1.chars().nth(idx) == s2.chars().nth(idx) {
        idx += 1;    
    }
    return &amp;s1[0..idx]
}

Notice that I changed both the return type and the last line.

Now, for this to work, we also need to adapt longest_common_prefix to work with string slices:

pub fn longest_common_prefix(mut strs: Vec&lt;String&gt;) -&gt; String {
    strs.sort();
    let mut longest_pref: &amp;str = &amp;strs[0];
    for i in 1..strs.len() {
        longest_pref = get_common_prefix(&amp;longest_pref, &amp;strs[i]);
    }
    return longest_pref.to_string();
}

We went back to just referencing the first element of strs, not taking it. Also, we perform the allocation into a String just once, when we actually have to return a String.

There are still some other optimizations to be done. First, sorting strs is useless, it won't change the result of the longest_common_prefix, so we can remove that

pub fn longest_common_prefix(strs: Vec&lt;String&gt;) -&gt; String {
    let mut longest_pref: &amp;str = &amp;strs[0];
    for i in 1..strs.len() {
        longest_pref = get_common_prefix(&amp;longest_pref, &amp;strs[i]);
    }
    return longest_pref.to_string();
}

Next, s1.chars().nth(i) is very slow (Θ(i)). A more efficient way to do this is to reuse the same iterator (s1.chars()), and to advance it at each step, as so

for (c1, c2) in s1.chars().zip(s2.chars()) {
	if c1 != c2 {
	    break;
    }
    idx += 1;    
}

.zip() will not take any leftover characters from the longest string, so we can actually remove the swap at all, getting

pub fn get_common_prefix&lt;&#39;a&gt;(s1: &amp;&#39;a str, s2: &amp;&#39;a str) -&gt; &amp;&#39;a str {
    let mut idx: usize = 0;
    for (c1, c2) in s1.chars().zip(s2.chars()) {
        if c1 != c2 {
	        break;
        }
        idx += c1.len_utf8();    
    }
    return &amp;s1[0..idx]
}

Note: as indicated by @SebastianRedi, idx shouldn't be increased by 1 but by c1.len_utf8(), because when indexing a string, the indexes are expressed in bytes, not in characters, and some characters are more than a single byte long.

答案2

得分: 3

以下是您要翻译的代码部分:

响应评论中的讨论,这是一个正确使用扩展字符簇并适用于字符串切片的任意迭代器的`longest_common_prefix()`实现:

use unicode_segmentation::UnicodeSegmentation;

pub fn longest_common_prefix<'a, I>(strings: I) -> &'a str
where
    I: IntoIterator<Item = &'a str>,
{
    let mut iters: Vec<_> = strings.into_iter().map(|s| s.graphemes(true)).collect();
    match iters.len() {
        0 => return "",
        1 => return iters[0].as_str(),
        _ => {}
    };
    let first = iters[0].as_str();
    let mut length = 0;
    loop {
        let Some(g) = iters[0].next() else { break; };
        if iters[1..].iter_mut().any(|iter| iter.next() != Some(g)) {
            break;
        }
        length += g.len();
    }
    &first[..length]
}

在此函数之外仍然需要执行Unicode规范化,例如:

use unicode_normalization::UnicodeNormalization;

let strings = ...; // 输入字符串
let normalized: Vec<String> = strings.iter().map(|s| s.nfc().collect()).collect();
let common_prefix = longest_common_prefix(normalized.iter().map(|s| s.as_str()));

上述代码使用以下依赖项:

unicode-segmentation = "1.10.1"
unicode-normalization = "0.1.22"

请注意,我已经将代码部分翻译为中文,不包括代码中的注释。

英文:

In response to the discussion in the comments on the other answer, Here's an implementation of longest_common_prefix() that correctly uses extended grapheme clusters and works for arbitrary iterators of string slices:

use unicode_segmentation::UnicodeSegmentation;

pub fn longest_common_prefix&lt;&#39;a, I&gt;(strings: I) -&gt; &amp;&#39;a str
where
    I: IntoIterator&lt;Item = &amp;&#39;a str&gt;,
{
    let mut iters: Vec&lt;_&gt; = strings.into_iter().map(|s| s.graphemes(true)).collect();
    match iters.len() {
        0 =&gt; return &quot;&quot;,
        1 =&gt; return iters[0].as_str(),
        _ =&gt; {}
    };
    let first = iters[0].as_str();
    let mut length = 0;
    loop {
        let Some(g) = iters[0].next() else { break; };
        if iters[1..].iter_mut().any(|iter| iter.next() != Some(g)) {
            break;
        }
        length += g.len();
    }
    &amp;first[..length]
}

Unicode normalization still needs to be performed outside of this function, e.g. like this:

use unicode_normalization::UnicodeNormalization;

let strings = ...; // the input strings
let normalized: Vec&lt;String&gt; = strings.iter().map(|s| s.nfc().collect()).collect();
let common_prefix = longest_common_prefix(normalized.iter().map(|s| s.as_str()));

The code above uses these dependencies:

unicode-segmentation = &quot;1.10.1&quot;
unicode-normalization = &quot;0.1.22&quot;

huangapple
  • 本文由 发表于 2023年5月15日 14:07:07
  • 转载请务必保留本文链接:https://go.coder-hub.com/76251273.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定