See our directory for easier navigation and a better overview of the project.
Read through our Contribution Guidelines before you contribute.
All Algorithms implemented in Rust
License: MIT License
See our directory for easier navigation and a better overview of the project.
Read through our Contribution Guidelines before you contribute.
There are a few linting errors and warnings currently, especially in ./src/data_structures
and ./src/graph
Examples:
error: parameter is only used in recursion
--> src\data_structures\b_tree.rs:104:39
|
104 | fn traverse_node<T: Ord + Debug>(&self, node: &Node<T>, depth: usize) {
| ^^^^
|
= note: `-D clippy::only-used-in-recursion` implied by `-D warnings`
note: parameter used here
--> src\data_structures\b_tree.rs:110:17
|
110 | self.traverse_node(&node.children[index], _depth);
| ^^^^
...
115 | self.traverse_node(node.children.last().unwrap(), _depth);
| ^^^^
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#only_used_in_recursion
error: parameter is only used in recursion
--> src\data_structures\linked_list.rs:185:26
|
185 | fn get_ith_node(&mut self, node: Option<NonNull<Node<T>>>, index: i32) -> Option<&T> {
| ^^^^
|
note: parameter used here
--> src\data_structures\linked_list.rs:190:22
|
190 | _ => self.get_ith_node(unsafe { (*next_ptr.as_ptr()).next }, index - 1),
| ^^^^
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#only_used_in_recursion
error: parameter is only used in recursion
--> src\general\huffman_encoding.rs:46:10
|
46 | &self,
| ^^^^
|
note: parameter used here
--> src\general\huffman_encoding.rs:63:17
|
63 | self.get_alphabet(height + 1, path, node.left.as_ref().unwrap(), map);
| ^^^^
64 | self.get_alphabet(
| ^^^^
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#only_used_in_recursion
error: use of `or_insert` followed by a call to `new`
--> src\graph\floyd_warshall.rs:53:34
|
53 | ... .or_insert(BTreeMap::new())
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try this: `or_default()`
|
= note: `-D clippy::or-fun-call` implied by `-D warnings`
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#or_fun_call
error: use of `or_insert` followed by a call to `new`
--> src\graph\prufer_code.rs:36:19
|
36 | tree.entry(a).or_insert(vec![]).push(b);
| ^^^^^^^^^^^^^^^^^ help: try this: `or_default()`
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#or_fun_call
While these issues are mainly stylistic it could be a good first PR opportunity for some quick fixes that stop warnings. Warnings about recursion may be unavoidable for some algorithms without making them completely cumbersome and hard to understand, in those cases #[allow(clippy::~specific_error~)] ...
(if everyone is ok with ignoring the warnings).
Hope to start some discussion on how to proceed as new warnings come about.
Thanks!
There are multiple problems in the repo that fall under CSP. Essentially a list of variables and constraints between them. It is not an algorithm but a class of problems that can be modeled in such a way, such as sudoku, n queens, graph coloring. There are multiple ways to solve them, one being backtracking. Could be considered a data structure? Otherwise I donโt know where it would live. I recently did an assignment for school in golang to make a sudoku and killer sudoku solver where we convert to a generic CSP to solve.
Where could this live in the repo? Itโs difficult to define every constraint that a problem would use but you can cover most problems with EQUALS and NOT_EQUALS constraints. Or maybe there is a good way to define constraints by passing in some lambda functions. Iโm not super experienced in rust but this could be something Iโd be interested to contribute.
by breaking early
I noticed there are a bunch of open PRs that haven't been reviewed. Any interest from @AnshulMalik in giving more people merge access? I have some time right now to review PRs, so I am volunteering to review some PRs.
Hi, I refactored the searching module, please merge #30 asap so that people can keep on working !
This trivial test fails:
#[test]
fn test_empty_heap() {
let mut heap = MaxHeap::new::<i32>();
assert_eq!(heap.next(), None)
}
---- data_structures::heap::tests::test_empty_heap stdout ----
thread 'data_structures::heap::tests::test_empty_heap' panicked at 'attempt to subtract with
overflow', src/data_structures/heap.rs:117:9
Other big issues:
Vec
contains a length meaning that count
is unneededDefault
can be entirely removed with zero-based indexing, saving memory and making the implementation more flexibleI am more than happy to enact these changes, if that is acceptable to you.
We should add a badge for https://gitter.im/the-algorithms/rust room in readme.
Since #3 is already overcrowded and we need to have our roadmap somewhere visible, I figured I should open a new issue. The list is currently my own to-do list, and maintainers' suggestions, additions, and ideas in general will be incorporated here. Also suggestions from community are welcome.
this is something we are covering in my algorithms course. it's possible to create algorithms that switch between different strategies based off the size of the input. for example this hybrid of selection sort and quick sort (using Hoare's partition scheme consistently outperforms a regular quick sort by a constant factor:
`
pub fn hybrid_quick_sort<T>(arr: &mut [T])
where
T: Ord + Clone,
{
let len = arr.len();
if len > 17 {
_hybrid_quick(arr, 0, len - 1)
} else {
selection_sort(arr)
}
}
fn _hybrid_quick<T>(arr: &mut [T], lo: usize, hi: usize)
where
T: Ord + Clone,
{
if lo < hi {
if hi - lo > 17 {
let p = partition(arr, lo, hi);
_hybrid_quick(arr, lo, p);
_hybrid_quick(arr, p + 1, hi);
} else {
selection_sort(&mut arr[lo..hi + 1]) //from first element to include to first element to exclude
}
}
}
Rust/src/data_structures/linked_list.rs
Line 199 in 6189823
it looks the implementation of drop is flawed and delete head is not returning none to terminate the drop process appropriately.
Consider e.g. the sorting algorithms: They all solve the same problem, yet each has its own test cases. This is only warranted if the tests are to test implementation details.
However, the better approach here is to write one comprehensive test suite - perhaps even using fuzzing - and testing all implementations against it. This will both increase coverage and reduce test duplication.
Hi guys,
thanks for this amazing project, really appreciate it! But here is one thing, and I feel like the most major idiot here, but I have to ask:
How do you use all these algorithms?
I mean, I did figure out you can not compile them one by one and have to 'cargo build' them, but then what? I am not experienced enough what to do next, and since the targets that got built aren't really readable or useful, how to use these algorithms?
Thanks!
Rust/src/string/aho_corasick.rs
Line 80 in a5cf37c
It will cause computing overflow when pattern appear at head of string.
If i - len + 1 == 0
, i - len
will be -1
first, then panic.
Change to i + 1 - len
will solve this.
In the algorithm for the Miller-Rabin primality test, 0 is reported as a prime. 0 should be special-cased by an initial "if 0 return false;" check. One can argue 0 is just invalid input for the algorithm, but I would then argue at least throwing an assert error on 0 input is preferable so it becomes clear to anyone reading or potentially copying the algorithm for primality testing that 0 is not a prime but not accounted for in the current algorithm logic.
The performance of insertion sort
can be enhanced by simply move items back instead of swap them:
pub fn insertion_sort<T>(arr: &mut [T])
where
T: cmp::PartialOrd + Copy,
{
for i in 1..arr.len() {
let cur = arr[i];
let mut j = i - 1;
while arr[j] > cur {
arr[j + 1] = arr[j]; // move items back
if j == 0 {
break;
}
j -= 1;
}
// we exit the loop from that break statement
if j == 0 && arr[0] > cur {
arr[0] = cur;
} else {
// `arr[j] > cur` is not satsified, exit from condition judgement
arr[j + 1] = cur;
}
}
}
By doing so, we can reduce the number of accesses to array elements by half. To demo this, I wrote a single test:
//! main.rs
mod sort;
use rand::random;
use sort::{insertion_enhanced_version, insertion_orig_version};
use std::{
env::args,
process::exit,
time::{Duration, Instant},
};
fn main() {
let av: Vec<String> = args().collect();
if av.len() < 3 {
eprintln!("usage: {} LEN <ALGORITHM>", av[0]);
exit(1);
}
let len: usize = av[1].parse().unwrap();
let mut s: Vec<i32> = random_array(len);
let now: Instant = Instant::now();
match av[2].as_str() {
"orig" => insertion_orig_version(&mut s),
"enhanced" => insertion_enhanced_version(&mut s),
_ => todo!("not implemented yet"),
}
let elapsed: Duration = now.elapsed();
println!(
"Use {} to sort {} numbers, consuming {:?}",
av[2].as_str(),
av[1].as_str(),
elapsed
);
}
fn random_array(len: usize) -> Vec<i32> {
(0..len).into_iter().map(|_| random()).collect()
}
//! sort.rs
pub fn insertion_enhanced_version<T>(arr: &mut [T])
where
T: PartialOrd + Copy,
{
for i in 1..arr.len() {
let cur = arr[i];
let mut j = i - 1;
while arr[j] > cur {
arr[j + 1] = arr[j];
if j == 0 {
break;
}
j -= 1;
}
// we exit the loop from that break statement
if j == 0 && arr[0] > cur {
arr[0] = cur;
} else {
// `arr[j] > cur` is not satsified, exit from condition judgement
arr[j + 1] = cur;
}
}
}
pub fn insertion_orig_version<T>(arr: &mut [T])
where
T: PartialOrd + Copy,
{
for i in 1..arr.len() {
let cur = arr[i];
let mut j = i - 1;
while arr[j] > cur {
arr.swap(j + 1, j);
if j == 0 {
break;
}
j -= 1;
}
}
}
You can specify how many items you wanna sort, and choose the algorithm you want, it will give you the time consumed on that:
$ cargo run 10000 orig
Use orig to sort 10000 numbers, consuming 683.218631ms
$ cargo run 10000 enhanced
Use enhanced to sort 10000 numbers, consuming 210.417512ms
$ cargo run 100000 orig
Use orig to sort 100000 numbers, consuming 68.68202042s
$ cargo run 100000 enhanced
Use enhanced to sort 100000 numbers, consuming 20.609979502s
As you can see, we got 3 times better performance:)
And this is the result tested on my machine:
$ neofetch
///////////// steve@pop-os
///////////////////// ------------
///////*767//////////////// OS: Pop!_OS 22.04 LTS x86_64
//////7676767676*////////////// Host: MacBookPro12,1 1.0
/////76767//7676767////////////// Kernel: 5.18.10-76051810-generic
/////767676///*76767/////////////// Uptime: 2 days, 21 hours, 16 mins
///////767676///76767.///7676*/////// Packages: 2426 (dpkg), 35 (flatpak)
/////////767676//76767///767676//////// Shell: zsh 5.8.1
//////////76767676767////76767///////// Resolution: 1920x1080
///////////76767676//////7676////////// DE: GNOME 42.2
////////////,7676,///////767/////////// WM: Mutter
/////////////*7676///////76//////////// WM Theme: Pop
///////////////7676//////////////////// Theme: Pop [GTK2/3]
///////////////7676///767//////////// Icons: Pop [GTK2/3]
//////////////////////'//////////// Terminal: tmux
//////.7676767676767676767,////// CPU: Intel i5-5257U (4) @ 3.100GHz
/////767676767676767676767///// GPU: Intel Iris Graphics 6100
/////////////////////////// Memory: 4352MiB / 7853MiB
///////////////////// Disk (/): 50G / 103G (52%)
/////////////
The current insertion sort algorithm differs greatly from the commonly implemented one, and could be improved in readability while maintaining performance
By using the same logic presented in #349 ("move items back instead of swapping them"), we can implement a more compact and simple algorithm, as shown below:
pub fn insertion_sort<T: Ord + Copy>(arr: &mut [T]) {
for i in 1..arr.len() {
let mut j = i;
let cur = arr[i];
while j > 0 && cur < arr[j - 1] {
arr[j] = arr[j - 1]; // move items back instead of swapping them
j -= 1;
}
arr[j] = cur;
}
}
For performance analysis, let's run the algorithm above and the currently implemented one for an input of size 100_000:
use std::cmp;
use std::time::Instant;
use rand::random;
// The current algorithm
fn insertion_sort_current<T>(arr: &mut [T])
where
T: cmp::PartialOrd + Copy,
{
// ...
}
// The proposed algorithm
fn insertion_sort_improved<T: Ord + Copy>(arr: &mut [T]) {
// ...
}
fn run_current(arr: &mut [u64]) {
let start = Instant::now();
insertion_sort_current(arr);
let duration = start.elapsed();
println!("Time elapsed in current insertion sort is: {:?}", duration);
}
fn run_improved(arr: &mut [u64]) {
let start = Instant::now();
insertion_sort_improved(arr);
let duration = start.elapsed();
println!("Time elapsed in improved insertion sort is: {:?}", duration);
}
fn main() {
const ARRAY_SIZE: usize = 100_000;
let mut arr_1: [u64; ARRAY_SIZE] = [0; ARRAY_SIZE];
for i in 0..ARRAY_SIZE {
arr_1[i] = random();
}
let mut arr_2 = arr_1.clone();
run_current(&mut arr_1);
run_improved(&mut arr_2);
}
The output:
$ cargo run
Time elapsed in current insertion sort is: 16.033703849s
Time elapsed in improved insertion sort is: 15.836348153s
As you can see, the performance between the two algorithms is practically the same, but the readability improves considerably
pub fn bubble_sort<T: Ord>(arr: &mut [T]) {
for i in 0..arr.len() {
for j in 0..arr.len() - 1 - i {
if arr[j] > arr[j + 1] {
arr.swap(j, j + 1);
}
}
}
}
can be changed to:
pub fn bubble_sort<T: Ord>(arr: &mut [T]) {
for i in 0..arr.len() - 1 {
for j in 0..arr.len() - 1 - i {
if arr[j] > arr[j + 1] {
arr.swap(j, j + 1);
}
}
}
}
to make sure that for a vector with n items, we just need to iterate n - 1 times
We should have a readme with some info just like other repositories have Python.
It should just highlight the things that we have implemented and the things which are yet to be implemented.
For now, it should just contain the headlines for different categories of algorithms and later, we can fill them with specific algorithms.
we can use SIMD to improve calculations and math speed
There is a good implementation of djikstra's algorithm in rust present here.
https://doc.rust-lang.org/std/collections/binary_heap/
Let me know if we can include this here.
Rosetta Code is a wiki of common programming problems, algorithms, etc written in different programming languages.
Another, smaller, but similar site is Programming Idioms
Rosetta Code is by far the most complete such project however. The entry for FizzBuzz for example contains solutions in 347 different languages
The linked_list module stores references to nodes using NonNull
s that are never dropped at any point.
Unless there is something I missed, this code doesn't ever free the memory allocated to the nodes.
The build_directory_md.py
run in our GitHub Action directory_workflow.yml should be replaced by Rust code.
This process should be done in three separate pull requests.
This issue is fairly easy and most beginners should be comfortable implementing algorithms of their choice in Rust. In case of any problem, raise an issue or just discuss it below.
Graphs
Dynamic Programming
Data Structures
General
Project Euler, LeetCode, etc.
hey, I recently had an assignment where I had to benchmark two sorting algorithms(selection and quick) against each other in order to create a hybrid, and did this using the sorting algorithms from this repository. I wrote the benchmarks using criterion, and was wondering if you would be open to adding benchmarks to this repository, it should be fairly trivial to take the benchmarks I created and refactor them to do benchmark all the comparative based sorting algorithms against each other.
you can find the benchmarks here and I'll be adding the markdown version of the actual report shortly
I think having similar signatures among methods that have same functionality (sorting, searching) should be followed. It is inconsistent if one sort accepts mutable vectors, another, mutable slices.
Having instance methods for something as simple as sort/search which doesn't require storing of a state also should be decided.
Hello, maybe im wrong, (im new to rust) but seeing the queue code, the dequeue operation
is taking O(n) time, and its suposed to take O(1) time.
I assume that the vector is implemented like in other languages (e.g c++) and a vector is really a dynamic array, and remove the first take O(n) because you need to swap all the elements one position to the left.
If this assumption is false, then ignore this comment.
We should remove the whole algorithm list from the README.md
file.
Here are a few reasons why we should do this:
DIRECTORY.md
file with a list of all algorithms.README.md
file longer and a bit more unreadable, IMO.What do you think about this? Thanks. ๐
I have a complete Vigenere encrypt algorithm written in Rust. However, my algorithm assumes that all characters in the text is ASCII. Since Rust strings are unicode encoded I think this is an implementation problem. The another problem is to make it work for other languages than English. I thought algorithm can take a trait (maybe called as Language
?) along with the text and key. In that way users can add their traits for their own languages.
There are multiple allow
statements in the codebase -
Rust/src/data_structures/heap.rs
Lines 136 to 138 in fbc20a7
Rust/src/data_structures/heap.rs
Lines 148 to 150 in fbc20a7
Lines 103 to 106 in fbc20a7
Lines 17 to 19 in fbc20a7
Lines 1 to 5 in fbc20a7
These are only few of them.
Should these be resolved or ignored ?
It's better if we write tests where we define the function, so it's easier to find.
There are few tests for search algorithms in https://github.com/TheAlgorithms/Rust/blob/master/src/lib.rs
We should move them to their modules
Travis moved from travis-ci.org to travis-ci.com, so you need to select 'Travis CI - Pull' and 'Travis CI - Branch' in status checks' settings and uncheck old setting.
With Hacktoberfest coming, I thought it might be a good idea to devise a strategy beforehand so that our contributors and community can make the most out of this event.
There are many, many algorithms out there, with variable degree of utility, that can be implemented by contributors, but most of them won't be of particular value, even though they can't be rejected. For example we won't be benefiting from yet another sorting algorithm with terrible run time behavior that was mentioned in $textbook
.
As such, it might be a good idea to somehow curate a to-do list with tasks of various difficulty levels for participants. The tasks need not be strictly coding related, but I can think of at least a few areas where we could benefit from having lots of new code (bignum, random and crypto to name a few.)
We can also start thinking of a new direction: Something like collecting all the accumulated knowledge here in a book or blog like platform to guide not only new learners, but also enthusiasts that could benefit from "human-readable" implementations of complex systems (like cryptography or random number generation for instance). One thing to keep in mind with this approach is that it will take a lot of polishing before it becomes anything useful.
To summarize, we need a strategy to make the most of this year's hacktoberfest. At very least a to-do list for new code and algorithms, but we may decide (and vote) to start being something more than a "just" repository to store algorithms. I think this issue might be a good place to start discussing our options.
Current implementation of merge sort
is top-down merge sort
Should we add bottom-up merge sort
?
Issue
ceil
function is only accurate to 1dp. For cases where n < num < n + 0.05
, it will incorrectly round down.
Demonstrating the issue
#[test]
fn positive_decimal() {
let num = 3.01;
assert_eq!(ceil(num), num.ceil());
}
There seems to be a .travis.yml
file, but I do not see any Travis runs on each commit.
Is it still being used? If so, we might want to move to GitHub Actions, which is faster and much easier.
If you agree with using GitHub Actions, I'd like to work on this. ๐
I remember that rust's index is from 0, and your code is
pub fn add(&mut self, value: T) {
self.count += 1;
self.items.push(value);
// Heapify Up
let mut idx = self.count;
while self.parent_idx(idx) > 0 {
let pdx = self.parent_idx(idx);
if (self.comparator)(&self.items[idx], &self.items[pdx]) {
self.items.swap(idx, pdx);
}
idx = pdx;
}
}
the idx should be self.count - 1
and the parent_index, left_child_index, right_index are wrong too,
the parent_index should be (index - 1) / 2
, left_child should be 2 * index + 1
, right_child should be 2 * index + 2
It's by far THE most important sorting implementation needed
Most sorting algorithms are named in the form alg_sort.rs, but insertion sort is named insertion.rs.
Hi everyone, as you may have noticed, there's some activity going on recently in this repo. That's me cleaning it up :) I'm a new maintainer of this repo and will do my best to review and give feedback on new PRs. There are a lot of old ones at the moment and I'm not a Rust expert to try and fix issues found in them on my own. So, please update your PRs by merging in the latest master branch and making sure that all checks pass. You can see more details as to why they fail by clicking on the "Details" link and then on the "The build" link.
Currently, all the tests related to sorting, test whether the array is sorted, I feel like the logic is repeated lot of times, it'd be awesome if we can create a helper function to check whether the slice is sorted or not.
This will help clean the code.
Typo in queue.rs, line 28.
This issue keeps track of implemented algorithms #3
This is the readme - https://github.com/TheAlgorithms/Rust
We need to keep the links in sync with the readme.
#3
A set of instructions should exist so that it's easier to format and add code prehand
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.