All Algorithms Implemented in Rust | Hacker News Reader

All Algorithms Implemented in Rust

github.com

81 pointsfofoz26 comments

First one I checked was `two_sum.rs` and it uses a `HashMap`: 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!

Eww, 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.

No 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.

Oh yeah that is true. I am an idiot.

Depends 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.

I 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

So 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.

Finally, idiomatic and, most importantly, safe implementations of textbook algos and data structures!

> and, most importantly, safe

https://github.com/TheAlgorithms/Rust/search?q=unsafe

Almost there...

Depends whether by "safe" you mean "not using unsafe" or "the implementation is safe". Many core data structures in Rust use unsafe, but I think most people would consider them safe implementations.

In the same way my c++ code is safe, yeah, the 'unsafe' code in this random-looking repo very well may be safe.

Unsafe rust has numerous safety checks above and beyond C++...

I’m very surprised that the rbtree needs to be unsafe at all.

It feels like a very early attempt. Skip the parent pointers and use Option rather than raw null pointers. Should get rid of the unsafe.

Linked list strikes again.

Is there not a way to do safe linked lists in Rust?

You 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-buil...

The 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?

> 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.

No, I think you are reading too much into it. One is free to Box-allocate/pointer-chase on every line in Rust without any trouble. Sure, as other low level languages, rust also prefers/makes stack-allocation more ergonomic/the default, which is a quite cache-friendly way of operation but not even the stack is “native” in and of itself - it is just a frequently and extensively used part of the “heap”.

Because 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.

Seems 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.

It uses unsafe though

Code that uses the `unsafe` keyword can be safe, though.

Yes, but you are on your own, and future maintainers will also be on their own.

The 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.

Yes, 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++.

Small, 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.

Reply on news.ycombinator.com