ebtech / rust-algorithms Goto Github PK
View Code? Open in Web Editor NEWCommon data structures and algorithms in Rust
License: MIT License
Common data structures and algorithms in Rust
License: MIT License
One problem I see with using Rust in programming competition websites is that we can't pull in external dependencies like rand
. Is there interest in simply offering a very short and sweet random number generator?
I was thinking about implementing a simple Treap for a dynamic BBST implementation (which is simple enough in Rust's ownership semantics), so maybe it makes sense to just embed a simple PRNG in the file. Options:
SmallRng
used in rand
: https://docs.rs/rand/0.8.4/src/rand/rngs/xoshiro256plusplus.rs.htmlDo you have any opinions about RNGs here?
Reading 2e5 integers from the file.
Your solution with unsafe gives times:
> cargo run
0.380072
> cargo run
0.328795
> cargo run
0.320145
Handmade parser over byte stream:
> cargo run
0.14436
> cargo run
0.130388
> cargo run
0.13056
use std::fs;
use std::io::{self, prelude::*};
use std::time::Instant;
use std::error::Error;
struct Parser
{
it: std::vec::IntoIter<u8>,
}
impl Parser
{
fn new(bytes: Vec<u8>) -> Parser {
Parser { it: bytes.into_iter() }
}
}
impl Iterator for Parser {
type Item = i32;
fn next(&mut self) -> Option<Self::Item> {
let mut ans = 0;
let mut sign = 1;
let mut started = false;
while let Some(b) = self.it.next() {
if b >= b'0' && b <= b'9' {
started = true;
ans = (b - b'0') as i32 + ans * 10;
} else if b == b'-' {
sign = -1;
} else if started == true {
break;
}
}
if started {
Some(ans * sign)
} else {
None
}
}
}
fn read() -> Result<(), Box<dyn Error>> {
let mut reader = io::BufReader::new(fs::File::open("stdin.txt")?);
let mut bytes: Vec<u8> = Vec::new();
reader.read_to_end(&mut bytes)?;
let mut parser = Parser::new(bytes);
let n = parser.next().ok_or("N")? as usize;
let mut v: Vec<i32> = Vec::with_capacity(n);
let mut empty = 0;
for token in parser {
if token == -1 {
empty += 1;
} else {
let token = token - 1;
v.push(token);
}
}
Ok(())
}
fn main() {
let instant = Instant::now();
if let Err(error) = read() {
eprintln!("{:?}", error);
}
println!("{}", instant.elapsed().as_micros() as f64 / 1e6);
}
.parse()
is an evil. Handmade solution faster in comparison to C++ with -O2
using std::scanf
and reading into an array.
0.171025
0.15101
0.149998
#include <iostream>
#include <chrono>
template<typename TimeT = std::chrono::microseconds>
struct measure
{
template<typename F, typename ...Args>
static double execution(F&& func, Args&&... args)
{
auto start = std::chrono::steady_clock::now();
std::forward<decltype(func)>(func)(std::forward<Args>(args)...);
auto duration = std::chrono::duration_cast< TimeT>
(std::chrono::steady_clock::now() - start);
return double(duration.count()) / 1e6;
}
};
void solve() {
std::freopen("stdin", "r", stdin);
std::freopen("stdout", "w", stdout);
int n, empty = 0;
std::scanf("%d", &n);
int v[size_t(2e5)]{-1};
for (size_t i = 0, p; i < n; ++i) {
std::scanf("%d", v + i);
}
}
int main () {
std::cerr << measure<>::execution(solve) << std::endl;
}
The doc comments should mention potential panics on inputs, such as an out of bounds find or merge on DisjointSets
It would be cool is this project was properly tagged, to be searchable on Github (for example, using rust
, algorithm
, etc ...). Tags are located under the name of the project.
Is there any chance you could get travis to generate html documentation and upload it to GitHub pages after every commit? I usually find the html docs really useful for quickly navigating a project, then you have the "src" link to look at the implementation.
I did something similar for my gcode-rs project.
I noticed a possible inconsistency between documentation and code implementation in rust-algorithms/src/string_proc.rs. The details can be found in the following code. The code does not check whether pattern is not empty before it is used but the constraint exists in the documentation.
/// # Panics
///
/// Panics if pattern is empty.
pub fn new(pattern: &'a [C]) -> Self {
let mut fail = Vec::with_capacity(pattern.len());
fail.push(0);
let mut len = 0;
for ch in &pattern[1..] {
while len > 0 && pattern[len] != *ch {
len = fail[len - 1];
}
if pattern[len] == *ch {
len += 1;
}
fail.push(len);
}
Self { pattern, fail }
}
For instance, how to submit my solution that uses this crate to a codeforces judge?
They require your solution to be in one file. Is there any kind of pre-submission script that could handle dumping the entire crate in the solution file?
Something like a splay tree or treap that can be easily augmented to e.g. track order statistics.
Hello,
Are you taking pull requests? I wrote a dfs method that returns an iterator for your graph class. I'm new to rust so I can't say if its the absolute best. It is iterative and keeps the state in the iterator struct. And of course a couple tests.
I also used a bit vector because why not :)
Let me know if this can be of interest and I'll create a proper PR. Otherwise, feel free to close this. Regardless a great repo, thank you !
use super::graph::Graph;
use bit_vec::BitVec;
impl Graph
{
fn dfs(&self, v: usize) -> DfsIterator
{
// Create a stack for DFS
let mut stack: Vec<usize> = Vec::new();
// Push the current source node.
stack.push(v);
DfsIterator {
graph: self,
visited: BitVec::from_elem(self.num_v(), false),
stack,
}
}
}
pub struct DfsIterator<'a>
{
graph: &'a Graph,
//is vertex visited
visited: BitVec,
//stack of vertices
stack: Vec<usize>,
}
impl<'a> Iterator for DfsIterator<'a>
{
type Item = usize;
/// Returns next vertex in the DFS
fn next(&mut self) -> Option<Self::Item>
{
let mut r = None;
//Code translated/adapted from https://www.geeksforgeeks.org/iterative-depth-first-traversal/
while !self.stack.is_empty() {
// Pop a vertex from stack and print it
let s = self.stack.pop().unwrap();
// Stack may contain same vertex twice. So
// we need to print the popped item only
// if it is not visited.
if !self.visited[s] {
self.visited.set(s, true);
r = Some(s);
}
// Get all adjacent vertices of the popped vertex s
// If a adjacent has not been visited, then puah it
// to the stack.
for (_e, u) in self.graph.adj_list(s) {
if !self.visited[u] {
self.stack.push(u);
}
}
if r != None {
return r;
}
}
return None;
}
}
#[cfg(test)]
mod test
{
use super::*;
#[test]
fn test_dfs()
{
let mut graph = Graph::new(4, 8);
graph.add_edge(0, 2);
graph.add_edge(2, 0);
graph.add_edge(1, 2);
graph.add_edge(0, 1);
graph.add_edge(3, 3);
graph.add_edge(2, 3);
//start at 2; -- 2 0 1 3
let dfs_search = graph.dfs(2).collect::<Vec<_>>();
assert_eq!(dfs_search, vec![2, 0, 1, 3]);
////https://www.geeksforgeeks.org/iterative-depth-first-traversal/
}
#[test]
fn test_dfs2()
{
let mut graph = Graph::new(5, 8);
graph.add_edge(0, 2);
graph.add_edge(2, 1);
graph.add_edge(1, 0);
graph.add_edge(0, 3);
graph.add_edge(3, 4);
graph.add_edge(4, 0);
let dfs_search = graph.dfs(0).collect::<Vec<_>>();
assert_eq!(dfs_search, vec![0, 2, 1, 3, 4]);
//0 3 4 2 1 or
//0 2 1 3 4
}
}
I just discovered this project and I thought this collection could benefit from implementations of algorithms like Miller-Rabin and Pollard-Rho. Thoughts?
If this does get the nod, I would love to implement this so I can practice my Rust skills.
Hey there!
I'm a mathematics instructor trying to transition into being a software developer looking for a good first PR and I was wondering if you guys were open to open source contributions. By nature of my job algorithms are kinda my jam and although there are several algorithm repositories on Github, this one seems to be the most recently active one.
I mentor both Rust and C on exercism.io but Rust is the programming language I'm excited about and looking to work with so I figure open source will be a good start.
Something like: https://github.com/mikolalysenko/bipartite-vertex-cover/blob/master/vcover.js
I can make a pull request when I'm done.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.