6
\$\begingroup\$

I've attempted to solve a small coding challenge I found online as a nice way to begin learning Rust. The largest challenge I feel going in with Rust is how working with strings is so fundamentally different from any other programming language I've used before. The challenge was this:

Write a function that takes two strings, s1 and s2 and returns the longest common sequence of s1 and s2:

"ABAZDC", "BACBAD" => "ABAD"
"AGGTAB", "GXTKAYB" => "GTAB"
"aaaa", "aa" => "aa"
"ABBA", "ABJABA" => "ABBA"

The challenge seemed simple but the way I understood how I one could iterate though Rust strings proved to be very difficult. With numerous copies of iterators made and copies of Strings being made back and forth I am aware that this program is in its most naive form.

I wonder if collecting the string's characters into a vector would've been a better approach. I really want to find a more efficient method of solving this problem with Rust that'll be more comparable to C++ in terms of performance.

#[macro_use]
extern crate criterion;

use criterion::Criterion;

fn longest_con_seq(s1:&String, s2:&String) -> String {

    let mut max: Option<String> = None; // Holds value of string with maximum length
    let mut current = String::new(); // String container to hold current longest value
    let mut s1_iter = s1.chars().peekable(); // Peekable iterator for string s1
    let mut s2_iter = s2.chars(); //Iterator for string s2
    let mut s2_prev_pos = s2_iter.clone(); // Iterator that holds position of previous location of first iterator
    let mut s1_prev_pos = s1_iter.clone(); // Peekable iterator used to make sure all possible combinations are located.

    loop {  
        let s1_char = s1_iter.next(); // Get character in s1
        if current.len() == 0 // If no consequtive string found yet store location of iterator
        {
            s1_prev_pos = s1_iter.clone()
        }
        match s1_char{
            Some(s1_char)=>
            {   
                loop{    
                    match s2_iter.next()
                    {
                        Some(s2_char) if s1_char == s2_char => {
                            current.push(s1_char);
                            s2_prev_pos = s2_iter.clone();
                            break;
                        },
                        Some(_)=>continue,
                        None=>{
                            s2_iter = s2_prev_pos.clone();
                            break;
                        },
                    }
                }
            },
            None=>{
                match s1_prev_pos.peek()
                {
                    Some(_) => {
                        match max{
                            Some(_) => {
                                let max_str = max.clone();
                                let max_str = max_str.unwrap();
                                if max_str.len() < current.len(){
                                    max = Some(current.clone());
                                }
                                current.clear();
                            },
                            None => {
                                max = Some(current.clone());
                                current.clear();
                            },
                        }
                        s1_iter = s1_prev_pos.clone();
                        s2_iter = s2.chars();
                    },
                    None => break,
                }
            },
        }
    }
    if let Some(_) = max {
        return max.unwrap();
    } else {
        return String::from("");
    }
}
fn criterion_benchmark(c: &mut Criterion) {
    let s1 = "GXTKAYB".to_owned();
    let s2 = "AGGTAB".to_owned();
    c.bench_function("Benchmark", move |b| b.iter(|| longest_con_seq(&s1, &s2)));
}
criterion_group!(benches, criterion_benchmark);
criterion_main!(benches);

C++ comparison

I wrote a C++ version of the code that manipulates the strings through their indices. I though it would outperform the Rust code but it wasn't so.


#include <benchmark/benchmark.h>
#include <string>

std::string longest_con_seq(std::string &s1, std::string &s2)
{
    std::string max = "", current = "";
    size_t s2_old_idx = 0, s1_old_idx = 0;
    bool first_iter = true;
    for(size_t s1_idx = 0; s1_idx < s1.length(); ++s1_idx)
    {   
        if(first_iter)
            s1_old_idx = s1_idx;

        first_iter = false;
        for(size_t s2_idx = s2_old_idx; s2_idx < s2.length(); ++s2_idx)
        {
            if(s1[s1_idx] == s2[s2_idx])
            {
                s2_old_idx = s2_idx + 1;
                current += s1[s1_idx];
                break;
            }
        }

        if(s1_idx == s1.length()-1 && s1_old_idx != s1.length()-1)
        {
            s1_idx = s1_old_idx;
            s2_old_idx = 0;
            if(max.length() == 0 || max.length() < current.length())
            {
                max = current;
            }
            current.clear();
            first_iter = true;
        }
        else if( s1_old_idx == s1.length()-1 )
        {
            break;
        }
    }
    return max;
}


static void BM_LongestConSeq(benchmark::State& state) {
    std::string s1 = "GXTKAYB", s2 = "AGGTAB";
    for (auto _ : state)
    {
        longest_con_seq(s1,s2);
    }
}
// Register the function as a benchmark
BENCHMARK(BM_LongestConSeq);


BENCHMARK_MAIN();

Results

Rust

**time:**   [96.755 ns **97.291 ns** 98.031 ns]   
**change:** [-2.8521% _-1.4304%_ -0.1568%] (p = 0.04 < 0.05)  
                        Change within noise threshold.  
_Found 12 outliers among 100 measurements (12.00%)_  
5 (5.00%) high mild  
7 (7.00%) high severe

C++

Benchmark
----------
Time: **152 ns**  
CPU: **152 ns**  
Iterations: **4471469**

I really don't know how to interpret the results, I used Google Benchmark for the C++ code and Criterion for the Rust code. It seems to look like the Rust code has outperformed the C++ code, but maybe I'm wrong.

