bin+lib lcs_rs

Implementation of the longest common subsequence

2 releases

0.1.1 May 30, 2024
0.1.0 May 30, 2024

#754 in Algorithms

MIT license

8KB
145 lines

lcs_rs

crates.io docs.rs license

Longest common subsequence implementation in Rust (and Java).

Usage

let s1 = "GCACAGCGGT";
let s2 = "TTGTGAAATC";

assert!(lcs_rs::lcs(s1, s2) == "GAAT");

bench for the 10000-10000 test

Todo: make benchmarks in a loop

Rust

Time: 687.737625ms
Time: 713.694264ms

Java

Time: 623.69858 millis
Time: 668.713163 millis

This result varies ~ += 50 ms on my pc.

None of both implementations have been hardly optimized, but the algorithm used is quite fast.

Attempt to explain why rust is slower (please don't quote me on this)

Maybe the JVM allocates some space directly when launching the program, which makes the allocation of the matrix faster.

Rust needs to iterate over all chars to get the number of chars in the string, because an UTF-8 can have different sizes. I don't think Java does this.

No runtime deps