2 releases
0.1.1 | May 30, 2024 |
---|---|
0.1.0 | May 30, 2024 |
#754 in Algorithms
8KB
145 lines
lcs_rs
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.