\$\endgroup\$
  • 1
    \$\begingroup\$ Sure, I'll write c++ version and benchmark both but its pretty clear with the ability to directly access indices with minimal to no copying of iterators the c++ solution would be much more efficient. \$\endgroup\$ – BiggySmallRyeda Jan 30 at 18:22
  • 1
    \$\begingroup\$ @BiggySmallRyeda I think you underestimate LLVM \$\endgroup\$ – Stargateur Jan 30 at 23:38
  • \$\begingroup\$ From experience with both C++ and Rust, performance is generally comparable, as long as you use equivalent operations. In terms of iterators specifically, C++ iterators compose badly, which generally give an edge to Rust if you start piling "filtering" iterators... but that's not very common. \$\endgroup\$ – Matthieu M. Jan 31 at 7:53
  • 1
    \$\begingroup\$ @MatthieuM. I added the edits you and the others recommended. I don't understand the results of the benchmark very well. Also, can someone judge my rust approach to the problem. \$\endgroup\$ – BiggySmallRyeda Jan 31 at 18:46
4
\$\begingroup\$
  1. Run Rustfmt, a tool for automatically formatting Rust code to the community-accepted style.
  2. Run Clippy, a tool for finding common mistakes that may not be compilation errors but are unlikely to be what the programmer intended.
  3. Don't accept a &StringWhy is it discouraged to accept a reference to a String (&String) or Vec (&Vec) as a function argument?
  4. Don't use explicit return keywords at the end of blocks.
  5. Instead of

    if let Some(_) = max {
        max.unwrap()
    

    bind the variable:

    if let Some(x) = max {
        x
    
  6. Your whole last conditional can be simplified to max.unwrap_or_default().

  7. Add some automated tests.

    #[test]
    fn example_1() {
        assert_eq!(longest_con_seq("ABAZDC", "BACBAD"), "ABAD");
    }
    
    #[test]
    fn example_2() {
        assert_eq!(longest_con_seq("AGGTAB", "GXTKAYB"), "GTAB");
    }
    
    #[test]
    fn example_3() {
        assert_eq!(longest_con_seq("aaaa", "aa"), "aa");
    }
    
    #[test]
    fn example_4() {
        assert_eq!(longest_con_seq("ABBA", "ABJABA"), "ABBA");
    }
    
  8. As before, don't match on Some and then unwrap, bind the variable. We can also avoid the clone by matching on a reference:

    match max {
        Some(_) => {
            let max_str = max.clone();
            let max_str = max_str.unwrap();
    
    match &max {
        Some(max_str) => {
    
  9. current.clear() is used in both match arms; extract it.

  10. max = Some(current.clone()) is the same; extract it and use a boolean.

    let do_it = match &max {
        Some(max_str) => {
            max_str.len() < current.len()
        }
        None => {
            true
        }
    };
    
    if do_it {
        max = Some(current.clone());
    }
    
  11. This construct can be replaced by as_ref and map_or:

    if max.as_ref().map_or(true, |s| s.len() < current.len()) {
        max = Some(current.clone());
    }
    

End result

#[macro_use]
extern crate criterion;

use criterion::Criterion;

fn longest_con_seq(s1: &str, s2: &str) -> String {
    let mut max: Option<String> = None; // Holds value of string with maximum length
    let mut current = String::new(); // String container to hold current longest value
    let mut s1_iter = s1.chars().peekable(); // Peekable iterator for string s1
    let mut s2_iter = s2.chars(); //Iterator for string s2
    let mut s2_prev_pos = s2_iter.clone(); // Iterator that holds position of previous location of first iterator
    let mut s1_prev_pos = s1_iter.clone(); // Peekable iterator used to make sure all possible combinations are located.

    loop {
        let s1_char = s1_iter.next(); // Get character in s1

        if current.is_empty() {
            // If no consecutive string found yet store location of iterator
            s1_prev_pos = s1_iter.clone()
        }

        match s1_char {
            Some(s1_char) => loop {
                match s2_iter.next() {
                    Some(s2_char) if s1_char == s2_char => {
                        current.push(s1_char);
                        s2_prev_pos = s2_iter.clone();
                        break;
                    }
                    Some(_) => continue,
                    None => {
                        s2_iter = s2_prev_pos.clone();
                        break;
                    }
                }
            },
            None => match s1_prev_pos.peek() {
                Some(_) => {
                    if max.as_ref().map_or(true, |s| s.len() < current.len()) {
                        max = Some(current.clone());
                    }
                    current.clear();

                    s1_iter = s1_prev_pos.clone();
                    s2_iter = s2.chars();
                }
                None => break,
            },
        }
    }

    max.unwrap_or_default()
}

fn criterion_benchmark(c: &mut Criterion) {
    let s1 = "GXTKAYB";
    let s2 = "AGGTAB";
    c.bench_function("Benchmark", move |b| b.iter(|| longest_con_seq(s1, s2)));
}

criterion_group!(benches, criterion_benchmark);
criterion_main!(benches);

#[test]
fn example_1() {
    assert_eq!(longest_con_seq("ABAZDC", "BACBAD"), "ABAD");
}

#[test]
fn example_2() {
    assert_eq!(longest_con_seq("AGGTAB", "GXTKAYB"), "GTAB");
}

#[test]
fn example_3() {
    assert_eq!(longest_con_seq("aaaa", "aa"), "aa");
}

#[test]
fn example_4() {
    assert_eq!(longest_con_seq("ABBA", "ABJABA"), "ABBA");
}

With numerous copies of iterators made and copies of Strings being made

Copies of iterators are generally going to be extremely lightweight. In many cases, they are equivalent to a pointer and and offset.

Cloning a String is slightly less ideal, but that may just be a restriction of the algorithm.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.