HN Explorer

28 comments

[ 2.8 ms ] story [ 61.3 ms ] thread
legerdemain
Finally, idiomatic and, most importantly, safe implementations of textbook algos and data structures!
klyrs
> and, most importantly, safe

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

Almost there...

filiphorvat
Linked list strikes again.
MuffinFlavored
Is there not a way to do safe linked lists in Rust?
howinteresting
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.

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

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

ZephyrBlu
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.
klyrs
In the same way my c++ code is safe, yeah, the 'unsafe' code in this random-looking repo very well may be safe.
jjnoakes
Unsafe rust has numerous safety checks above and beyond C++...
yazaddaruvala
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.

miohtama
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.
29athrowaway
It uses unsafe though
eminence32
Code that uses the `unsafe` keyword can be safe, though.
29athrowaway
Yes, but you are on your own, and future maintainers will also be on their own.
kaba0
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.
29athrowaway
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++.

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

[deleted]
(comment deleted)
dwroberts
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

0xADD1E
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.
IshKebab
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!

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

IshKebab
Oh yeah that is true. I am an idiot.
zodiac
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.
chrismorgan
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.