6 ms·
All Algorithms Implemented in Rust
- legerdemain 4y agoFinally, idiomatic and, most importantly, safe implementations of textbook algos and data structures!
- 29athrowaway 4y agoIt uses unsafe though
- eminence32 4y agoCode that uses the `unsafe` keyword can be safe, though.
- 29athrowaway 4y agoYes, but you are on your own, and future maintainers will also be on their own.
- kaba0 4y agoThe exact same way all other parts of the code is. You are also on your own in case of any logic bugs, which may well be likely even worse to debug.
- 29athrowaway 4y agoYes, but an important reason to migrate a solution to Rust are the guarantees that it offers with respect to safety. Those guarantees go away if you use "unsafe". In that case, you may just use C or C++.
- kaba0 4y agoSmall, encapsulated uses of unsafe wrapped in a safe wrapper are entirely different than thousands of lines of unsafe. Also - many of the borrow checker’s guarantees are enforced inside unsafe as well.
- klyrs 4y ago> and, most importantly, safe https://github.com/TheAlgorithms/Rust/search?q=unsafe https://github.com/TheAlgorithms/Rust/search?q=unsafe Almost there...
- filiphorvat 4y agoLinked list strikes again.
- MuffinFlavored 4y agoIs there not a way to do safe linked lists in Rust?
- msdrigg 4y agoYou can do a singly linked list just fine. But with a doubly linked list, who owns the memory to each node? In reality, you can do a doubly linked list with something like `RefCell`. See the famous blog post on linked lists in rust here: https://rust-unofficial.github.io/too-many-lists/fourth-building.html https://rust-unofficial.github.io/too-many-lists/fourth-buil...
- deleted 4y ago[deleted]
- howinteresting 4y agoBecause of cache locality issues, linked lists are a bad data structure for almost all purposes. A plain old vector, or maybe a VecDeque, wins for almost all workloads. For the few times they are useful (e.g. if you're writing lock-free algorithms, you want a hard upper bound O(1) append rather than just amortized O(1) append, or you don't have malloc available), Rust is a fine language to write them in. But also there are plenty of high-quality libraries on crates.io, so you probably won't have to write your own.
- jackpeterfletch 4y agoThe borrow checker makes a doublily linked list difficult, from my understanding. They're almost always a bad data structure to pick though, as the speed difference between being able to iterate a contiguous list, and even completely rebuild it, vs having to follow arbitrary pointers mean that the 'complexity' improvements of a linked list often become irrelevant. ------ Open Question) I have this intuition that the borrow checker might enforce a way of working that fundamentally stops you from doing things that aren't _really_ compatible with the way a CPU actually works on the lowest level. Is there any credence to that, and if so, is it happenstance, or is there some more fundamental reason?
- miohtama 4y agoSeems like all source code files I checked lacked comments, or had too little of them, so not so sure what is the reusability of this code.
- deleted 4y ago[deleted]
- dwroberts 4y agoI think the Karatsuba implementation is kind of missing the point of the whole exercise by just leaning on i128’s methods. It should really be defining a big num type or doing all the work on strings etc. It’s also going to explode if I put in a number with several thousand digits as it is unwrap()ing everywhere
- 0xADD1E 4y agoSo long as it’s never trying to parse a non-digit, the unwraps should be fine. Since it’s using i128s as arguments (and then converting them to strings to do the maths) that should be safe. For actual use, a proper bignum type for the arguments seems like it should be the biggest change needed though.
- IshKebab 4y agoFirst one I checked was `two_sum.rs` and it uses a `HashMap`: https://github.com/TheAlgorithms/Rust/blob/master/src/general/two_sum.rs https://github.com/TheAlgorithms/Rust/blob/master/src/genera... Surely the best way is to sort the numbers and then walk from both ends? Nice work anyway!
- 988747 4y agoNo expert on algorithms, but: Sorting an array is O(n*log(n)) Hashmap operations are constant time, and walking through array to put stuff in it is O(n) So, implementation based on Hashmap should be slightly faster. It requires extra memory, though.
- IshKebab 4y agoOh yeah that is true. I am an idiot.
- zodiac 4y agoDepends on what you mean by "best". For e.g. comparison-based sorting will already cost O(n log n) time but the HashMap solution will run in O(n) HashMap operations.
- chrismorgan 4y agoEww, eww, eww, why is that returning Vec<i32>? It should clearly be returning Option<(usize, usize)>. pub fn two_sum(nums: Vec<i32>, target: i32) -> Option<(usize, usize)> { let mut hash_map: HashMap<i32, i32> = HashMap::new(); for (i, item) in nums.iter().enumerate() { match hash_map.get(&(target - item)) { Some(value) => return Some((i, *value)), None => hash_map.insert(*item, i); } } None } If the caller wants to do something weird like converting the index to an i32 (which immediately means you can’t handle 2³¹ or more (~2 billion) items) or turning it into a zero-or-two-element Vec (which is inefficient and far easier to make mistakes with), they can do that themselves. This speaks very clearly to me that either there is some unreasonable constraint in place that I don’t immediately see, or neither the author nor the reviewer was at all competent in Rust.